A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations

2007/10/10 by Godsil, Chris, Meagher, Karen · 1 citation
#05A05 #20B30 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0710.2109

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 π, σin S there is a point i in 1,...,n such that π(i)=σ(i). Deza and Frankl \citeMR0439648 proved that if S a subset of S(n) is intersecting then |S| ≤ (n-1)!. Further, Cameron and Ku \citeMR2009400 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.

Cited by

• A Composition-Based Approach to EKR Problems

Related

• A new proof for the Erdős-Ko-Rado Theorem for the alternating group
• The Erdős-Ko-Rado property for some permutation groups
• An Erdős-Ko-Rado theorem in general linear groups
• Intersecting Families of Permutations
• The Erdős-Ko-Rado property for some 2-transitive groups