A new proof of the Erdos-Ko-Rado theorem for intersecting families of permutations

被引：67

作者：

Godsil, Chris ^{[1
]}

Meagher, Karen ^{[2
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] Univ Regina, Dept Math & Stat, Regina, SK S4S 0A2, Canada

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2009年 / 30卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

VECTOR-SPACES; SETS; SYSTEMS; GRAPHS;

D O I：

10.1016/j.ejc.2008.05.006

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 epsilon {1....,n) such that pi(i) = sigma(i). Deza and Frankl JP. Frankl, M. Deza, On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A 22 (3) (1977) 352-3601 proved that if S subset of S(n) is intersecting then |S| <= (n - 1)|. Further, Cameron and Ku [P]. Cameron, C.Y. Ku, Intersecting families of permutations, European J. Combin. 24 (7) (2003) 881-890] showed 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. (C) 2008 Elsevier Ltd. All rights reserved.

引用

页码：404 / 414

页数：11

共 23 条

[1] Cycle decompositions IV: complete directed graphs and fixed length directed cycles [J].