Shadows and intersections: Stability and new proofs
By Peter Keevash. 2008
78 citations recorded by the source corpus.
Abstract We give a short new proof of a version of the Kruskal–Katona theorem due to Lovasz. Our method can be extended to a stability result, describing the approximate structure of configurations that are close to being extremal, which answers a question of Mubayi. This in turn leads to another combinatorial proof of a stability theorem for intersecting families, which was originally obtained by Friedgut using spectral techniques and then sharpened by Keevash and Mubayi by means of a purely combinatorial result of Frankl. We also give an algebraic perspective on these problems, giving yet another proof of intersection stability that relies on expansion of a certain Cayley graph of the symmetric group, and an algebraic generalisation of Lovasz's theorem that answers a question of Frankl and Tokushige.
Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/216d98a2f1e7af9cc185cc3c849eb73b34d5599a
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Discrete Mathematics and Combinatorics
In Geometry and Topology
Citations in the corpus
- Stability versions of Erdős–Ko–Rado type theorems via isoperimetry (2016, background): “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.”
- Upper tails via high moments and entropic stability (2019, unknown): “This could be proved by appealing to a stability version of the Kruskal–Katona theorem due to Keevash [45].”
- The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton--Milner family (2015, background): “called “stability” of the Erd˝os–Ko–Rado theorem in a very strong sense (for other stability-type results related to the Erd˝os–Ko–Rado theorem, we refer the reader to Dinur and Friedgut [4], Keevash [15] and Keevash and Mubayi [16]). What lies beyond the 1967 theorem of Hilton and Milner, that is, ”