Double-tower upper-bound conjecture for regularity of bounded-VC hypergraphs
Double-tower upper-bound conjecture for regularity of bounded-VC hypergraphs
Let be a -graph with bounded VC dimension, and let denote the vertex partition in the upper-bound theorem. Double-tower upper-bound conjecture. The bound in the upper-bound theorem can be improved to
This conjecture asserts that the true regularity behavior for -graphs with bounded VC dimension is closer to a tower than to a double tower. The current results leave this gap 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.