article
Substructures in Latin squares
published
yes
Matthew Alan
Kwan
author 5fca0887-a1db-11eb-95d1-ca9d5e0453b30000-0002-4003-7567
Ashwin
Sah
author
Mehtaab
Sawhney
author
Michael
Simkin
author
MaKw
department
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 Nature2023
eng
Israel Journal of Mathematics
0021-2172
1565-8511
2202.0508810.1007/s11856-023-2513-9
2562363-416
Kwan MA, Sah A, Sawhney M, Simkin M. 2023. Substructures in Latin squares. Israel Journal of Mathematics. 256(2), 363–416.
M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Israel Journal of Mathematics 256 (2023) 363–416.
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>
Kwan, Matthew Alan, et al. “Substructures in Latin Squares.” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 363–416, doi:<a href="https://doi.org/10.1007/s11856-023-2513-9">10.1007/s11856-023-2513-9</a>.
M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “Substructures in Latin squares,” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2. Springer Nature, pp. 363–416, 2023.
Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “Substructures in Latin Squares.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s11856-023-2513-9">https://doi.org/10.1007/s11856-023-2513-9</a>.
Kwan, M. A., Sah, A., Sawhney, M., & Simkin, M. (2023). Substructures in Latin squares. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href="https://doi.org/10.1007/s11856-023-2513-9">https://doi.org/10.1007/s11856-023-2513-9</a>
144442023-10-22T22:01:14Z2023-10-31T11:27:30Z