Polynomial graph-partition conjecture for bounded-VC hypergraphs
Polynomial graph-partition conjecture for bounded-VC hypergraphs
Assume for simplicity that is tripartite with parts , each of size . An -graph partition consists of partitions
and a function such that for all but triples , if , , and , then
Polynomial graph-partition conjecture. If has bounded VC dimension, then it has an -graph partition with many graphs. This would sharpen the tower-type bound currently obtained for such graph partitions; polynomial bounds remain open.
Sources & referencesView supporting material
Primary source
Lior Gishboliner, Asaf Shapira and Yuval Wigderson, “Regularity for hypergraphs with bounded VC_2 dimension”, arXiv:2508.09969 (2025).
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.