The feasible region of hypergraphs

DOI10.1016/J.JCTB.2020.12.004MaRDI QIDQ1998756zbMATH OpenOpenAlexFDO

Authors Xizhi Liu, Dhruv Mubayi

Publication date 8 March 2021

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

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

zbMATH Keywords

shadowstabilityLagrangianhypergraph Turán problems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hypergraphs (05C65)

Abstract: Let $mathcalF$ be a family of $r$-uniform hypergraphs. The feasible region $Omega(mathcalF)$ of $mathcalF$ is the set of points $(x,y)$ in the unit square such that there exists a sequence of $mathcalF$-free $r$-uniform hypergraphs whose edge density approaches $x$ and whose shadow density approaches $y$. The feasible region provides a lot of combinatorial information, for example, the supremum of $y$ over all $(x,y)inOmega(mathcalF)$ is the Tur'{a}n density $pi(mathcalF)$, and $Omega(emptyset)$ gives the Kruskal-Katona theorem. We undertake a systematic study of $Omega(mathcalF)$, and prove that $Omega(mathcalF)$ is completely determined by a left-continuous almost everywhere differentiable function; and moreover, there exists an $mathcalF$ for which this function is not continuous. We also extend some old related theorems. For example, we generalize a result of Fisher and Ryan to hypergraphs and extend a classical result of Bollob'as by almost completely determining the feasible region for cancellative triple systems.

Recommendations

• The feasible region of induced graphs
• On the boundary of the region defined by homomorphism densities
• Constructions of non-principal families in extremal hypergraph theory
• The Turán problem for hypergraphs on fixed size
• Stability theorems for some Kruskal-Katona type results

Cites work

• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3722700 (Why is no real title available?)
• scientific article; zbMATH DE number 3508542 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 2171466 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A hypergraph extension of Turán's theorem
• An exact Turán result for the generalized triangle
• Bounds on the number of complete subgraphs
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• Flag algebras
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Large networks and graph limits
• On generalized graphs
• On the Minimal Density of Triangles in Graphs
• On the boundary of the region defined by homomorphism densities
• Stability theorems for cancellative hypergraphs
• The clique density theorem
• The early history of block designs
• The number of cliques in graphs of given order and size
• Three-graphs without two triples whose symmetric difference is contained in a third

Cited in

(6)

• Stability theorems for some Kruskal-Katona type results
• A 2-stable family of triple systems
• The feasible region of induced graphs
• A unified approach to hypergraph stability
• A hypergraph Turán problem with no stability
• On the boundary of the region defined by homomorphism densities

This page was built for publication: The feasible region of hypergraphs

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