Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity

DOI10.1137/22M1541290MaRDI QIDQ6046820zbMATH OpenFDO

Authors Chong Shangguan

Publication date 6 September 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.11338

zbMATH Keywords

sparse hypergraphBrown-Erdős-Sós problemdegenerate Turán density

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Hypergraphs (05C65) Extremal combinatorics (05D99)

Abstract: For fixed integers $rge3,ege3$, and $vger+1$, let $f_r(n,v,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ distinct edges contains at least $v+1$ vertices. In 1973, Brown, ErdH{o}s and S'os proved that $f_r(n,er-(e-1)k,e)=Theta(n^k)$ and conjectured that the limit $li{m}_{nightarrowinfty}frac{f}_3(n,e+2,e)n^2$ always exists for all fixed integers $ege3$. In 2020 Shangguan and Tamo conjectured that the limit $li{m}_{nightarrowinfty}frac{f}_r(n,er-(e-1)k,e)n^k$ always exists for all fixed integers $r>kge2$ and $ege3$, which contains the BES conjecture as a special case for $r=3,k=2$. Recently, based on a result of Glock, Joos, Kim, K"uhn, Lichev, and Pikhurko, Delcourt and Postle proved the BES conjecture. Extending their result, we show that the limit $li{m}_{nightarrowinfty}frac{f}_r(n,er-2(e-1),e)n^2$ always exists, thereby proving the BES conjecture for every uniformity.

Recommendations

• On an extremal hypergraph problem of Brown, Erdős and Sós
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• A new bound for the Brown-Erdős-Sós problem
• Degenerate Turán densities of sparse hypergraphs
• Sparse hypergraphs: new bounds and constructions

Cites work

• scientific article; zbMATH DE number 5130822 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• A new bound for the Brown-Erdős-Sós problem
• An extension of the Ruzsa-Szemerédi theorem
• Degenerate Turán densities of sparse hypergraphs
• Large girth approximate Steiner triple systems
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• On a conjecture of Erdős on locally sparse Steiner triple systems
• On a packing and covering problem
• On an extremal hypergraph problem of Brown, Erdős and Sós
• On the existence of triangulated spheres in 3-graphs, and related problems
• Sparse hypergraphs with applications to coding theory
• Sparse hypergraphs: new bounds and constructions
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Triple systems with no three triples spanning at most five points
• Uniform hypergraphs containing no grids

Cited in

(6)

• On the \((6,4)\)-problem of Brown, Erdős, and Sós
• The limit in the $(k+2, k)$-Problem of Brown, Erd\H{o}s and S\'os exists for all $k\geq 2$
• On an extremal hypergraph problem of Brown, Erdős and Sós
• Sparse hypergraphs: new bounds and constructions
• A Ramsey variant of the Brown-Erdős-Sós conjecture
• Degenerate Turán densities of sparse hypergraphs

This page was built for publication: Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046820)