Two values for the chromatic number of a random graph G(n,d/n)

Combinatorics, Probability and Statistics 1 Minute

You need to know: Graph, vertices, edges, chromatic number of a graph, limits, basic probability theory, independent events.

Background: Let G(n,p) denote random graph with n vertices, such that every possible edge is included independently with probability p. For a fixed d>0, consider sequence of random graphs G\left(n,\frac{d}{n}\right) with n\to\infty.

The Theorem: On 9th October 2003, Dimitris Achlioptas and Assaf Naor submitted to the Annals of Mathematics a paper in which they proved that, with probability that tends to 1 as n\to\infty, the chromatic number of G\left(n,\frac{d}{n}\right) is either k_d or k_d+1, where k_d denotes the smallest integer k such that d<2k\log k.

Short context: Chromatic number is one of the most important and well-studied invariants of a graph, and it is natural to ask what it is equal to for random graphs. In 1991, Luczak proved that for every d>0 there exists a constant k_d, such that, with probability that tends to 1 as n\to\infty, the chromatic number of G\left(n,\frac{d}{n}\right) is either k_d or k_d+1. However, the exact value of k_d remained unknown. The Theorem answers this question.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 5.11 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

One thought on “Two values for the chromatic number of a random graph G(n,d/n)”

  1. Pingback: For c<1/4, the chromatic number of G(n,1/2) is not concentrated on n^c consecutive values – Theorems of the 21st century

Leave a comment