Intersecting Families of Permutations

Details Intersecting Families of Permutations Intersecting Families of Permutations

2010-11-15

arxiv.org/abs/1011.3342v1

Mathematics

Combinatorics

An expanded version (with slightly more detail and an added open problems section added) of a paper written in late 2008, prev

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Intersecting Families of Permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Intersecting Families of Permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intersecting Families of Permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-298595