Shadows of 3-uniform hypergraphs under a minimum degree condition

DOI10.1137/21M1450227MaRDI QIDQ5043057zbMATH OpenOpenAlexFDO

Authors

Publication date 27 October 2022

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

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

zbMATH Keywords

hypergraphKruskal-Katona theoremRademacher-Turánshadow

Mathematics Subject Classification ID

Triple systems (05B07) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Extremal set theory (05D05)

Abstract: We prove a minimum degree version of the Kruskal--Katona theorem: given $dge1/4$ and a triple system $F$ on $n$ vertices with minimum degree at least $$, we obtain asymptotically tight lower bounds for the size of its shadow. Equivalently, for $tgen/2-1$, we asymptotically determine the minimum size of a graph on $n$ vertices, in which every vertex is contained in at least $$ triangles. This can be viewed as a variant of the Rademacher--Tur'an problem.

Recommendations

• Shadow ratio of hypergraphs with bounded degree
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Matchings in 3-uniform hypergraphs of large minimum vertex degree
• Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
• A note on codegree problems for hypergraphs

Cites work

• \(F\)-factors in hypergraphs via absorption
• \({\ell}\)-degree Turán density
• A degree version of the Hilton-Milner theorem
• A note on Huang-Zhao theorem on intersecting families with large minimum degree
• Co-degree density of hypergraphs
• Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
• Degree versions of theorems on intersecting families via stability
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Extremal graphs with local covering conditions
• scientific article; zbMATH DE number 4039909 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Packing k-partite k-uniform hypergraphs
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs

Cited in

(5)

• Minimum shadows in uniform hypergraphs and a generalization of the Takagi function
• Shadow ratio of hypergraphs with bounded degree
• Many Cliques in Bounded-Degree Hypergraphs
• The degree and codegree threshold for linear triangle covering in 3-graphs
• The degree and codegree threshold for generalized triangle and some trees covering

This page was built for publication: Shadows of 3-uniform hypergraphs under a minimum degree condition

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