Limits of Latin squares

Abstract

Limits of Latin squares, Discrete Analysis 2023:8, 66 pp. There has been a great deal of work over the last fifteen to twenty years on the theme of continuous limits of discrete combinatorial objects. In particular, any sequence of graphs of increasing size has a subsequence that converges in a suitable sense to a _graphon_, which is a measurable function $f:[0,1]^2\to [0,1]$. To see why this might be, one can apply Szemerédi's regularity lemma (or in fact weaker regularity lemmas suffice) to each graph and then replace each regular pair by a complete bipartite graph with all edges weighted by the density of that pair. The result is a weighted graph that approximately shares several important properties with the original graph, such as the number of edges joining two sets of vertices, or the number of copies of some fixed subgraph. It is also naturally associated with a graphon: one can partition $[0,1]$ into intervals corresponding to the vertex sets of the regular partition and define the measurable function to be constant on each product of those intervals, where the constant is the density of the bipartite graph induced by the corresponding pair of vertex sets. It is a short step from this observation to a proof that each sequence of graphs has a subsequence (after permuting vertices if necessary) that converges to a graphon. The convergence is in the _cut norm_, which is defined to be the supremum over any two sets $A,B\subset[0,1]$ of $|\int_{A\times B} f(x,y)dx\,dy|$. An important property of the limit is that for any fixed subgraph $H$, the density of copies of $H$ in the graphs in the sequence converges to the density of copies of $H$ in the limiting graphon. Another limiting object, of close relevance to this paper, is that of a _permuton_, which is the limit of a sequence of permutations. More precisely, it is the limit of a sequence of bijections from $\{1,2,\dots,n\}$ to itself, where we regard $\{1,2,\dots,n\}$ as an ordered set and not just a set. This makes it possible to talk about "patterns" that occur inside a permutation $\pi$: given a permutation $\sigma$ of $\{1,2,\dots,k\}$ for some fixed $k$, we say that $\sigma$ _occurs in_ $\pi$ if we can find $1\leq x_1 Image created specially for this article by [Ecir Baff](https://art-aleatoire.com/)