The exact bound for the Erd\H{o}s-Ko-Rado theorem for t-cycle-intersecting permutations

arXiv1208.3638MaRDI QIDQ6235096FDOQ6235096

Authors: K. Meagher, Alison Purdy 

Publication date: 17 August 2012

Abstract: In this paper we adapt techniques used by Ahlswede and Khachatrian in their proof of the Complete ErdH{o}s-Ko-Rado Theorem to show that if $ngeq2t+1$, then any pairwise $t$-cycle-intersecting family of permutations has cardinality less than or equal to $(n-t)!$. Furthermore, the only families attaining this size are the stabilizers of $t$ points, that is, families consisting of all permutations having $t$ 1-cycles in common. This is a strengthening of a previous result of Ku and Renshaw and supports a recent conjecture by Ellis, Friedgut and Pilpel concerning the corresponding bound for $t$-intersecting families of permutations.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

This page was built for publication: The exact bound for the Erd\H{o}s-Ko-Rado theorem for $t$-cycle-intersecting permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6235096)