Discrepancy of High-Dimensional Permutations

Discrepancy of high-dimensional permutations, Discrete Analysis 2016:11, 8pp.

A permutation matrix is a (necessarily square) 01-matrix with exactly one 1 in each row and column. A three-dimensional analogue of a permutation matrix is a three-dimensional grid of 0s and 1s – more formally, a function \(f:\{1,2,\dots,n\}^3\to\{0,1\}\) – such that for every \(x,y\) there is exactly one \(z\) such that \(f(x,y,z)=1\), and similarly for the other two coordinates. (An alternative generalization would be to say that for every \(x\) there is exactly one pair \((y,z)\) such that \(f(x,y,z)=1\), but this generalization is more interesting.) An equivalent, but less symmetric, definition is that it is a function \(g:\{1,2,\dots,n\}^2\to\{1,2,\dots,n\}\) such that for each \(x\) the function \(y\mapsto g(x,y)\) is a bijection and for each \(y\) the function \(x\mapsto g(x,y)\) is a bijection. Such objects are called Latin squares: given a Latin square \(g\) the corresponding three-dimensional permutation \(f\) is defined by taking \(f(x,y,z)\) to be 1 if and only if \(g(x,y)=z\); in the other direction, given a three-dimensional permutation \(f\), the corresponding Latin square is defined by setting \(g(x,y)\) to be the unique \(z\) such that \(f(x,y,z)=1\). To put this more concisely, \(f\) is the characteristic function of the graph of \(g\). (Just to be clear, in the paper, the authors refer to a normal permutation as a one-dimensional permutation, since it permutes a one-dimensional array of objects, and in general a \(d\)-dimensional permutation has a \((d+1)\)-dimensional array of 0s and 1s as its “matrix”.)

An important branch of combinatorics, with links to analysis, number theory and other areas, is discrepancy theory. A typical problem in discrepancy specifies two collections \(\mathcal A\) and \(\Sigma\) of a set \(X\) and asks how “balanced” a set \(S\in\Sigma\) can be with respect to the sets in \(\mathcal A\). Given a set \(A\in\mathcal A\), one defines the discrepancy of \(S\) in \(A\) to be the difference between \(|S\cap A|\) and the “expected” size of \(S\cap A\) (where this has some natural meaning that varies from problem to problem), and the discrepancy of \(S\) with respect to \(\mathcal A\) is the maximum of these discrepancies. We then try to minimize this quantity over all \(S\in\Sigma\): this is the discrepancy of \(\Sigma\) with respect to \(\mathcal A\).

This paper takes \(\Sigma\) to be the set of three-dimensional permutation matrices , or rather the subsets \(S\subset\{1,2,\dots,n\}^3\) of which they are the characteristic functions, and \(\mathcal A\) is the set of all Cartesian products \(A=X\times Y\times Z\subset\{1,2,\dots,n\}^3\). In this case, the “expected” size of an intersection \(S\cap A\) is simply \(|S||A|/n^3=|A|/n\), so the aim is to find a good estimate for the minimum over all sets \(S\) that come from permutation matrices of the maximum over all Cartesian products \(A\) of \(\bigl||S\cap A|-|A|/n\bigr|\).

The main conjecture in the paper is that for a random three-dimensional permutation matrix, this discrepancy is \(O(|A|^{1/2})\), with a similar conjecture for higher dimensions. (Note that this a more precise statement than one obtains from the general formulation of discrepancy problems just given, since the bound depends on the size of \(A\), but we could of course fix that size.) This would imply that for a random three-dimensional permutation matrix, the largest that \(|X||Y||Z|\) can be if \(S\cap (X\times Y\times Z)=\emptyset\) is \(O(n^2)\). The authors prove that there exists a three-dimensional permutation matrix with this property, using ideas from Keevash’s breakthrough results about designs.

Besides the main conjecture, several other appealing open problems are given in the paper. One reason they are not straightforward is that it is significantly harder to analyse a random Latin square than it is a random permutation: we do not even have a satisfactory asymptotic estimate for their number when \(n\) is large.

^{_{Image by RainerTypke}}