Polynomial graph-partition conjecture for bounded-VC2_2 hypergraphs

Assume for simplicity that H\mathcal{H} is tripartite with parts X,Y,ZX,Y,Z, each of size nn. An ε\varepsilon-graph partition consists of partitions

X×Y=E1EM,X×Z=F1FM,Y×Z=G1GM,X\times Y=E_1\sqcup\dots\sqcup E_M,\quad X\times Z=F_1\sqcup\dots\sqcup F_M,\quad Y\times Z=G_1\sqcup\dots\sqcup G_M,

and a function f:[M]3{0,1}f:[M]^3\to\{0,1\} such that for all but εn3\varepsilon n^3 triples (x,y,z)X×Y×Z(x,y,z)\in X\times Y\times Z, if xyEixy\in E_i, xzFjxz\in F_j, and yzGkyz\in G_k, then

xyzE(H)f(i,j,k)=1.xyz\in E(\mathcal{H})\Longleftrightarrow f(i,j,k)=1.

Polynomial graph-partition conjecture. If H\mathcal{H} has bounded VC2_2 dimension, then it has an ε\varepsilon-graph partition with M=poly(1/ε)M=\operatorname{poly}(1/\varepsilon) 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

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.