Shadows and intersections: Stability and new proofs
From MaRDI portal
Abstract: We give a short new proof of a version of the Kruskal-Katona theorem due to Lov'asz. 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 Lov'asz's theorem that answers a question of Frankl and Tokushige.
Recommendations
- On strengthenings of the intersecting shadow theorem
- Shadows and intersections in vector spaces
- Tight bounds for Katona's shadow intersection theorem
- The problem of shadow for domains in Euclidean spaces
- The shadow picture problem for nonintersecting curves
- Shadows. Convexity, regularity, and subharmonicity
- Shadowing in the case of nontransverse intersection
- Topological and geometric properties of generalized convex sets and the shadow problem
- Stable determination of convex bodies from intersections
Cites work
- scientific article; zbMATH DE number 3489128 (Why is no real title available?)
- scientific article; zbMATH DE number 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 736295 (Why is no real title available?)
- scientific article; zbMATH DE number 3189757 (Why is no real title available?)
- A Certain Class of Incidence Matrices
- A new short proof for the Kruskal-Katona theorem
- A note on the use of determinant for proving lower bounds on the size of linear circuits
- A simple proof of the Kruskal-Katona theorem
- A simple proof of the Kruskal-Katona theorem and of some associated binomial inequalities
- Erdős-Ko-Rado from Kruskal-Katona
- Erdős-Ko-Rado theorem with conditions on the maximal degree
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Improved lower bounds on the rigidity of Hadamard matrices
- Intersecting Families are Essentially Contained in Juntas
- Minimal eigenvalue of the Coxeter Laplacian for the symmetric group
- On the measure of intersecting families, uniqueness and stability
- On the number of copies of one hypergraph in another
- On the number of subgraphs of prescribed type of graphs with a given number of edges
- Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
- Set systems without a simplex or a cluster
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Symmetric groups and expanders
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Threshold functions
Cited in
(40)- A pushing-pulling method: New proofs of intersection theorems
- Stability theorems for some Kruskal-Katona type results
- Minimising the total number of subsets and supersets
- On strengthenings of the intersecting shadow theorem
- Tight bounds for Katona's shadow intersection theorem
- Upper tails via high moments and entropic stability
- Removal and stability for Erdős-Ko-Rado
- Stability analysis for \(k\)-wise intersecting families
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Shadows and intersections in vector spaces
- An inequality for functions on the Hamming cube
- A product version of the Hilton-Milner-Frankl theorem
- The shadow picture problem for nonintersecting curves
- Stability for vertex isoperimetry in the cube
- Shadows of ordered graphs
- Vertex isoperimetry and independent set stability for tensor powers of cliques
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- Remarks on the Erdős matching conjecture for vector spaces
- On the structure of subsets of the discrete cube with small edge boundary
- The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family
- Hypercontractivity on the symmetric group
- A Deza-Frankl type theorem for set partitions
- Inclusion matrices for rainbow subsets
- Transference for the Erdős-Ko-Rado theorem
- A simple removal lemma for large nearly-intersecting families
- Resilience of ranks of higher inclusion matrices
- Extremal families for Kruskal-Katona theorem
- Complete r-partite graphs determined by their domination polynomial
- A non-trivial intersection theorem for permutations with fixed number of cycles
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- A product version of the Hilton-Milner theorem
- Diversity
- On the densities of cliques and independent sets in graphs
- Stability of the potential function
- Almost isoperimetric subsets of the discrete cube
- On the rank of higher inclusion matrices
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Invitation to intersection problems for finite sets
- On a biased edge isoperimetric inequality for the discrete cube
- Set Systems with L-Intersections and k-Wise L-Intersecting Families
This page was built for publication: Shadows and intersections: Stability and new proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q932174)
