Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Intersecting families of permutations


Authors: David Ellis, Ehud Friedgut and Haran Pilpel
Journal: J. Amer. Math. Soc. 24 (2011), 649-682
MSC (2010): Primary 05E10, 20C30, 05D99
Published electronically: January 31, 2011
MathSciNet review: 2784326
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A set of permutations $ I \subset S_n$ is said to be $ k$-intersecting if any two permutations in $ I$ agree on at least $ k$ points. We show that for any $ k \in \mathbb{N}$, if $ n$ is sufficiently large depending on $ k$, then the largest $ k$-intersecting subsets of $ S_n$ are cosets of stabilizers of $ k$ points, proving a conjecture of Deza and Frankl. We also prove a similar result concerning $ k$-cross-intersecting subsets. Our proofs are based on eigenvalue techniques and the representation theory of the symmetric group.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 05E10, 20C30, 05D99

Retrieve articles in all journals with MSC (2010): 05E10, 20C30, 05D99


Additional Information

David Ellis
Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB England
Address at time of publication: St John’s College, Cambridge, CB2 1TP, United Kingdom

Ehud Friedgut
Affiliation: Department of Mathematics, Hebrew University, 91904 Jerusalem, Israel, and Department of Mathematics, University of Toronto, 40 St. George Street, Toronto, Ontario M5S 2E4, Canada

Haran Pilpel
Affiliation: Department of Mathematics, Hebrew University, 91904 Jerusalem, Israel
Address at time of publication: Google, Inc., Levinstein Tower 26th Floor, 23 Manachem Begin St, 66183 Tel Aviv, Israel

DOI: http://dx.doi.org/10.1090/S0894-0347-2011-00690-5
PII: S 0894-0347(2011)00690-5
Keywords: Intersecting families of permutations, Erdos-Ko-Rado, representation theory.
Received by editor(s): March 9, 2009
Received by editor(s) in revised form: November 15, 2010, and December 8, 2010
Published electronically: January 31, 2011
Additional Notes: Research of the second author was supported in part by the Israel Science Foundation, grant no. 0397684, and NSERC grant 341527.
Research of the third author was supported in part by the Giora Yoel Yashinsky Memorial Grant.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.