Latin squares with maximal partial transversals of many lengths

DOI10.1016/J.JCTA.2021.105403zbMATH Open1491.05042arXiv1911.05912OpenAlexW3120529259MaRDI QIDQ2229166FDOQ2229166

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)

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$.

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

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

zbMATH Keywords

Latin squareCayley tablesubsquaremaximal partial transversalomniversal

Mathematics Subject Classification ID

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

Cites Work

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

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
• All group‐based latin squares possess near transversals
• Domination for Latin square graphs
• 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)