Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 16 min ago
PreprintCC BY-NC-ND 4.0arXiv

A Tight Erdős-Stone Bound for All Graph Densities

  • Asaf Shapira
  • Raphael Yuster
Open at sourcePDFDOICite

Abstract

The Erdős--Stone Theorem asserts that if a graph has edge density 1−1/r+δ then it contains a complete (r+1)-partite graph with b vertices in each part, where b=bn(r,δ) ≫ 1. The celebrated Chvátal--Szemerédi theorem determined the exact order of bn(r,δ) for every δ< 1/r3. Their bound, however, is not tight when δ=1/r−ε, that is, when the graph has edge density 1−ε for small ε. Our main result in this paper determines the correct order in this remaining regime, thereby enabling us to give a tight bound for the Erdős--Stone problem for all edge densities. More precisely, we prove that for every integer r≥ 2 and 0< δ< 1/r we have bn(r,δ)=Θ((log n)/((1/r−δ)rlog(1/δ))) . The lower bound is obtained using a Kövari-Sós-Turán-type argument combined with a variant of Nikiforov's method of constructing large blow-ups, while the upper bound is proved using a correlated random graph construction, related to tensor powers.

Related

  1. Tight connectivity and shadow densities in generalized Erdős--Rogers problems
    Lulu Dai, Qizhong Lin
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. On Densities in the Erdős-Falconer Distance Problems over the Integers
    Eyvindur Ari Palsson, Jian-An Wang
    arXivPreprintarXiv licenceFull textAlgebra & number theoryAnalysis & PDEsarXiv
  3. Improved Sidorenko bound for hypergraph Turan densities
    Shuyan Chen, Xinmin Hou, Xizhi Liu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem
    Xiangliang Kong, Chong Shangguan, Xin Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The Erdős-Hajnal Property for the six-vertex Graph with Edge Set {ab,bc,cd,de,af,bf,df}
    Viet-Hoang Tran, Tan M. Nguyen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{shapira2026tight,
  title = {{A Tight Erdős-Stone Bound for All Graph Densities}},
  author = {Asaf Shapira and Raphael Yuster},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.01498},
  eprint = {2609.01498},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.01498},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - A Tight Erdős-Stone Bound for All Graph Densities
AU  - Asaf Shapira
AU  - Raphael Yuster
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.01498
UR  - https://arxiv.org/abs/2609.01498
AB  - The Erdős--Stone Theorem asserts that if a graph has edge density 1−1/r+δ then it contains a complete (r+1)-partite graph with b vertices in each part, where b=b_n(r,δ) ≫ 1. The celebrated Chvátal--Szemerédi theorem determined the exact order of b_n(r,δ) for every δ< 1/r^3. Their bound, however, is not tight when δ=1/r−ε, that is, when the graph has edge density 1−ε for small ε. Our main result in this paper determines the correct order in this remaining regime, thereby enabling us to give a tight bound for the Erdős--Stone problem for all edge densities. More precisely, we prove that for every integer r≥ 2 and 0< δ< 1/r we have b_n(r,δ)=Θ((log n)/((1/r−δ)rlog(1/δ))) . The lower bound is obtained using a Kövari-Sós-Turán-type argument combined with a variant of Nikiforov's method of constructing large blow-ups, while the upper bound is proved using a correlated random graph construction, related to tensor powers.
ER  -