ACO The ACO Seminar (2014–2015)

Apr. 20, 4:30pm, Porter Hall 226A   (Note unusual day, time, and location)
David Conlon, University of Oxford
On the Erdős–Gyárfás problem in generalised Ramsey theory


Fix positive integers p and q with 2q ≤ binom(p,2). An edge-colouring of the complete graph Kn is said to be a (p, q)-colouring if every Kp receives at least q different colours. The function f(n, p, q) is the minimum number of colours that are needed for Kn to have a (p,q)-colouring. This function was introduced by Erdős and Shelah about 40 years ago, but Erdős and Gyárfás were the first to study the function in a systematic way. They proved that f(n, p, p) is polynomial in n and asked to determine the maximum q, depending on p, for which f(n,p,q) is subpolynomial in n. We prove that the answer is p-1.

We also discuss some related questions.

Joint work with Jacob Fox, Choongbum Lee and Benny Sudakov.

Back to the ACO home page