The feasible region of hypergraphs

DOI10.1016/J.JCTB.2020.12.004zbMATH Open1459.05226arXiv1911.02090OpenAlexW3117795563MaRDI QIDQ1998756FDOQ1998756

Authors: Xizhi Liu, Dhruv Mubayi 

Publication date: 8 March 2021

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

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.

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

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

zbMATH Keywords

shadowstabilityLagrangian[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=hypergraph+Tur%EF%BF%BD%EF%BF%BDn+problems&go=Go hypergraph Tur��n problems]

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Flag algebras
• Title not available (Why is that?)
• A hypergraph extension of Turán's theorem
• Title not available (Why is that?)
• The number of cliques in graphs of given order and size
• Title not available (Why is that?)
• On generalized graphs
• The clique density theorem
• On the Minimal Density of Triangles in Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• Three-graphs without two triples whose symmetric difference is contained in a third
• Stability theorems for cancellative hypergraphs
• An exact Turán result for the generalized triangle
• Bounds on the number of complete subgraphs
• The early history of block designs
• On the boundary of the region defined by homomorphism densities

Cited In (5)

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

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)