Setwise intersecting families of permutations

2011/06/03 by David Ellis, Ellis, David
Engineering · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Representation Theory (math.RT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1106.0725

openalex publication_date 2011/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A family of permutations A ⊂ S_n is said to be t-set-intersecting if for any two permutations σ, π∈ A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the largest t-set-intersecting families of permutations in S_n are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza-Frankl conjecture, proved in [4]. Our proof uses similar techniques to those of [4], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.

Related

• Intersecting Families of Permutations
• Stability for t-intersecting families of permutations
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• 2-intersecting permutations
• 3-setwise intersecting families of the symmetric group