Constant discrepancy conjecture for random regular hypergraphs

Let t>0t>0 be an integer, and let H\mathcal{H} be a random tt-regular hypergraph on nn vertices and KnlognK\frac{n}{\log n} edges, where K>0K>0 is an absolute constant. Write disc(H)\operatorname{disc}(\mathcal{H}) for the hypergraph discrepancy.

Constant discrepancy conjecture. There is an absolute constant K>0K>0 such that, for every integer t>0t>0, a random tt-regular hypergraph H\mathcal{H} on nn vertices and KnlognK\frac{n}{\log n} edges satisfies

disc(H)=O(1)\operatorname{disc}(\mathcal{H})=O(1)

with high probability.

The conjecture concerns the regime where the number of edges is on the order of n/lognn/\log n, 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

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.