Polynomial dependence in the weak regularity-to-homogeneity proposition
Polynomial dependence in the weak regularity-to-homogeneity proposition
For every and , there exists such that every -partite -graph of slicewise VC-dimension at most that is weakly -regular satisfies . Polynomial-dependence conjecture. The parameter may be chosen so that . The preceding result gives only single-exponential dependence on ; the conjecture asks for a polynomial bound under bounded slicewise VC-dimension.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Lior Gishboliner, Asaf Shapira and Yuval Wigderson, “Is it easy to regularize a hypergraph with easy links?”, arXiv:2506.15582 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.