Conlon, Fox, Lee and Sudakov's Erdős–Gyárfás function conjecture

Let fr(n,p,q)f_r(n,p,q) denote the least number of colours in an rr-uniform colouring of the complete hypergraph on nn vertices with no induced copy of a pp-vertex hypergraph using at most q1q-1 colours. For positive integers pp and rr satisfying 2r<p2\leq r<p, Conlon, Fox, Lee and Sudakov's conjecture.

fr(n,p,(p1r1))=no(1).f_r\left(n,p,\binom{p-1}{r-1}\right)=n^{o(1)}.

This conjecture extends the Erdős–Gyárfás problem from graphs to general uniformity. The surrounding results establish subpolynomial bounds for the cases r=2r=2 and (r,p)=(3,4)(r,p)=(3,4), while polynomial lower bounds are known when the third parameter is increased to (p1r1)+1\binom{p-1}{r-1}+1; the general assertion remains open.

Sources & referencesView supporting material

Primary source

Barnabás Janzer and Oliver Janzer, “On locally rainbow colourings”, arXiv:2304.12260 (2023).

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.