Substructures in Latin squares

DOI10.1007/S11856-023-2513-9MaRDI QIDQ6050265zbMATH OpenFDO

Authors Matthew Kwan, Ashwin Sah, Mehtaab Sawhney, Michael Simkin

Publication date 12 October 2023

Published in Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

high-girth Steiner triple systemsrandom Latin squares

Mathematics Subject Classification ID

Triple systems (05B07) Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: 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 $2imes2$ Latin subsquare) is at least $(e^{-9/4}n-o(n){)}^{n^2}$. Equivalently, $mathbbPleft[mathbfN=0ight]ge{e}^{-n^2/4-o(n^2)}=e^{-(1+o(1))mathbbEmathbfN}$, where $mathbfN$ 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<deltale1$ we have $mathbbP[mathbfNle(1-delta)mathbbEmathbfN]=exp(-Theta(n^2))$ and for any constant $delta>0$ we have $mathbbP[mathbfNge(1+delta)mathbbEmathbfN]=exp(-Theta(n^{4/3}logn))$. 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 $2imes2$ submatrices with the same arrangement of symbols) is of order $n^4$, 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.

Recommendations

• scientific article; zbMATH DE number 4183425
• The subconstituent algebra of a Latin square
• Orthogonal Latin squares with subsquares
• scientific article; zbMATH DE number 16249
• Latin squares with disjoint subsquares of two orders
• scientific article; zbMATH DE number 124515
• Sets of mutually orthogonal Latin squares with ``like subsquares
• scientific article; zbMATH DE number 3902665
• Subsquare-free Latin squares of odd order
• A generalization of plexes of Latin squares

Cites work

• A course in combinatorics.
• Almost all Steiner triple systems are almost resolvable
• Almost all Steiner triple systems have perfect matchings
• An upper bound on the number of high-dimensional permutations
• Asymptotic enumeration of Latin rectangles
• Bounds on the number of small Latin subsquares
• Clique decompositions of multipartite graphs and completion of Latin squares
• Completions of -dense partial Latin squares
• Counting designs
• Discrepancy of high-dimensional permutations
• Fractional clique decompositions of dense partite graphs
• Fractional triangle decompositions of dense 3-partite graphs
• Generating uniformly distributed random latin squares
• scientific article; zbMATH DE number 6473829 (Why is no real title available?)
• scientific article; zbMATH DE number 16254 (Why is no real title available?)
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 3485805 (Why is no real title available?)
• scientific article; zbMATH DE number 3532967 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Intercalates and discrepancy in random Latin squares
• Large deviations in random latin squares
• Large girth approximate Steiner triple systems
• Mappings of Latin squares
• Maximal nonassociativity via fields
• Maximally nonassociative quasigroups via quadratic orthomorphisms
• Minimalist designs
• Monotone subsequences in high-dimensional permutations
• Most Latin squares have many subsquares
• On a conjecture of Erdős on locally sparse Steiner triple systems
• On certain constructions for latin squares with no latin subsquares of order two
• On tail probabilities for martingales
• Partial associativity and rough approximate groups
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Shadows of colored complexes.
• Subsquare-free Latin squares of odd order
• The cycle structure of two rows in a random Latin square
• The infamous upper tail
• The solution of van der Waerden's problem for permanents
• Threshold for Steiner triple systems
• Upper tails via high moments and entropic stability

Cited in

(14)

• Most Latin squares have many subsquares
• Latin squares with a unique intercalate
• Discrepancy of high-dimensional permutations
• scientific article; zbMATH DE number 1066160 (Why is no real title available?)
• Intercalates and discrepancy in random Latin squares
• ON THE NUMBER OF QUADRATIC ORTHOMORPHISMS THAT PRODUCE MAXIMALLY NONASSOCIATIVE QUASIGROUPS
• Quasirandom Latin squares
• Large deviations in random latin squares
• Subsquares in random Latin squares and rectangles
• Isotopisms of quadratic quasigroups
• How to burn a Latin square
• Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings
• Multidimensional quadrangle condition and cuboctahedra in Latin hypercubes
• Subsquare-free Latin squares of odd order

This page was built for publication: Substructures in Latin squares

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