Limits of Latin squares

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<\dots<x_k\leq n$ such that the orderings of $\pi(x_1),\dots,\pi(x_k)$ and $\sigma(x_1),\dots,\sigma(x_k)$ are the same. The density of $\sigma$ in $\pi$ is the probability that the orderings are the same if we choose $x_1,\dots,x_k$ uniformly at random from all $\binom nk$ possibilities.

Just as a graphon is a slightly more complicated object than a graph, since it takes values in $[0,1]$ rather than in $\{0,1\}$, so a permuton is slightly more complicated than a permutation, since it takes values in a kind of continuous doubly stochastic matrix: that is, a measure on $[0,1]^2$ such that every marginal in each direction has measure 1.

A Latin square is a function $L:\{1,2,\dots,n\}^2\to\{1,2,\dots,n\}$ that is injective in each variable separately. That is, if we write it as a matrix, then each row and each column contains each number between 1 and $n$ exactly once. An example of a Latin square is a group multiplication table, but by no means all Latin squares arise this way.

If we associate with a Latin square $L$ the subset $\{(x,y,z):z=L(x,y)\}$ of $\{1,2,\dots,n\}^3$, then we obtain a 3-dimensional set that intersects every line parallel to one of the axes in exactly one point. If we take the characteristic function of this set, we obtain a 3-dimensional 01-matrix that has one 1 in each row in each of the three directions, so it is a natural 3-dimensional analogue of a permutation matrix. In particular, all its 2-dimensional slices are permutation matrices.

This paper defines the notion of a Latinon, the appropriate limiting object for Latin squares, and develops the basic theory. As with permutons, the order on the set $\{1,2,\dots,n\}$ is very much taken into account. It is not quite as straightforward to talk about patterns in Latin squares, since if $L$ is a large Latin square and we choose two small subsets $A,B\subset\{1,2,\dots,n\}$ of the same size, then the restriction of $L$ to $A\times B$ will almost never be a Latin square. Nevertheless, such restrictions are considered: if $A=\{a_1,\dots,a_k\}$ and $B=\{b_1,\dots,b_k\}$, with $a_1<\dots<a_k$ and $b_1<\dots<b_k$, then $L$ gives us an ordering on $\{1,2,\dots,k\}^2$, which except in a few degenerate cases will be a total ordering, and this ordering is the kind of pattern for which we discuss densities. For instance, given a Latin square, we can ask for the probability $p$ that if $a_1<a_2$ and $b_1<b_2$ are chosen uniformly at random, then $L(a_1,b_2)<L(a_2,b_2)<L(a_2,b_1)<L(a_1,b_1)$, and $p$ will be the density of that pattern. The authors show that for every sequence of Latin squares there is a subsequence and a Latinon such that the densities of all patterns of this type converge to their densities in the Latinon. To give an example, the addition tables of the cyclic groups mod $n$ converge to an object that is basically the addition table of the group $\mathbb R/\mathbb Z$, though more formally it is the function that takes $(x,y)$ to the probability measure $\delta_{x+y}$.

Note that if one takes the three-dimensional view of a Latin square mentioned above, then the roles of the third coordinate in these patterns are not the same as that of the other two. For this reason, the definition the authors give of a Latinon is not the obvious three-dimensional generalization of the definition of a permuton, but a more complicated object that allows them to analyse these non-symmetric pattern densities.

Another source of complexity that arises for Latinons that is not a difficulty for either graphons or permutons is that it is not clear how to associate with a Latinon a large Latin square that approximates it. Consider for instance the graphon that takes the value 1/2 everywhere. This can be well approximated by a random graph with edge probability 1/2. Similarly, if we consider the uniform measure on $[0,1]^2$ as a permuton, it is well approximated by a random permutation. However, if we take the Latinon that associates with each point in $[0,1]^2$ the uniform distribution on $[0,1]$, it is much less clear what to do. Of course, we could just take the uniform distribution on all $n\times n$ Latin squares, but this distribution has very complicated dependencies, so is much harder to understand. Indeed, there are several interesting open problems concerning enumeration of $n\times n$ Latin squares (even approximately), or generating them efficiently (even approximately uniformly), and so on. If we now move from the uniform Latinon to one that is a bit more complicated, it is far from obvious how to associate with it a large Latin square.

The authors conclude their paper with suggestions for further work. One natural line of enquiry is to generalize the results of this paper to $k$-dimensional permutations for arbitrary $k$, which appears to require new ideas: the difficulties are related to the fact that 3-uniform hypergraphs are significantly more complicated objects than graphs.

_{Image created specially for this article by Ecir Baff}