Almost-everywhere optimal empty-box conjecture for Latin squares

For a dd-dimensional permutation AA, let T[n]d+1\mathcal T\subseteq[n]^{d+1} be a box and write A(T)A(\mathcal T) for the number of 11-entries of AA in it. An empty box is a box with A(T)=0A(\mathcal T)=0, and let ε(A)\varepsilon(A) be the maximum volume of an empty box. In particular, for an order-nn Latin square, ε(A)\varepsilon(A) is the maximum volume of an empty box in its associated three-dimensional permutation. Almost-everywhere optimal empty-box conjecture. Asymptotically almost every order-nn Latin square AA satisfies

ε(A)=O(n2).\varepsilon(A)=O(n^2).

The conjecture would improve the paper's bound O(n2log2n)O(n^2\log^2 n) for almost every Latin square to the optimal order, matching the universal lower bound ε(A)=Ω(n2)\varepsilon(A)=\Omega(n^2) and the infinitely many examples with ε(A)=O(n2)\varepsilon(A)=O(n^2).

Sources & referencesView supporting material

Primary source

Nathan Linial and Zur Luria, “Discrepancy of High-Dimensional Permutations”, arXiv:1512.04123 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.