Substructures in Latin squares
Kwan, Matthew Alan
Sah, Ashwin
Sawhney, Mehtaab
Simkin, Michael
We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares, resolving a conjecture of Linial that there exist Latin squares with arbitrarily high girth. As a consequence, we see that the number of order- n Latin squares with no intercalate (i.e., no 2×2 Latin subsquare) is at least (e−9/4n−o(n))n2. Equivalently, P[N=0]≥e−n2/4−o(n2)=e−(1+o(1))EN
, where N is the number of intercalates in a uniformly random order- n Latin square.
In fact, extending recent work of Kwan, Sah, and Sawhney, we resolve the general large-deviation problem for intercalates in random Latin squares, up to constant factors in the exponent: for any constant 0<δ≤1 we have P[N≤(1−δ)EN]=exp(−Θ(n2)) and for any constant δ>0 we have P[N≥(1+δ)EN]=exp(−Θ(n4/3logn)).
Finally, as an application of some new general tools for studying substructures in random Latin squares, we show that in almost all order- n Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate 2×2 submatrices with the same arrangement of symbols) is of order n4, which is the minimum possible. As observed by Gowers and Long, this number can be interpreted as measuring ``how associative'' the quasigroup associated with the Latin square is.
Springer Nature
2023
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/14444
Kwan MA, Sah A, Sawhney M, Simkin M. Substructures in Latin squares. <i>Israel Journal of Mathematics</i>. 2023;256(2):363-416. doi:<a href="https://doi.org/10.1007/s11856-023-2513-9">10.1007/s11856-023-2513-9</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/s11856-023-2513-9
info:eu-repo/semantics/altIdentifier/issn/0021-2172
info:eu-repo/semantics/altIdentifier/issn/1565-8511
info:eu-repo/semantics/altIdentifier/arxiv/2202.05088
info:eu-repo/semantics/openAccess