The Chromatic Number of Random Graphs

Explore the fascinating world of graph theory and random graphs in this 46-minute lecture by Annika Heckel at BIMSA. Dive into the concept of chromatic number, a fundamental graph parameter used to determine the minimum number of colors needed to color vertices in a graph without adjacent vertices sharing the same color. Examine the study of random graphs, particularly the G(n,p) model, and its significance in graph theory. Learn about the groundbreaking work of Shamir and Spencer in bounding chromatic number fluctuations, and the long-standing question posed by Bollobás and Erdős regarding lower bounds. Discover Heckel's recent breakthrough in establishing a lower bound for the chromatic number of G(n,1/2) that nearly matches the classic upper bound. Explore the sharpened results and their implications, as well as a surprising conjecture on the exact limiting distribution of the chromatic number. Gain insights from three different papers, including collaborative work with Oliver Riordan and Konstantinos Panagiotou, as you delve into this cutting-edge research in graph theory and random graphs.

Annika Heckel: The chromatic number of random graphs #ICBS2024