Intersecting Families of Permutations

By David Ellis, Ehud Friedgut, Haran Pilpel. 2010

272 citations recorded by the source corpus.

A set of permutations $I \subset S_n$ is said to be {\em 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.

Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/d7820a39d0002bf3a070b80ee19a2df89b79d664

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

1. Norihide Tokushige
2. Peter Borg
3. Ehud Friedgut
4. David Ellis

In Electrical and Electronic Engineering

1. Norihide Tokushige
2. Peter Borg
3. David Ellis

Citations in the corpus

• Triangle-intersecting Families of Graphs (2010, background): “A central idea in [5] and [8] is that one may choose appropriate weights on the edges of this graph to perturb the operator defined by the adjacency matrix, and improve these bounds.”
• The eigenvalue method for cross t-intersecting families (2013, methodology): “(We will need Lemma 2 (b) which follows from the proof of Lemma 1 easily, but this is not mentioned in [4].”
• Extremal t‐intersecting sub‐families of hereditary families (2009, result): “Cameron and Ku [9] proved that actually S∗ [n],n is strictly EKR; this result was also deduced from a more general result on certain vertex transitive graphs in [36].”