Intersecting families of permutations

Peter J. Cameron*, C. Y. Ku

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

103 Citations (Scopus)

Abstract

Let Sn be the symmetric group on the set X={1,2,...,n}. A subset S of Sn is intersecting if for any two permutations g and h in S, g(x)=h(x) for some x∈X (that is g and h agree on x). Deza and Frankl (J. Combin. Theory Ser. A 22 (1977) 352) proved that if S⊆Sn is intersecting then S ≤(n-1)!. This bound is met by taking S to be a coset of a stabiliser of a point. We show that these are the only largest intersecting sets of permutations.

Original languageEnglish
Pages (from-to)881-890
Number of pages10
JournalEuropean Journal of Combinatorics
Volume24
Issue number7
DOIs
Publication statusPublished - 1 Oct 2003

Fingerprint

Dive into the research topics of 'Intersecting families of permutations'. Together they form a unique fingerprint.

Cite this