Constant discrepancy conjecture for random regular hypergraphs
Constant discrepancy conjecture for random regular hypergraphs
Let be an integer, and let be a random -regular hypergraph on vertices and edges, where is an absolute constant. Write for the hypergraph discrepancy.
Constant discrepancy conjecture. There is an absolute constant such that, for every integer , a random -regular hypergraph on vertices and edges satisfies
with high probability.
The conjecture concerns the regime where the number of edges is on the order of , where the authors believe a phase transition for constant discrepancy occurs. Existing results establish constant discrepancy in related random-hypergraph models and denser regimes, but the stated random regular case remains open.
Sources & referencesView supporting material
Primary source
Aditya Potukuchi, “A spectral bound on hypergraph discrepancy”, arXiv:1907.04117 (2020).
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.