Polynomial Erdős–Hajnal-type dependence for tripartite 3-graphs

Let H0H_0 be a tripartite 33-graph one of whose parts is a singleton. For every ε>0\varepsilon>0, there exists δ>0\delta>0 such that, whenever HH is a 33-partite 33-graph on parts V1V2V3V_1\cup V_2\cup V_3, each of size nn, containing no tripartitely induced copy of H0H_0, there are subsets ViViV_i'\subseteq V_i with Viδn|V_i'|\geq\delta n and d(V1,V2,V3)[0,ε][1ε,1]d(V_1',V_2',V_3')\in[0,\varepsilon]\cup[1-\varepsilon,1]. Polynomial-dependence conjecture. The parameter δ\delta may be chosen so that δ=εO(1)\delta=\varepsilon^{O(1)}. The proposition currently yields only the lower bound δ2poly(1/ε)\delta\geq 2^{-\operatorname{poly}(1/\varepsilon)}; the conjecture asks for polynomial dependence on ε\varepsilon.

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).

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.