Combinatorics and Discrete Probability Seminar
Tom Bohman
Carnegie Mellon University
Notes on two-point concentration of the independence number of the random graph
Abstract: It is well known that for any constant
probability p there exists a function k(n) such that the independence number of the binomial random graph G(n,p) is concentrated on two values (i.e.the independence number of G(n,p) is k(n) or
k(n)+1 with high probability). In this
talk we discuss the extension of this
result to p(n) that tends to 0 with n. In particular, we determine the probability at which two point concentration of the independence number of G(n,p) breaks down. We also discuss the independence number of G(n,m), and show that there is a range of values for m in which the independence number of G(n,m) is concentrated on two values while the independence number of the corresponding
G(n,p) is not concentrated on two values.
Joint work with Jakob Hofstad.
Monday November 11, 2024 at 3:00 PM in 1227 SEO