Polynomial Erdős–Hajnal-type dependence for tripartite 3-graphs
Polynomial Erdős–Hajnal-type dependence for tripartite 3-graphs
Let be a tripartite -graph one of whose parts is a singleton. For every , there exists such that, whenever is a -partite -graph on parts , each of size , containing no tripartitely induced copy of , there are subsets with and . Polynomial-dependence conjecture. The parameter may be chosen so that . The proposition currently yields only the lower bound ; the conjecture asks for polynomial dependence on .
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
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.