On the Erdos-Gyarfas problem in generalised Ramsey theory

29 April 2014
David Conlon
<p>Fix positive integers p and q with 2 \leq q \leq {p \choose 2}. An edge-colouring of the complete graph K_n is said to be a (p, q)-colouring if every K_p receives at least q different colours. The function f(n, p, q) is the minimum number of colours that are needed for K_n to have a (p,q)-colouring. This function was introduced by Erdos and Shelah about 40 years ago, but Erdos and Gyarfas 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. <br /> <br />We also discuss some related questions. <br /> <br />Joint work with Jacob Fox, Choongbum Lee and Benny Sudakov. </p>
  • Combinatorial Theory Seminar