OpenAlex ·

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

Ting-Wei Chao, Xinqi Huang and Hong Liu

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2609.38115
Original
Read it at the publisher
Topics
CombinatoricsNumber Theory

Abstract

The Brown--Erdős--Sós problem is a fundamental problem in sparse hypergraph Turán theory. For integers $r,k\ge 2$ and $s\ge 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)}\bigl(n;(r-t)k+t,k\bigr)=Θ(n^t)$ for all $r>t\ge 2$ and $k\ge 2$. However, the existence and the value of the leading coefficient have remained largely open. We determine the coefficient $π(r,t,k):=\lim_{n\to\infty}n^{-t}f^{(r)}\bigl(n;(r-t)k+t,k\bigr)$ for every such $r,t,k$, except when $(r,t)=(3,2)$ and $k\ge 4$ is even. In particular, \[ π(r,t,k) = \begin{cases} \frac{2}{t!\bigl(2\binom{r}{t}-1\bigr)}, & \text{if $k$ is odd},\\ \frac{1}{t!\binom{r}{t}}, & \text{if $k$ is even and $r\ge4$}. \end{cases} \] Surprisingly, for $r\ge4$, 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\ge 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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Combinatorics

Get the few papers worth your time in Combinatorics every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics