A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
From MaRDI portal
Publication:1003591
DOI10.1016/J.EJC.2008.05.006zbMATH Open1177.05010arXiv0710.2109OpenAlexW1995234636MaRDI QIDQ1003591FDOQ1003591
Publication date: 4 March 2009
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0710.2109
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Chromatic number and the 2-rank of a graph
- Intersection theorems for systems of finite vector spaces
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Problems in algebraic combinatorics
- An existence theorem for latin squares
- On the maximum number of permutations with given maximal or minimal distance
- Stable sets of maximal size in Kneser-type graphs
- Intersecting families of permutations
- Erdös–Ko–Rado Theorem—22 Years Later
- Cycle decompositions. IV: Complete directed graphs and fixed length directed cycles
- The Erdős-Ko-Rado theorem for vector spaces
- Independent sets in association schemes
- An extension of the Erdoes, Ko, Rado theorem to t-designs
- Erdős-Ko-Rado theorems for uniform set-partition systems
- On the spectrum of the derangement graph
- Nombres de coloration de l'hypergraphe h-parti complet
Cited In (61)
- On the Erdos-Ko-Rado property of finite groups of order a product of three primes
- Intersection theorems for finite general linear groups
- KKL's influence on me
- On the intersection spectrum of \(\mathrm{PSL}_2(q)\)
- Diversity and intersecting theorems for weak compositions
- Intersection density of cubic symmetric graphs
- All \(3\)-transitive groups satisfy the strict-Erdős-Ko-Rado property
- On the EKR-module property
- An extension of the Erdős-Ko-Rado theorem to set-wise 2-intersecting families of perfect matchings
- The Erdős-Ko-Rado theorem for the derangement graph of the projective general linear group acting on the projective space
- The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
- Alternating sign property of the perfect matching derangement graph
- On the intersection density of primitive groups of degree a product of two odd primes
- Hilton-Milner results in projective and affine spaces
- On maximum intersecting sets in direct and wreath product of groups
- Graphical designs and extremal combinatorics
- The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations
- An Erdős-Ko-Rado theorem for the group \(\mathrm{PSU}(3, q)\)
- Structure of independent sets in direct products of some vertex-transitive graphs
- Sharply transitive sets in quasigroup actions.
- Characterization of intersecting families of maximum size in \(\mathrm{PSL}(2,q)\)
- All 2-transitive groups have the EKR-module property
- An analogue of the Erdős-Ko-Rado theorem for weak compositions
- Erdős-Ko-Rado theorems for permutations and set partitions
- Size and structure of large \((s,t)\)-union intersecting families
- On the intersection density of the symmetric group acting on uniform subsets of small size
- Cross-intersecting families and primitivity of symmetric systems
- Maximal sets of \(k\)-spaces pairwise intersecting in at least a \((k-2)\)-space
- Erdős-Ko-Rado for perfect matchings
- Chromatic number via Turán number
- On the Chromatic Number of Matching Kneser Graphs
- Setwise intersecting families of permutations
- Theorems of Erdős-Ko-Rado type in geometrical settings
- Extremal \(G\)-free induced subgraphs of Kneser graphs
- Title not available (Why is that?)
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- On \(r\)-cross \(t\)-intersecting families for weak compositions
- 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
- An Erdős-Ko-Rado theorem for the derangement graph of PGL(\(2,q\)) acting on the projective line
- An Erdős--Ko--Rado theorem for partial permutations
- The Erdős-Ko-Rado property for some 2-transitive groups
- On the Erdős-Ko-Rado property for finite groups
- On the largest intersecting set in \(\mathrm{GL}_2(q)\) and some of its subgroups
- Largest independent sets of certain regular subgraphs of the derangement graph
- A Deza-Frankl type theorem for set partitions
- Eigenvalues of the derangement graph
- Two-Part and k-Sperner Families: New Proofs Using Permutations
- Erdős-Ko-Rado theorems for set partitions with certain block size
- A generalization of the Erdős-Ko-Rado theorem to \(t\)-designs in certain semilattices
- A non-trivial intersection theorem for permutations with fixed number of cycles
- Some Erdös-Ko-Rado results for linear and affine groups of degree two
- Stability for intersecting families in \(\mathrm{PGL}(2,q)\)
- On complete multipartite derangement graphs
- Erdős-Ko-Rado theorem for irreducible imprimitive reflection groups
- Setwise intersecting families in classical Coxeter groups
- An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings
- 3-setwise intersecting families of the symmetric group
- Strongly intersecting integer partitions
- Intersecting families of permutations
- A quasi-stability result for dictatorships in \(S_n\)
Uses Software
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)
