Unavoidable hypergraphs

DOI10.1016/J.JCTB.2021.06.010MaRDI QIDQ1984522zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 16 September 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

hypergraph Turan numberssunflowersunavoidable hypergraphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Abstract: The following very natural problem was raised by Chung and ErdH{o}s in the early 80's and has since been repeated a number of times. What is the minimum of the Tur'an number $extex(n,mathcalH)$ among all $r$-graphs $mathcalH$ with a fixed number of edges? Their actual focus was on an equivalent and perhaps even more natural question which asks what is the largest size of an $r$-graph that can not be avoided in any $r$-graph on $n$ vertices and $e$ edges? In the original paper they resolve this question asymptotically for graphs, for most of the range of $e$. In a follow-up work Chung and ErdH{o}s resolve the $3$-uniform case and raise the $4$-uniform case as the natural next step. In this paper we make first progress on this problem in over 40 years by asymptotically resolving the $4$-uniform case which gives us some indication on how the answer should behave in general.

Recommendations

• On unavoidable hypergraphs
• Universal and unavoidable graphs
• The maximum size of hypergraphs without generalized 4-cycles
• Saturated r-uniform hypergraphs
• On Ramsey - Turan type theorems for hypergraphs

Cites work

• A Partition Property of Simplices in Euclidean Space
• An extremal problem for 3-graphs
• Bounds on pairs of families with restricted intersections
• Coding for Sunflowers
• Every large set of equidistant (0,+1,-1)-vectors forms a sunflower
• Exact solution of some Turán-type problems
• Extremal numbers for odd cycles
• Forbidden Intersections
• Forbidden vector-valued intersections
• Forbidding just one intersection
• Frankl-Rödl-type theorems for codes and permutations
• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3166040 (Why is no real title available?)
• scientific article; zbMATH DE number 4200236 (Why is no real title available?)
• scientific article; zbMATH DE number 3691331 (Why is no real title available?)
• scientific article; zbMATH DE number 3561362 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Improved bounds for Erdős' matching conjecture
• Improved bounds for the sunflower lemma
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection Theorems for Systems of Sets
• Intersection theorems with geometric consequences
• Note on sunflowers
• On a problem of K. Zarankiewicz
• On a theorem of Rademacher-Turán
• On finite set-systems whose every intersection is a kernel of a star
• On the maximum number of edges in a hypergraph with given matching number
• On unavoidable graphs
• On unavoidable hypergraphs
• Open problems of Paul Erd�s in graph theory
• Proof of the Erdős matching conjecture in a new range
• Recent developments in extremal combinatorics: Ramsey and Turán type problems
• The Erdős matching conjecture and concentration inequalities
• The history of degenerate (bipartite) extremal graph problems
• The maximum number of edges in a 3-graph not containing a given star
• The Turán number of sparse spanning graphs
• Unavoidable stars in 3-graphs
• Universal and unavoidable graphs
• What we know and what we do not know about Turán numbers

Cited in

(6)

• Turán numbers of sunflowers
• On unavoidable hypergraphs
• Universal and unavoidable graphs
• On unavoidable graphs
• Absolutely avoidable order-size pairs in hypergraphs
• Linear dependencies, polynomial factors in the Duke-Erdős forbidden sunflower problem

This page was built for publication: Unavoidable hypergraphs

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