Covers and partial transversals of Latin squares (Q2414936): Difference between revisions

In order to delve into the study of transversals of Latin squares, both concepts of $c$-cover and partial transversal of deficit $d$ of a Latin square of order $n$ are introduced. The former (respectively, the latter) refers to a set of $c$ entries (respectively, $n-d$ entries) of the Latin square, with at least (respectively, at most) one entry per row, one entry per column and one entry per symbol. A cover is said to be minimal if it does not contain any proper subset being also a cover of the Latin square. On the other hand, a partial transversal is said to be maximal if it is not contained in a larger partial transversal. The paper deals with the relationship among all these concepts. Thus, for instance, it is proved that every $(n + a)$-cover contains a partial transversal of deficit $2a$. If $n\geq 2$, then every partial transversal of deficit $d$ is contained in an $(n + \lceil d/2 \rceil)$-cover. If the former is maximal, then the smallest cover containing it has size $n + \lceil d/2 \rceil$. As a consequence, the minimum size of a cover in a Latin square of order $n\geq 2$ is $n + a$ if and only if the minimum deficit of a partial transversal of such a Latin square is either $2a$ or $2a - 1$. If $n\geq 5$, then each entry of a Latin square having a transversal belongs to a minimal $(n + 1)$-cover. The authors also prove that every minimal cover of a Latin square of order $n$ has size at most $\lfloor 3(n + 1/2 - \sqrt{n + 1/4})\rfloor$. The existence of a Latin square of order $t^2 + t$ containing a minimal $c$-cover for all $c\in\{t^2 + t,\ldots, 3t^2\}$ is also ensured. Some asymptotical considerations and open problems are enumerated.