Setwise intersecting families of permutations

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

David Ellis

Publication date: 22 March 2012

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

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.

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

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

zbMATH Keywords

representation theory[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Ko-Rado&go=Go Erd��s-Ko-Rado]intersecting families of permutations

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (30)

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

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)