Erdős problem 582
Does there exist a graph which contains no , and yet any -colouring of the edges produces a monochromatic ?
Sources
FormalConjectures/ErdosProblems/
582.lean
Retained formal statement
Does there exist a graph which contains no , and yet any -colouring of the edges produces a monochromatic ?
Erdős and Hajnal [ErHa67] first asked for the existence of any such graph. Existence was proved by Folkman [Fo70], but with very poor quantitative bounds. (As a result these quantities are often called Folkman numbers.) The current best bounds on the minimal number of vertices of such a graph are , where the lower bound is due to Bikov and Nenov [BiNe20] and the upper bound is due to Lange, Radziszowski, and Xu [LRX14].
True ↔ ∃ V x G, G.CliqueFree 4 ∧ Erdos582.EdgeRamseyTriangle G