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.
We also discuss some related questions.
Joint work with Jacob Fox, Choongbum Lee and Benny Sudakov.
Seminar series
Date
Tue, 29 Apr 2014
Time
14:30 -
15:30
Location
L3
Speaker
David Conlon
Organisation
University of Oxforord