Intersecting families of permutations

被引:135
作者
Cameron, PJ [1 ]
Ku, CY [1 ]
机构
[1] Queen Mary Univ London, Sch Math Sci, London E1 4NS, England
关键词
D O I
10.1016/S0195-6698(03)00078-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 E X (that is g and h agree on x). Deza and Frankl (J. Combin. Theory Ser. A 22 (1977) 352) proved that if S subset of or equal to S-n is intersecting then \S\ less than or equal to (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.
引用
收藏
页码:881 / 890
页数:10
相关论文
共 6 条
[1]  
[Anonymous], 1987, Combinatorics of finite sets
[2]  
Cameron PJ, 2002, BOLYAI SOC MATH STUD, V11, P205
[3]  
CAMERON PJ, 1986, ALGEBRAIC EXTREMAL M, P39
[4]   INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS [J].
ERDOS, P ;
RADO, R ;
KO, C .
QUARTERLY JOURNAL OF MATHEMATICS, 1961, 12 (48) :313-&
[5]   MAXIMUM NUMBER OF PERMUTATIONS WITH GIVEN MAXIMAL OR MINIMAL DISTANCE [J].
FRANKL, P ;
DEZA, M .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1977, 22 (03) :352-360
[6]  
*GAP GROUP, 2002, GAP GROUPS ALG PROGR