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

Asymptotics of the Brown--Erdős--Sós problem at integer exponents

  • Ting-Wei Chao
  • Xinqi Huang
  • Hong Liu
Open at sourcePDFDOICite

Abstract

The Brown--Erdős--Sós problem is a fundamental problem in sparse hypergraph Turán theory. For integers r,k≥ 2 and s≥ r, the problem asks for the maximum number f(r)(n;s,k) of edges in an n-vertex r-uniform hypergraph containing no k distinct edges spanning at most s vertices. In 1971, Brown, Erdős, and Sós proved that f(r)(n;(r−t)k+t,k)=Θ(nt) for all r>t≥ 2 and k≥ 2. However, the existence and the value of the leading coefficient have remained largely open. We determine the coefficient π(r,t,k):=limn→∞n−tf(r)(n;(r−t)k+t,k) for every such r,t,k, except when (r,t)=(3,2) and k≥ 4 is even. In particular, π(r,t,k) = 2/(t!(2binomrt−1)), & if $k$ is odd, 1/t!binomrt, & if $k$ is even and $r≥4$. Surprisingly, for r≥4, the limit π(r,t,k) depends on k only through its parity, not its value. For the remaining case, we prove that π(3,2,k)>1/6 for all even k≥ 4, showing that the natural packing construction is never asymptotically optimal. As an application, we extend a connection of Bennett, Cushman, and Dudek to arbitrary uniformity to resolve several cases of the Erdős--Gyárfás--Shelah generalized Ramsey problem.

Related

  1. 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
  2. The quadratic Brown--Erdős--Sós problem for 3-uniform hypergraphs with 8 and 9 edges
    Levente Bodnár, Oleg Pikhurko, Shumin Sun +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. An Approximate Version of Vu's Theorem on Economical Subbases For Non-Integer Exponents
    Ataleshvara Bhargava
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. On the asymptotics of the Erdős-Rogers function
    Domagoj Bradač, Oliver Janzer, Rik Sarkar
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Estimating the asymptotics of integer partitions in intermediate dimensions (d = 3,4,5,6)
    Avinandan Mondal
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsMathematical physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chao2026asymptotics,
  title = {{Asymptotics of the Brown--Erdős--Sós problem at integer exponents}},
  author = {Ting-Wei Chao and Xinqi Huang and Hong Liu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38115},
  eprint = {2609.38115},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38115},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - Asymptotics of the Brown--Erdős--Sós problem at integer exponents
AU  - Ting-Wei Chao
AU  - Xinqi Huang
AU  - Hong Liu
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.38115
UR  - https://arxiv.org/abs/2609.38115
AB  - The Brown--Erdős--Sós problem is a fundamental problem in sparse hypergraph Turán theory. For integers r,k≥ 2 and s≥ r, the problem asks for the maximum number f^(r)(n;s,k) of edges in an n-vertex r-uniform hypergraph containing no k distinct edges spanning at most s vertices. In 1971, Brown, Erdős, and Sós proved that f^(r)(n;(r−t)k+t,k)=Θ(n^t) for all r>t≥ 2 and k≥ 2. However, the existence and the value of the leading coefficient have remained largely open. We determine the coefficient π(r,t,k):=lim_n→∞n^−tf^(r)(n;(r−t)k+t,k) for every such r,t,k, except when (r,t)=(3,2) and k≥ 4 is even. In particular, π(r,t,k) = 2/(t!(2binomrt−1)), & if $k$ is odd, 1/t!binomrt, & if $k$ is even and $r≥4$. Surprisingly, for r≥4, the limit π(r,t,k) depends on k only through its parity, not its value. For the remaining case, we prove that π(3,2,k)>1/6 for all even k≥ 4, showing that the natural packing construction is never asymptotically optimal. As an application, we extend a connection of Bennett, Cushman, and Dudek to arbitrary uniformity to resolve several cases of the Erdős--Gyárfás--Shelah generalized Ramsey problem.
ER  -