Skip to content
DraconiticResearch
Search Sources API
186,631 studies31 sourcesUpdated 37 min ago
PreprintCC BY 4.0arXiv

The extremal cases of the Erd\H os--Sós conjecture

  • Bruce Reed
  • Maya Stein
Open at sourcePDFDOICite

Abstract

The Erd\H os--Sós conjecture states that every n-vertex graph G with more than (k−2)n/2 edges contains every k-vertex tree. We solve the extremal cases of this conjecture, showing that for some fixed μ>0, the conjecture holds for each G that minimally satisfies the assumptions of the conjecture and has a subgraph~H of minimum degree δ(H)≥ (1−μ)k. In our proof, we mainly have to deal with H taking two different shapes: either H is close to the complete graph Kk or H is close to the complete bipartite graph Kk,k.

Related

  1. Complete centroaffine extremal hypersurfaces and centroaffine Bernstein conjecture
    Cheng Xing, Yalin Sun, Ruiwei Xu
    arXivPreprintarXiv licenceFull textAnalysis & PDEsGeometry & topologyarXiv
  2. On extremal problems related to the Krzyż conjecture
    Sarah May Instanes, Adrián Llinares, Dragan Vukotić
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  3. An Extremal Formula for Elliptical Width and the Bourin--Lee Conjecture
    Mohammad Sababheh
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. Equality Cases in the Tu-Deng Conjecture Bound
    Thomas W. Cusick
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. The Ternary and Quaternary Cases of the {2,4}-Distance Code Conjecture
    Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{reed2026extremal,
  title = {{The extremal cases of the Erd\H os--Sós conjecture}},
  author = {Bruce Reed and Maya Stein},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.05411},
  eprint = {2609.05411},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.05411},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The extremal cases of the Erd\H os--Sós conjecture
AU  - Bruce Reed
AU  - Maya Stein
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.05411
UR  - https://arxiv.org/abs/2609.05411
AB  - The Erd\H os--Sós conjecture states that every n-vertex graph G with more than (k−2)n/2 edges contains every k-vertex tree. We solve the extremal cases of this conjecture, showing that for some fixed μ>0, the conjecture holds for each G that minimally satisfies the assumptions of the conjecture and has a subgraph~H of minimum degree δ(H)≥ (1−μ)k. In our proof, we mainly have to deal with H taking two different shapes: either H is close to the complete graph K_k or H is close to the complete bipartite graph K_k,k.
ER  -