The structure of large intersecting families

DOI10.1090/PROC/13390zbMATH Open1358.05039arXiv1602.01391OpenAlexW2272851450MaRDI QIDQ2970053FDOQ2970053

Authors: Dhruv Mubayi, Alexandr Kostochka 

Publication date: 27 March 2017

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Abstract: A collection of sets is {em intersecting} if every two members have nonempty intersection. We describe the structure of intersecting families of $r$-sets of an $n$-set whose size is quite a bit smaller than the maximum $n-1chooser-1$ given by the ErdH os-Ko-Rado Theorem. In particular, this extends the Hilton-Milner theorem on nontrivial intersecting families and answers a recent question of Han and Kohayakawa for large $n$. In the case $r=3$ we describe the structure of all intersecting families with more than 10 edges. We also prove a stability result for the Erdos matching problem. Our short proofs are simple applications of the Delta-system method introduced and extensively used by Frankl since 1977.

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

Recommendations

• Structure and supersaturation for intersecting families
• On the union of intersecting families
• Multiply-intersecting families revisited
• On cross-intersecting families
• Multiply-intersecting families
• Structural results for conditionally intersecting families and some applications
• On the kernel of intersecting families
• A note on large \(H\)-intersecting families
• Size and structure of large \((s,t)\)-union intersecting families
• The structure of large non-trivial \(t\)-intersecting families of finite sets

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Ko-Rado+theorem&go=Go Erd��s-Ko-Rado theorem]delta-system method

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15) Extremal set theory (05D05) Triple systems (05B07)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• A Combinatorial Theorem
• Title not available (Why is that?)
• On Erdős' extremal problem on matchings in hypergraphs
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Hypergraph Turán numbers of linear cycles
• Linear trees in uniform hypergraphs
• On families of finite sets no two of which intersect in a singleton
• The size of a hypergraph and its matching number
• Improved bounds for Erdős' matching conjecture
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• On intersecting families of finite sets
• On intersecting families of finite sets
• The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family

Cited In (29)

• Tight bounds for Katona's shadow intersection theorem
• Large non-trivial \(t\)-intersecting families of signed sets
• Nearly extremal non-trivial cross \(t\)-intersecting families and \(r\)-wise \(t\)-intersecting families
• Title not available (Why is that?)
• Degree versions of theorems on intersecting families via stability
• Application of hypergraph Hoffman's bound to intersecting families
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
• Size and structure of large \((s,t)\)-union intersecting families
• Intersecting Families are Essentially Contained in Juntas
• The structure of maximal non-trivial \(d\)-wise intersecting uniform families with large sizes
• Stability on matchings in 3-uniform hypergraphs
• Structure and supersaturation for intersecting families
• Erdős-Ko-Rado with conditions on the minimum complementary degree
• A generalization of diversity for intersecting families
• Short proofs of three results about intersecting systems
• Stability of intersecting families
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• Stabilities for non-uniform \(t\)-intersecting families
• Hypergraphs without non-trivial intersecting subgraphs
• Non-trivial \(t\)-intersecting families for symplectic polar spaces
• A hierarchy of maximal intersecting triple systems
• On shadows of intersecting families
• Intersecting families of polynomials over finite fields
• A degree version of the Hilton-Milner theorem
• Nontrivial \(t\)-intersecting families for vector spaces
• The structure of large non-trivial \(t\)-intersecting families of finite sets
• On the multicolor Ramsey number for 3-paths of length three
• Non-trivial \(d\)-wise intersecting families
• Intersecting families of discrete structures are typically trivial

This page was built for publication: The structure of large intersecting families

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