Mathematical Sciences Seminar - Colouring dense random graphs
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
A (proper) colouring of a graph is a vertex colouring where no two neighbouring vertices are coloured the same. The chromatic number is the least number of colours where this is possible. We study the chromatic number of G(n,p), the random graph with n vertices where each edge is included independently with probability p. Determining the chromatic number of G(n,p) is one of the classic challenges in random graph theory. For the case where p is constant, we will establish upper and lower bounds which are the first to match each other up to a term of size o(1) in the denominator. In particular, these bounds determine the average colour class size in an optimal colouring almost completely, answering a question by Kang and McDiarmid. We also consider a closely related graph parameter - the equitable chromatic number of the dense random graph G(n,m) - which can be determined exactly on a subsequence of the integers.
Contact name:
Department of Economics, Mathematics and Statistics