TY - JOUR

T1 - Latin squares with maximal partial transversals of many lengths

AU - Evans, Anthony B.

AU - Mammoliti, Adam

AU - Wanless, Ian M.

PY - 2021/5

Y1 - 2021/5

N2 - A partial transversal T of a Latin square L is a set of entries of L in which each row, column and symbol is represented at most once. A partial transversal is maximal if it is not contained in a larger partial transversal. Any maximal partial transversal of a Latin square of order n has size at least [Formula presented] and at most n. We say that a Latin square is omniversal if it possesses a maximal partial transversal of all plausible sizes and is near-omniversal if it possesses a maximal partial transversal of all plausible sizes except one. Evans (2019) showed that omniversal Latin squares of order n exist for any odd n≠3. By extending this result, we show that an omniversal Latin square of order n exists if and only if n∉{3,4} and n≢2(mod4). Furthermore, we show that near-omniversal Latin squares exist for all orders n≡2(mod4). Finally, we show that no non-trivial finite group has an omniversal Cayley table, and only 15 finite groups have a near-omniversal Cayley table. In fact, as n grows, Cayley tables of groups of order n miss a constant fraction of the plausible sizes of maximal partial transversals. In the course of proving this, we partially solve the following interesting problem in combinatorial group theory. Suppose that we have two finite subsets R,C⊆G of a group G such that |{rc:r∈R,c∈C}|=m. How large do |R| and |C| need to be (in terms of m) to be certain that R⊆xH and C⊆Hy for some subgroup H of order m in G, and x,y∈G?

AB - A partial transversal T of a Latin square L is a set of entries of L in which each row, column and symbol is represented at most once. A partial transversal is maximal if it is not contained in a larger partial transversal. Any maximal partial transversal of a Latin square of order n has size at least [Formula presented] and at most n. We say that a Latin square is omniversal if it possesses a maximal partial transversal of all plausible sizes and is near-omniversal if it possesses a maximal partial transversal of all plausible sizes except one. Evans (2019) showed that omniversal Latin squares of order n exist for any odd n≠3. By extending this result, we show that an omniversal Latin square of order n exists if and only if n∉{3,4} and n≢2(mod4). Furthermore, we show that near-omniversal Latin squares exist for all orders n≡2(mod4). Finally, we show that no non-trivial finite group has an omniversal Cayley table, and only 15 finite groups have a near-omniversal Cayley table. In fact, as n grows, Cayley tables of groups of order n miss a constant fraction of the plausible sizes of maximal partial transversals. In the course of proving this, we partially solve the following interesting problem in combinatorial group theory. Suppose that we have two finite subsets R,C⊆G of a group G such that |{rc:r∈R,c∈C}|=m. How large do |R| and |C| need to be (in terms of m) to be certain that R⊆xH and C⊆Hy for some subgroup H of order m in G, and x,y∈G?

KW - Cayley table

KW - Latin square

KW - Maximal partial transversal

KW - Omniversal

KW - Subsquare

UR - http://www.scopus.com/inward/record.url?scp=85099192573&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2021.105403

DO - 10.1016/j.jcta.2021.105403

M3 - Article

AN - SCOPUS:85099192573

SN - 0097-3165

VL - 180

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

M1 - 105403

ER -