Sparse hypergraphs: new bounds and constructions

DOI10.1016/J.JCTB.2020.10.003MaRDI QIDQ2222044zbMATH OpenOpenAlexFDO

Authors Gennian Ge, Chong Shangguan

Publication date 3 February 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

hypergraph rainbow cycleshypergraph removal lemmahypergraph Turán problemsolution-free setsparse hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65)

Abstract: Let $f_r(n,v,e)$ denote the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices, in which the union of any $e$ distinct edges contains at least $v+1$ vertices. The study of $f_r(n,v,e)$ was initiated by Brown, Erd{H{o}}s and S{'o}s more than forty years ago. In the literature, the following conjecture is well known. Conjecture: $n^{k-o(1)}<f_r(n,er-(e-1)k+1,e)=o(n^k)$ holds for all fixed integers $r>kge2$ and $ege3$ as $nightarrowinfty$. For $r=3,e=3,k=2$, the bound $n^{2-o(1)}<f_3(n,6,3)=o(n^2)$ was proved by the celebrated (6,3)-theorem of Ruzsa and Szemer{'e}di. In this paper, we add more evidence for the validity of the conjecture. On one hand, using the hypergraph removal lemma we show that the upper bound part of the conjecture is true for all fixed integers $rgek+1geege3$. On the other hand, using tools from additive number theory we present several constructions showing that the lower bound part of the conjecture is true for $rge3$, $k=2$ and $e=4,5,7,8$. Prior to our results, all known constructions that match the conjectured lower bound satisfy either $r=3$ or $e=3$. Our constructions are the first ones in the literature that break this barrier.

Recommendations

• Sparse hypergraphs with applications to coding theory
• Degenerate Turán densities of sparse hypergraphs
• On an extremal hypergraph problem of Brown, Erdős and Sós
• Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós

Cites work

• An extension of the Ruzsa-Szemerédi theorem
• Combinatorial batch codes
• Counting subgraphs in quasi‐random 4‐uniform hypergraphs
• Degenerate Turán densities of sparse hypergraphs
• Extremal problems on set systems
• Graph removal lemmas
• scientific article; zbMATH DE number 5130822 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (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?)
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On a packing and covering problem
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• On an extremal hypergraph problem of Brown, Erdős and Sós
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On subsets of \(\mathbb F_q^n\) containing no \(k\)-term progressions
• Parent-identifying codes
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Regularity Lemma for k-uniform hypergraphs
• Regularity properties for triple systems
• Separating hash families: a Johnson-type bound and new constructions
• Small cores in 3-uniform hypergraphs
• Solving a linear equation in a set of integers I
• Sparse hypergraphs with applications to coding theory
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The counting lemma for regular k‐uniform hypergraphs
• Triple systems with no three triples spanning at most five points
• Uniform hypergraphs containing no grids

Cited in

(15)

• Sparse hypergraphs with low independence number
• A new bound for the Brown-Erdős-Sós problem
• Degenerate Turán densities of sparse hypergraphs
• L_p regular sparse hypergraphs
• A counting lemma for sparse pseudorandom hypergraphs
• scientific article; zbMATH DE number 1303555 (Why is no real title available?)
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Sparse halves in dense triangle-free graphs
• Sparse 0−1 Matrices and Forbidden Hypergraphs
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs
• Sparse hypergraphs with applications to coding theory
• Constructing dense grid-free linear 3-graphs
• An extension of the Ruzsa-Szemerédi theorem
• Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity
• Separating hash families with large universe

This page was built for publication: Sparse hypergraphs: new bounds and constructions

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