Two-point concentration for graph classes admitting sparse vertex deletion

Abstract

For fixed $p\in(0,1)$, we prove that the maximum number of vertices in an induced subgraph of $G(n,p)$ from a given class is concentrated on two consecutive integers, unifying and extending several earlier results. We require that the class contain arbitrarily large graphs and that every sufficiently large $k$-vertex member have a vertex of degree $o(k)$ whose deletion leaves a graph in the same class. This condition holds for empty graphs, trees, forests, planar graphs, graphs of bounded maximum degree, degeneracy or treewidth, graphs excluding a fixed complete bipartite subgraph (including graphs containing no cycle of length four), and many other graph classes.