Latin squares with maximal partial transversals of many lengths

DOI10.1016/J.JCTA.2021.105403MaRDI QIDQ2229166zbMATH OpenOpenAlexFDO

Authors Anthony B. Evans, Adam Mammoliti, Ian M. Wanless

Publication date 22 February 2021

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.05912

zbMATH Keywords

Latin squareCayley tablesubsquaremaximal partial transversalomniversal

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: 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 $lceilfracn2ceil$ and at most $n$. We say that a Latin square is omniversal if it possesses a maximal partial transversal of all feasible sizes and is near-omniversal if it possesses a maximal partial transversal of all feasible sizes except one. Evans showed that omniversal Latin squares of order $n$ exist for any odd $neq3$. By extending this result, we show that an omniversal Latin square of order $n$ exists if and only if $notin3,4$ and $notequiv2mod4$. Furthermore, we show that near-omniversal Latin squares exist for all orders $nequiv2mod4$. Finally, we show that no non-trivial group has an omniversal Cayley table, and only 15 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 feasible sizes of maximal partial transversals. In the course of proving this, we are led to consider the following interesting problem in combinatorial group theory. Suppose that we have two subsets $R,CsubseteqG$ of a finite group $G$ such that $|rc:rinR,cinC|=m$. How large do $|R|$ and $|C|$ need to be (in terms of $m$) to be certain that $RsubseteqxH$ and $CsubseteqHy$ for some subgroup $H$ of order $m$ in $G$, and $x,yinG$.

Recommendations

• Maximal partial transversals in a class of latin squares
• On transversals in Latin squares
• On the number of transversals in Latin squares
• Latin squares with restricted transversals
• Latin squares with restricted transversals
• A generalization of transversals for Latin squares
• Transversals in generalized Latin squares
• scientific article; zbMATH DE number 1885937
• On the number of transversals in a class of Latin squares
• Transversals in Latin squares: a survey

Cites work

• scientific article; zbMATH DE number 3120863 (Why is no real title available?)
• scientific article; zbMATH DE number 3745510 (Why is no real title available?)
• A Combinatorial Theorem with an Application to Latin Rectangles
• A note on finite abelian groups
• Abschätzung der asymptotischen Dichte von Summenmengen
• Bounds on the number of small Latin subsquares
• Closest multiplication tables of groups
• Covers and partial transversals of Latin squares
• Extensions of the Scherk-Kemperman theorem
• How far apart can the group multiplication tables be?
• Maximal partial transversals in a class of latin squares
• On the distance between non-isomorphic groups.
• On the sum of two sets in a group
• Orthogonal Latin squares based on groups
• The Hall-Paige conjecture, and synchronization for affine and diagonal groups
• Transversals in Latin squares: a survey

Cited in

(8)

• Completing partial transversals of Cayley tables of Abelian groups
• On the maximum number of Latin transversals
• Full and quarter plane complete infinite Latin squares
• Maximal partial transversals in a class of latin squares
• Domination for Latin square graphs
• All group‐based latin squares possess near transversals
• Covers and partial transversals of Latin squares
• Small partial Latin squares that cannot be embedded in a Cayley table

This page was built for publication: Latin squares with maximal partial transversals of many lengths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229166)