Intersecting families of permutations

Peter J. Cameron; C. Y. Ku

doi:10.1016/S0195-6698(03)00078-7

Intersecting families of permutations

Peter J. Cameron^*, C. Y. Ku

^*Corresponding author for this work

Centre for Interdisciplinary Research in Computational Algebra

Research output: Contribution to journal › Article › peer-review

129 Citations (Scopus)

Abstract

Let S_n be the symmetric group on the set X={1,2,...,n}. A subset S of S_n 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⊆S_n 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 language	English
Pages (from-to)	881-890
Number of pages	10
Journal	European Journal of Combinatorics
Volume	24
Issue number	7
DOIs	https://doi.org/10.1016/S0195-6698(03)00078-7
Publication status	Published - 1 Oct 2003

Access to Document

10.1016/S0195-6698(03)00078-7

Cite this

@article{b20b82eed1ae4548bed9a4d991340a2d,

title = "Intersecting families of permutations",

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.",

author = "Cameron, {Peter J.} and Ku, {C. Y.}",

year = "2003",

month = oct,

day = "1",

doi = "10.1016/S0195-6698(03)00078-7",

language = "English",

volume = "24",

pages = "881--890",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press/Elsevier ",

number = "7",

}

TY - JOUR

T1 - Intersecting families of permutations

AU - Cameron, Peter J.

AU - Ku, C. Y.

PY - 2003/10/1

Y1 - 2003/10/1

N2 - 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.

AB - 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.

U2 - 10.1016/S0195-6698(03)00078-7

DO - 10.1016/S0195-6698(03)00078-7

M3 - Article

AN - SCOPUS:0141688328

SN - 0195-6698

VL - 24

SP - 881

EP - 890

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 7

ER -

Intersecting families of permutations

Abstract

Access to Document

Fingerprint

Cite this