CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar
David Conlon
University of Oxford
Title: On the Erdös–Gyárfás problem in generalised Ramsey theory

Abstract:

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.

Date: Monday, April 20, 2015
Time: 4:30 pm
Location: Porter Hall 226A
Note: Note unusual day, time, and location