Triangle-intersecting families of graphs
From MaRDI portal
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
- Anticlusters and intersecting families of subsets
- Families intersecting on an interval
- scientific article; zbMATH DE number 4029608 (Why is no real title available?)
- scientific article; zbMATH DE number 3349875 (Why is no real title available?)
- Intersecting families of permutations
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- 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
(40)- More complete intersection theorems
- Boolean functions: influence, threshold and noise
- The junta method in extremal hypergraph theory and Chvátal's conjecture
- On a biased edge isoperimetric inequality for the discrete cube
- 3-setwise intersecting families of the symmetric group
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- The theta number of simplicial complexes
- Families of integral cographs within a triangular array
- Approximation by juntas in the symmetric group, and forbidden intersection problems
- High dimensional Hoffman bound and applications in extremal combinatorics
- Families of very different paths
- scientific article; zbMATH DE number 4134102 (Why is no real title available?)
- G-Intersection Theorems for Matchings and Other Graphs
- A note on large H-intersecting families
- Spectral bounds for the independence ratio and the chromatic number of an operator
- Connector families of graphs
- A quasi-stability result for dictatorships in S_n
- On \(k\)-neighbor separated permutations
- Path separation by short cycles
- Structured Codes of Graphs
- \(K_4\)-intersecting families of graphs
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- Graph-codes
- KKL's influence on me
- On sum-intersecting families of positive integers
- A note on Hamiltonian-intersecting families of graphs
- Short proofs of three results about intersecting systems
- Kruskal-Katona-type problems via the entropy method
- Triangle-different Hamiltonian paths
- Intersection theorems for families of matchings of complete k-partite k-graphs
- The probability that a random graph is even-decomposable
- Stability of large rainbow intersecting families with product measure
- Upper bounds for linear graph codes
- Unified bounds for the independence number of graphs
- Spectral bounds for the independence number of graphs and even uniform hypergraphs
- Difference-isomorphic graph families
- Invitation to intersection problems for finite sets
- Proof of an intersection theorem via graph homomorphisms
- Stability for intersecting families in \(\mathrm{PGL}(2,q)\)
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)
