A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
From MaRDI portal
(Redirected from Publication:1003591)
Abstract: Let S(n) be the symmetric group on n points. A subset S of S(n) is intersecting if for any pair of permutations pi, sigma in S there is a point i in {1,...,n} such that pi(i)=sigma(i). Deza and Frankl cite{MR0439648} proved that if S a subset of S(n) is intersecting then |S| leq (n-1)!. Further, Cameron and Ku cite{MR2009400} show that the only sets that meet this bound are the cosets of a stabilizer of a point. In this paper we give a very different proof of this same result.
Recommendations
Cites work
- scientific article; zbMATH DE number 1601795 (Why is no real title available?)
- scientific article; zbMATH DE number 3884178 (Why is no real title available?)
- scientific article; zbMATH DE number 51906 (Why is no real title available?)
- scientific article; zbMATH DE number 1054727 (Why is no real title available?)
- scientific article; zbMATH DE number 2232233 (Why is no real title available?)
- An existence theorem for latin squares
- An extension of the Erdoes, Ko, Rado theorem to t-designs
- Chromatic number and the 2-rank of a graph
- Cycle decompositions. IV: Complete directed graphs and fixed length directed cycles
- Erdös–Ko–Rado Theorem—22 Years Later
- Erdős-Ko-Rado theorems for uniform set-partition systems
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Independent sets in association schemes
- Intersecting families of permutations
- Intersection theorems for systems of finite vector spaces
- Nombres de coloration de l'hypergraphe h-parti complet
- On the maximum number of permutations with given maximal or minimal distance
- On the spectrum of the derangement graph
- Problems in algebraic combinatorics
- Stable sets of maximal size in Kneser-type graphs
- The Erdős-Ko-Rado theorem for vector spaces
Cited in
(63)- An Erdős--Ko--Rado theorem for partial permutations
- Some Erdös-Ko-Rado results for linear and affine groups of degree two
- The Erdős-Ko-Rado property for some 2-transitive groups
- On the Erdős-Ko-Rado property for finite groups
- An Erdős-Ko-Rado-type theorem in Coxeter groups.
- Hilton-Milner results in projective and affine spaces
- Eigenvalues of the derangement graph
- Maximal sets of \(k\)-spaces pairwise intersecting in at least a \((k-2)\)-space
- On maximum intersecting sets in direct and wreath product of groups
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- Structure of independent sets in direct products of some vertex-transitive graphs
- Intersecting families of permutations
- On the largest intersecting set in \(\mathrm{GL}_2(q)\) and some of its subgroups
- Erdős-Ko-Rado for perfect matchings
- All 2-transitive groups have the EKR-module property
- The Erdős-Ko-Rado theorem for the derangement graph of the projective general linear group acting on the projective space
- Graphical designs and extremal combinatorics
- Two-Part and k-Sperner Families: New Proofs Using Permutations
- Stability for intersecting families in \(\mathrm{PGL}(2,q)\)
- The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations
- On the intersection density of the symmetric group acting on uniform subsets of small size
- Erdős-Ko-Rado theorems for set partitions with certain block size
- Theorems of Erdős-Ko-Rado type in geometrical settings
- Largest independent sets of certain regular subgraphs of the derangement graph
- Erdős-Ko-Rado theorem for irreducible imprimitive reflection groups
- Intersecting families in the alternating group and direct product of symmetric groups
- Strongly intersecting integer partitions
- On complete multipartite derangement graphs
- Sharply transitive sets in quasigroup actions.
- A generalization of the Erdős-Ko-Rado theorem to \(t\)-designs in certain semilattices
- An analogue of the Erdős-Ko-Rado theorem for weak compositions
- Characterization of intersecting families of maximum size in \(\mathrm{PSL}(2,q)\)
- On \(r\)-cross \(t\)-intersecting families for weak compositions
- An Erdős-Ko-Rado theorem for the group \(\mathrm{PSU}(3, q)\)
- A non-trivial intersection theorem for permutations with fixed number of cycles
- Erdős-Ko-Rado theorems for permutations and set partitions
- The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
- An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings
- Chromatic number via Turán number
- Setwise intersecting families in classical Coxeter groups
- A Deza-Frankl type theorem for set partitions
- On diversity of certain \(t\)-intersecting families
- Cross-intersecting families and primitivity of symmetric systems
- Extremal \(G\)-free induced subgraphs of Kneser graphs
- Setwise intersecting families of permutations
- An Erdős-Ko-Rado theorem for finite 2-transitive groups
- A new proof for the Erdős-Ko-Rado theorem for the alternating group
- Alternating sign property of the perfect matching derangement graph
- On the intersection density of primitive groups of degree a product of two odd primes
- A quasi-stability result for dictatorships in \(S_n\)
- On the chromatic number of matching Kneser graphs
- Size and structure of large \((s,t)\)-union intersecting families
- 3-setwise intersecting families of the symmetric group
- An Erdős-Ko-Rado theorem for the derangement graph of PGL(\(2,q\)) acting on the projective line
- All \(3\)-transitive groups satisfy the strict-Erdős-Ko-Rado property
- On the EKR-module property
- Diversity and intersecting theorems for weak compositions
- Intersection theorems for finite general linear groups
- An extension of the Erdős-Ko-Rado theorem to set-wise 2-intersecting families of perfect matchings
- KKL's influence on me
- On the intersection spectrum of \(\mathrm{PSL}_2(q)\)
- On the Erdos-Ko-Rado property of finite groups of order a product of three primes
- Intersection density of cubic symmetric graphs
This page was built for publication: A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003591)
