Two-point concentration for graph classes admitting sparse vertex deletion
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.00437
curl -X POST /api/v1/records/arxiv/2611.00437/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.00437/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'