Multicolour Erdős--Hajnal Conjecture

Importance: High ✭✭✭
Keywords: ramsey theory
Recomm. for undergrads: no
Posted by: Jon Noel
on: October 10th, 2019
Conjecture   For every fixed $ k\geq2 $ and fixed colouring $ \chi $ of $ E(K_k) $ with $ m $ colours, there exists $ \varepsilon>0 $ such that every colouring of the edges of $ K_n $ contains either $ k $ vertices whose edges are coloured according to $ \chi $ or $ n^\varepsilon $ vertices whose edges are coloured with at most $ m-1 $ colours.

See [FGP].

Bibliography

[FGP] Jacob Fox, Andrey Grinshpun and János Pach: The Erdős–Hajnal conjecture for rainbow triangles, J. Combin. Theory, Series B. 111 (2016), 75--125.


* indicates original appearance(s) of problem.