The structure of large intersecting families
By Alexandr V. Kostochka, Dhruv Mubayi. 2016
47 citations recorded by the source corpus.
A collection of sets is 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 1 r 1 given by the Erd} 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 Erd} os matching problem. Our short proofs are simple applications of the Delta-system method introduced and extensively used by Frankl since 1977.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering
View Paper: https://www.semanticscholar.org/paper/bebccfa4b1dbc26cdb893121c4af58224b49a3aa
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Electrical and Electronic Engineering
Citations in the corpus
- Stability versions of Erdős–Ko–Rado type theorems via isoperimetry (2016, result): “In [43], Keevash and Mubayi used Frankl’s result to prove an EKR-type theorem on set systems that do not contain a simplex or a cluster.”