ACO The ACO Seminar (2022–2023)

September 15, 3:30pm, Wean 8220
Jakob Hofstad, Carnegie Mellon University
Two Point Concentration of the Independence Number for Sparse Random Graphs


It is well known that, for any constant probability p, there exists a function k(n) such that the independence number of the Erdös-Rényi random graph G(n,p) is concentrated on two values; i.e., the independence number equals k(n) or k(n)+1 with high probability (that is, with probability converging to 1 as n approaches infinity). This result was proved independently by Erdös and Bollobás and by Matula in the 1970's by using standard first and second moment techniques. However, very little attention has been devoted to extending this result to probabilities p that converge to 0 with increasing n. Indeed, the original argument can be used to prove the same result for p = n^c for any constant c > -1/3, though this statement does not seem to appear in any of the literature. In this talk, we will show that the independence number of G(n,p) is still concentrated on two values for p = n^c where c > -2/3 by using a more general random variable, then we give an argument due to Say and Sawhney for why this behavior cannot persist for c ≤ -2/3. This is joint work with Tom Bohman.

Back to the ACO home page Back to the ACO Seminar schedule