Stable sets of maximal size in Kneser-type graphs

DOI10.1016/J.EJC.2003.10.006zbMath1048.05078OpenAlexW2084490360WikidataQ105583611 ScholiaQ105583611MaRDI QIDQ1827339

Benoit Larose, Claudia Malvenuto

Publication date: 6 August 2004

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2003.10.006

zbMATH Keywords

Cayley graphsKneser graphsPermutation graphsVertex-transitive graphsStable sets

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal set theory (05D05)

Related Items (54)

An Erdős-Ko-Rado theorem for finite 2-transitive groups ⋮ Structure of independent sets in direct products of some vertex-transitive graphs ⋮ On Disjoint Cross Intersecting Families of Permutations ⋮ Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations ⋮ The Katona cycle proof of the Erdős-Ko-Rado theorem and its possibilities ⋮ On maximum intersecting sets in direct and wreath product of groups ⋮ On the largest intersecting set in \(\mathrm{GL}_2(q)\) and some of its subgroups ⋮ An analogue of the Erdős-Ko-Rado theorem for weak compositions ⋮ Cross-intersecting families and primitivity of symmetric systems ⋮ An Erdős-Ko-Rado theorem for the derangement graph of PGL(\(2,q\)) acting on the projective line ⋮ The Erdős-Ko-Rado property for some 2-transitive groups ⋮ An Erdős-Ko-Rado theorem for permutations with fixed number of cycles ⋮ On the Erdős-Ko-Rado property for finite groups ⋮ A non-trivial intersection theorem for permutations with fixed number of cycles ⋮ Intersection theorems for finite general linear groups ⋮ On the intersection density of the symmetric group acting on uniform subsets of small size ⋮ Stability for intersecting families in \(\mathrm{PGL}(2,q)\) ⋮ Theorems of Erdős-Ko-Rado type in geometrical settings ⋮ A new proof for the Erdős-Ko-Rado theorem for the alternating group ⋮ An Erdős-Ko-Rado-type theorem in Coxeter groups. ⋮ Forbidding just one intersection, for permutations ⋮ Setwise intersecting families in classical Coxeter groups ⋮ On triangles in derangement graphs ⋮ Intersecting families in classical Coxeter groups ⋮ Erdős-Ko-Rado theorems for permutations and set partitions ⋮ An Erdős-Ko-Rado theorem for the group \(\mathrm{PSU}(3, q)\) ⋮ Fourier analysis and large independent sets in powers of complete graphs ⋮ The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations ⋮ Characterization of intersecting families of maximum size in \(\mathrm{PSL}(2,q)\) ⋮ A quasi-stability result for dictatorships in \(S_n\) ⋮ Intersecting families of permutations ⋮ The Erdős-Ko-Rado theorem for the derangement graph of the projective general linear group acting on the projective space ⋮ Erdős-Ko-Rado theorem for irreducible imprimitive reflection groups ⋮ Eigenvalues of the derangement graph ⋮ Cross-intersecting families of permutations ⋮ Some Erdős-Ko-Rado theorems for injections ⋮ Unnamed Item ⋮ On the EKR-module property ⋮ 3-setwise intersecting families of the symmetric group ⋮ A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations ⋮ Largest independent sets of certain regular subgraphs of the derangement graph ⋮ Invitation to intersection problems for finite sets ⋮ Maximum stable sets in analogs of Kneser and complete graphs ⋮ Strongly intersecting integer partitions ⋮ Independent sets of maximal size in tensor powers of vertex-transitive graphs ⋮ On \(t\)-intersecting families of signed sets and permutations ⋮ Intersection theorem for finite permutations ⋮ Setwise intersecting families of permutations ⋮ On the Erdos-Ko-Rado property of finite groups of order a product of three primes ⋮ On \(r\)-cross \(t\)-intersecting families for weak compositions ⋮ A Deza-Frankl type theorem for set partitions ⋮ On complete multipartite derangement graphs ⋮ On the intersection density of primitive groups of degree a product of two odd primes ⋮ An Erdős--Ko--Rado theorem for partial permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• Homomorphisms of 3-chromatic graphs
• On the maximum number of permutations with given maximal or minimal distance
• Graph products, Fourier analysis and spectral techniques
• Projectivity and independent sets in powers of graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Applications of product colouring
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting families of permutations

This page was built for publication: Stable sets of maximal size in Kneser-type graphs