Setwise intersecting families of permutations

Details Setwise intersecting families of permutations Setwise intersecting families of permutations

2011-06-03

arxiv.org/abs/1106.0725v2

Mathematics

Combinatorics

Revised version with a substantially expanded open problems section

Scientific paper

A family of permutations A \subset S_n is said to be t-set-intersecting if for any two permutations \sigma, and \pi \in A, there exists a t-set x whose image is the same under both permutations, i.e. \sigma(x)=\pi(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\'anos K\"orner. 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.

Affiliated with

Also associated with

No associations

Rating

Setwise 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 Setwise intersecting families of permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Setwise intersecting families of permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-224304