The exact bound for the Erdős-Ko-Rado theorem for t-cycle-intersecting permutations

2012/08/17 by Karen Meagher, Meagher, Karen, Alison Purdy +1
Computer Science · Medicine · #05D05 (Primary) 05A05 (Secondary) #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #Data-Driven Disease Surveillance #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1208.3638

openalex publication_date 2012/08/17 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

In this paper we adapt techniques used by Ahlswede and Khachatrian in their proof of the Complete Erdős-Ko-Rado Theorem to show that if n ≥ 2t+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.

Related

• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• 2-intersecting permutations
• Intersecting generalised permutations
• Forbidding just one intersection, for permutations
• The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings