{"id":"arxiv/2611.00437","url":"https://arxiv.org/abs/2611.00437","tags":["math.CO","math.PR"],"score":0,"title":"Two-point concentration for graph classes admitting sparse vertex deletion","domain":"math.CO","source":"arxiv","authors":["Margarita Akhmejanova","Vladislav Kozhevnikov"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}