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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4029608 (Why is no real title available?)
- scientific article; zbMATH DE number 3349875 (Why is no real title available?)
- Anticlusters and intersecting families of subsets
- Families intersecting on an interval
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersecting families of permutations
- On the degree of Boolean functions as real polynomials
- On the measure of intersecting families, uniqueness and stability
- Representations of families of triples over GF(2)
- Some intersection theorems for ordered sets and graphs
- The complete intersection theorem for systems of finite sets
- The exact bound in the Erdős-Ko-Rado theorem
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
- Boolean functions: influence, threshold and noise
- Structured Codes of Graphs
- scientific article; zbMATH DE number 4134102 (Why is no real title available?)
- A note on Hamiltonian-intersecting families of graphs
- \(K_4\)-intersecting families of graphs
- 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
- The theta number of simplicial complexes
- Short proofs of three results about intersecting systems
- On \(k\)-neighbor separated permutations
- Kruskal-Katona-type problems via the entropy method
- G-Intersection Theorems for Matchings and Other Graphs
- Graph-codes
- Spectral bounds for the independence ratio and the chromatic number of an operator
- Families of integral cographs within a triangular array
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- The junta method in extremal hypergraph theory and Chvátal's conjecture
- KKL's influence on me
- 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
- A quasi-stability result for dictatorships in \(S_n\)
- On a biased edge isoperimetric inequality for the discrete cube
- 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)
