Subpolynomial growth conjecture for even-edge cliques

Let KpK_p be the complete graph on pp vertices, and let f(n,H)f(n,H) be the smallest number of colors in an edge coloring of KnK_n in which every copy of HH intersects at least one color class in an odd number of edges. Subpolynomial clique-growth conjecture. For any positive integer p4p\geq 4 with p0,1(mod4)p\equiv 0,1\pmod{4}, one has

f(n,Kp)=no(1).f(n,K_p)=n^{o(1)}.

The conjecture extends the stated general upper bound, whose polynomial exponent tends to zero as pp increases, and concerns the variant of the Erdős–Gyárfás problem for cliques with an even number of edges. The supplied source does not indicate whether it has been resolved.

Sources & referencesView supporting material

Primary source

Gennian Ge, Zixiang Xu and Yixuan Zhang, “A new variant of the Erdős-Gyárfás problem on K_5”, arXiv:2306.14682 (2023).

Additional references

2 papers in this index state this conjecture (2016–2023). The statement above is taken from the most recent of them; the others are arXiv:1605.00131.

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.