{
  "id": "2202.05088",
  "version": "v1",
  "published": "2022-02-10T15:16:04.000Z",
  "updated": "2022-02-10T15:16:04.000Z",
  "title": "Substructures in Latin squares",
  "authors": [
    "Matthew Kwan",
    "Ashwin Sah",
    "Mehtaab Sawhney",
    "Michael Simkin"
  ],
  "comment": "32 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "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 $2\\times2$ Latin subsquare) is at least $(e^{-9/4}n-o(n))^{n^{2}}$. Equivalently, $\\Pr\\left[\\mathbf{N}=0\\right]\\ge e^{-n^{2}/4- (n^{2})}=e^{-(1+o(1))\\mathbb{E}\\mathbf{N}}$, where $\\mathbf{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<\\delta\\le1$ we have $\\Pr[\\mathbf{N}\\le(1-\\delta)\\mathbb{E}\\mathbf{N}]=\\exp(-\\Theta(n^{2}))$ and for any constant $\\delta>0$ we have $\\Pr[\\mathbf{N}\\ge(1+\\delta)\\mathbb{E}\\mathbf{N}]=\\exp(-\\Theta(n^{4/3}(\\log n)^{2/3}))$. Finally, we show that in almost all order-$n$ Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate $2\\times2$ subsquares 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-02-10T15:16:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "substructures",
      "high-girth steiner triple systems",
      "general large-deviation problem",
      "random latin squares",
      "intercalate"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}