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

DOI10.1137/22M1541290zbMATH Open1520.05058arXiv2210.11338MaRDI QIDQ6046820FDOQ6046820

Authors: Chong Shangguan 

Publication date: 6 September 2023

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

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.

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

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

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)

Cites Work

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

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
• A Ramsey variant of the Brown-Erdős-Sós conjecture
• Sparse hypergraphs: new bounds and constructions
• 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)