Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 52 min ago
PreprintarXiv licencearXiv

Two-point concentration for graph classes admitting sparse vertex deletion

  • Margarita Akhmejanova
  • Vladislav Kozhevnikov
Open at sourcePDFDOICite

Abstract

For fixed p∈(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.

Related

  1. Non-isomorphic graphs have distinct vertex-Ramsey classes
    Maria Axenovich, Patrick Schmitteckert
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Local energy and vertex deletion for Aα-matrices
    Ravinder Kumar, Piyush Sharma
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. DP vertex-arboricity of sparse graphs
    Peter Bradshaw, Alexandr Kostochka, Zimu Xiang
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Concentration of bounded sparse chaoses and sparse Khatri-Rao embeddings
    Guozheng Dai, Yiyun He, Ke Wang +1
    arXivPreprintarXiv licenceFull textProbabilityStatisticsarXiv
  5. Sharp spectral norm concentration and regularization of sparse random tensors
    Zhixin Zhou, Yizhe Zhu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{akhmejanova2026twopoint,
  title = {{Two-point concentration for graph classes admitting sparse vertex deletion}},
  author = {Margarita Akhmejanova and Vladislav Kozhevnikov},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.00437},
  eprint = {2611.00437},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.00437},
}
RIS
TY  - UNPB
TI  - Two-point concentration for graph classes admitting sparse vertex deletion
AU  - Margarita Akhmejanova
AU  - Vladislav Kozhevnikov
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.00437
UR  - https://arxiv.org/abs/2611.00437
AB  - For fixed p∈(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.
ER  -