High-dimensional permutation discrepancy conjecture
High-dimensional permutation discrepancy conjecture
Let be a positive integer. A -dimensional permutation is an array of zeros and ones with exactly one on every line parallel to any coordinate axis. For a box , define its volume and the number of permutation entries it contains by
High-dimensional permutation discrepancy conjecture. For every there exist arbitrarily large -dimensional permutations such that, for every box ,
This is a high-dimensional analogue of the expander mixing lemma and predicts optimal square-root discrepancy for all boxes. The paper gives heuristic motivation but no resolution of the conjecture.
Sources & referencesView supporting material
Primary source
Nathan Linial and Zur Luria, “Discrepancy of High-Dimensional Permutations”, arXiv:1512.04123 (2016).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.