Setwise intersecting families of permutations

DOI10.1016/J.JCTA.2011.12.003zbMATH Open1237.05210OpenAlexW2159609825MaRDI QIDQ765866FDOQ765866

Authors David Ellis

Publication date 22 March 2012

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.0725

zbMATH Keywords

representation theoryintersecting families of permutationsErdős-Ko-Rado

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of representation theory (05E10)

Abstract: A family of permutations $Asubset{S}_n$ is said to be emph{$t$-set-intersecting} if for any two permutations $sigma,piinA$, 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.

Recommendations

• Intersecting families of permutations
• 3-setwise intersecting families of the symmetric group
• Stability for \(t\)-intersecting families of permutations
• Intersecting families of permutations
• Approximation by juntas in the symmetric group, and forbidden intersection problems

Cites work

• scientific article; zbMATH DE number 51129 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• An Erdős-Ko-Rado-type theorem in Coxeter groups.
• Intersecting families of permutations
• Intersecting families of permutations
• On the maximum number of permutations with given maximal or minimal distance
• On the spectrum of the derangement graph
• Properties of generalized derangement graphs
• Representations and characters of groups.
• Stable sets of maximal size in Kneser-type graphs
• The Hook Graphs of the Symmetric Group

Cited in

(34)

• Some Erdös-Ko-Rado results for linear and affine groups of degree two
• Intersecting families of permutations
• Stability for \(t\)-intersecting families of permutations
• Intersecting families of discrete structures are typically trivial
• On the EKR-module property
• Interlocked Permutations
• Path separation by short cycles
• On the intersection density of the Kneser graph \(K(n, 3)\)
• On $t$-Intersecting Families of Permutations
• The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations
• On the intersection density of the symmetric group acting on uniform subsets of small size
• Set systems and families of permutations with small traces
• Enumeration of intersecting families
• Intersection theorems for finite general linear groups
• Theorems of Erdős-Ko-Rado type in geometrical settings
• Cameron-Liebler sets in permutation groups
• Intersecting families of permutations
• A non-trivial intersection theorem for permutations with fixed number of cycles
• The Family F of Permutations of ℕ
• Intersecting families of sets and permutations: a survey
• Setwise intersecting families in classical Coxeter groups
• An extension of the Erdős-Ko-Rado theorem to set-wise 2-intersecting families of perfect matchings
• An extension of the Erdős-Ko-Rado theorem to uniform set partitions
• An Erdős-Ko-Rado theorem for finite 2-transitive groups
• Intersecting families in classical Coxeter groups
• On the intersection density of primitive groups of degree a product of two odd primes
• Forbidding just one intersection, for permutations
• Cross-Intersecting Families of Partial Permutations
• On \(t\)-intersecting families of signed sets and permutations
• Intersecting generalised permutations
• 3-setwise intersecting families of the symmetric group
• Approximation by juntas in the symmetric group, and forbidden intersection problems
• Counting families of mutually intersecting sets
• Eigenvalues of Cayley graphs

This page was built for publication: Setwise intersecting families of permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765866)