Speaker: Tom Bohman (Carnegie Mellon University)

Title: Two point concentration of the domination number of the random graph

Abstract:  

We show that the domination number of the binomial random graph G_{n,p} with edge probability p =n^{-\gamma} is concentrated on two values for \gamma < 2/3 and not concentrated on two values for \gamma > 2/3.

The main ingredient in the proof is a Poisson type approximation for the probability that a random bipartite graph has no isolated vertices in a regime where standard tools are not available.

Joint work with Lutz Warnke and Emily Zhu.