Triangle-intersecting families of graphs
From MaRDI portal
Publication:2428720
DOI10.4171/JEMS/320zbMATH Open1238.05143arXiv1010.4909MaRDI QIDQ2428720FDOQ2428720
Authors: David Ellis, Yuval Filmus, Ehud Friedgut 
Publication date: 20 April 2012
Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)
Abstract: A family of graphs F is said to be triangle-intersecting if for any two graphs G,H in F, the intersection of G and H contains a triangle. A conjecture of Simonovits and Sos from 1976 states that the largest triangle-intersecting families of graphs on a fixed set of n vertices are those obtained by fixing a specific triangle and taking all graphs containing it, resulting in a family of size (1/8) 2^{n choose 2}. We prove this conjecture and some generalizations (for example, we prove that the same is true of odd-cycle-intersecting families, and we obtain best possible bounds on the size of the family under different, not necessarily uniform, measures). We also obtain stability results, showing that almost-largest triangle-intersecting families have approximately the same structure.
Full work available at URL: https://arxiv.org/abs/1010.4909
Recommendations
Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Extremal combinatorics (05D99)
Cites Work
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- The complete intersection theorem for systems of finite sets
- Some intersection theorems for ordered sets and graphs
- Title not available (Why is that?)
- The exact bound in the Erdős-Ko-Rado theorem
- On the degree of Boolean functions as real polynomials
- Title not available (Why is that?)
- On the measure of intersecting families, uniqueness and stability
- Intersecting families of permutations
- Families intersecting on an interval
- Representations of families of triples over \(GF(2)\)
- Anticlusters and intersecting families of subsets
Cited In (33)
- Proof of an intersection theorem via graph homomorphisms
- Triangle-different Hamiltonian paths
- On sum-intersecting families of positive integers
- More complete intersection theorems
- Structured Codes of Graphs
- Boolean functions: influence, threshold and noise
- A note on Hamiltonian-intersecting families of graphs
- \(K_4\)-intersecting families of graphs
- Title not available (Why is that?)
- A note on large \(H\)-intersecting families
- Path separation by short cycles
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- Short proofs of three results about intersecting systems
- On \(k\)-neighbor separated permutations
- The theta number of simplicial complexes
- Kruskal-Katona-type problems via the entropy method
- Graph-codes
- G-Intersection Theorems for Matchings and Other Graphs
- Spectral bounds for the independence ratio and the chromatic number of an operator
- Families of integral cographs within a triangular array
- KKL's influence on me
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- The junta method in extremal hypergraph theory and Chvátal's conjecture
- Families of very different paths
- Stability for intersecting families in \(\mathrm{PGL}(2,q)\)
- High dimensional Hoffman bound and applications in extremal combinatorics
- Connector families of graphs
- 3-setwise intersecting families of the symmetric group
- 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
- A quasi-stability result for dictatorships in \(S_n\)
- Approximation by juntas in the symmetric group, and forbidden intersection problems
This page was built for publication: Triangle-intersecting families of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428720)
