The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations
The set of permutations of \([n] := \{1, \dots, n\}\) is denoted by \(\mbox{Sym}(n)\). A subset \(\mathcal{A}\) of \(\mbox{Sym}(n)\) is said to be \(t\)-pointwise intersecting if for every \(\sigma, \tau \in \mathcal{A}\) there exists some \(t\)-subset \(S\) of \([n]\) such that \(\sigma(x) = \tau(x)\) for each \(x \in S\). A subset \(\mathcal{A}\) of \(\mbox{Sym}(n)\) is said to be \(t\)-setwise intersecting if for every \(\sigma, \tau \in \mathcal{A}\) there exists some \(t\)-subset \(S\) of \([n]\) such that \(\{\sigma(x) \colon x \in S\} = \{\tau(x) \colon x \in S\}\). We say that \(\mbox{Sym}(n)\) has the \(t\)-pointwise star property if the size of a largest \(t\)-pointwise intersecting subset of \(\mbox{Sym}(n)\) is the size \((n-t)!\) of the \(t\)-pointwise intersecting subset \(\{\sigma \in \mbox{Sym}(n) \colon \sigma(i) = i \mbox{ for each } i \in [t]\}\). We say that \(\mbox{Sym}(n)\) has the \(t\)-setwise star property if the size of a largest \(t\)-setwise intersecting subset of \(\mbox{Sym}(n)\) is the size \(t!(n-t)!\) of the \(t\)-setwise intersecting subset \(\{\sigma \in \mbox{Sym}(n) \colon \{\sigma(1), \dots, \sigma(t)\} = [t]\}\). \textit{P. Frankl} and \textit{M. Deza} [J. Comb. Theory, Ser. A 22, 352--360 (1977; Zbl 0352.05003)] proved that \(\mbox{Sym}(n)\) has the \(1\)-pointwise star property. This is an analogue of the Erdős-Ko-Rado Theorem [\textit{P. Erdős} et al., Q. J. Math., Oxf. II. Ser. 12, 313--320 (1961; Zbl 0100.01902)]. Deza and Frankl conjectured that \(\mbox{Sym}(n)\) has the \(t\)-pointwise star property if \(n\) is sufficiently large depending on \(t\). \textit{D. Ellis} et al. [J. Am. Math. Soc. 24, No. 3, 649--682 (2011; Zbl 1285.05171)] proved this conjecture, and they conjectured that \(\mbox{Sym}(n)\) has the \(t\)-pointwise star property for \(n \geq 2t+1\). \textit{D. Ellis} [J. Comb. Theory, Ser. A 119, No. 4, 825--849 (2012; Zbl 1237.05210)] conjectured that \(\mbox{Sym}(n)\) has the \(t\)-setwise star property for \(n \geq t\), and he proved this for \(n\) sufficiently large depending on \(t\). The authors prove that for \(n \geq 2\), \(\mbox{Sym}(n)\) has the \(2\)-pointwise star property and the \(2\)-setwise star property.
- Intersecting families of permutations
- Approximation by juntas in the symmetric group, and forbidden intersection problems
- A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
- Erdős-Ko-Rado theorems for permutations and set partitions
- Stability for t-intersecting families of permutations
- 3-setwise intersecting families of the symmetric group
- Intersecting families of permutations
- An Erdős-Ko-Rado theorem for integer sequences of given rank
- Setwise intersecting families of permutations
- Partially ordered sets associated with permutations
- A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
- A proof and generalizations of the Erdős-Ko-Rado theorem using the method of linearly independent polynomials
- A simple proof of the Erdős-Chao Ko-Rado theorem
- All 2-transitive groups have the EKR-module property
- An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings
- Erdös–Ko–Rado Theorem—22 Years Later
- Erdős-Ko-Rado theorems. Algebraic approaches
- Generating a random permutation with random transpositions
- scientific article; zbMATH DE number 1601795 (Why is no real title available?)
- scientific article; zbMATH DE number 2232233 (Why is no real title available?)
- Intersecting families of permutations
- Intersecting families of permutations
- Intersection Properties of Systems of Finite Sets
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- On the maximum number of permutations with given maximal or minimal distance
- Setwise intersecting families of permutations
- Spectra of Cayley graphs
- Stable sets of maximal size in Kneser-type graphs
- The Hook Graphs of the Symmetric Group
- A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
- 3-setwise intersecting families of the symmetric group
- On the intersection density of primitive groups of degree a product of two odd primes
- On the intersection density of the symmetric group acting on uniform subsets of small size
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- Some Erdös-Ko-Rado results for linear and affine groups of degree two
- An extension of the Erdős-Ko-Rado theorem to uniform set partitions
- On the intersection density of the Kneser graph \(K(n, 3)\)
- Intersection density of imprimitive groups of degree \(pq\)
- Intersection density of transitive groups with small cyclic point stabilizers
- Intersection theorems for families of matchings of complete k-partite k-graphs
- Uniqueness for 2-intersecting families of permutations and perfect matchings
- An Erdős--Ko--Rado theorem for partial permutations
- Erdős-Ko-Rado theorems for permutations and set partitions
This page was built for publication: The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2236813)
