University of Cambridge > > Combinatorics Seminar > The (non-)concentration of the chromatic number

The (non-)concentration of the chromatic number

Add to your list(s) Download to your calendar using vCal

  • UserOliver Riordan (University of Oxford)
  • ClockThursday 31 October 2019, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason.

Let $G(n,1/2)$ be the random graph on $n$ vertices in which each edge is present with probability $1/2$, independently of the others. A classical question is: what is the chromatic number $X_n$ of $G(n,1/2)$, i.e., how many colours do we need to colour all vertices so that adjacent vertices receive different colours? Of course, $X_n$ is a random variable: one main thrust of past work is proving better and better upper and lower bounds that hold with high probability (probability tending to 1), starting with the asymptotic formula proved by Bollob\’as in the 1980s. A separate direction asked: even if we can’t pin down the value of $X_n$ precisely, can we bound how much it varies? A nowadays standard argument gives an upper bound of $O(n{1/2})$. Surprisingly, until very recently \emph{no} meaningful lower bounds were known, although this natural question was raised by Bollob\’as many years ago. Recently, Annika Heckel made a breakthrough, establishing a lower bound of $n{1/4-o(1)}$. She and I have now extended this to $n{1/2-o(1)}$, almost matching the upper bound.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity