Discrepancy of High-Dimensional Permutations

2015/12/13 by Linial, Nathan, Luria, Zur · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1512.04123

Abstract

Let L be an order-n Latin square. For X, Y, Z ⊆ \1, ... ,n\, let L(X, Y. Z) be the number of triples i∈ X, j∈ Y, k∈ Z such that L(i,j) = k. We conjecture that asymptotically almost every Latin square satisfies |L(X, Y, Z) - \frac 1n |X||Y||Z||≤ O(√(|X||Y||Z|)) for every X, Y and Z. Let ε(L):= max |X||Y||Z| when L(X, Y, Z)=0. The above conjecture implies that ε(L) ≤ O(n²) holds asymptotically almost surely (this bound is obviously tight). We show that there exist Latin squares with ε(L) ≤ O(n²), and that ε(L) ≤ O(n² log² n) for almost every order-n Latin square. On the other hand, we recall that ε(L)≥ Ω(n^33/14) if L is the multiplication table of an order-n group. Some of these results extend to higher dimensions. Many open problems remain.

Cited by

• Three-dimensional symmetric designs of propriety 3
• Parities in random Latin squares

Related

• Intercalates and Discrepancy in Random Latin Squares
• Substructures in Latin squares
• Large deviations in random Latin squares
• Packing of permutations into Latin squares
• Square-root cancellation for the signs of Latin squares