Combinatorics and Discrete Probability Seminar: Notes on two-point concentration of the independence number of the random graph, by Tom Bohman
November 11, 2024
3:00 PM - 3:50 PM
Tom Bohman (Carnegie Mellon University): Notes on two-point concentration of the independence number of the random graph
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.
Please click here to make changes to, or delete, this seminar announcement.
Date posted
Nov 6, 2024
Date updated
Nov 6, 2024
Speakers
