Intersecting families of transformations
For \(n\in \mathbb{N}\), let \(\mathcal{T}_{n}\) and \(\mathcal{S}_{n}\) denote the full transformation semigroup and the symmetric group on the finite set \(X_{n}=\{1< \cdots <n\}\), respectively. Two transformations \(\alpha\) and \(\beta\) in \(\mathcal{T}_{n}\) are called \(t\)-intersect if there exists a subset \(Y\subseteq X_{n}\) of size \(t\) such that \(x\alpha =x\beta\) for each \(x\in Y\). A subset \(I\) of \(\mathcal{T}_{n}\) is called a \(t\)-intersecting family if any two transformations in \(I\) are \(t\)-intersect. A \(t\)-intersecting family \(I\) is called maximum if there exists no t-intersecting family \(J\) of \(\mathcal{T}_{n}\) such that \(\rvert J\lvert >\rvert I\lvert\). It is shown in [\textit{P. Frankl} and \textit{M. Deza}, J. Comb. Theory, Ser. A 22, 352--360 (1977; Zbl 0352.05003)] that if \(I\subseteq \mathcal{S}_{n}\) is \(1\)-intersecting, then \(\rvert I\lvert \leq(n-1)!\). The authors focus on \(1\)-intersecting families of \(\mathcal{T}_{n}\), especially of \[K(n,r)=\{ \alpha\in \mathcal{T}_{n} : \lvert \mbox{im}(\alpha)\rvert \leq r \}\] for \(1\leq r\leq n\). They prove that the cardinality of a maximum \(1\)-intersecting family of \(K(n,r)\) is \(\sum\limits_{k=1}^{r}\binom{n-1}{k-1}S(n,k)(k-1)!\) where \(S(n,k)\) denotes the Stirling number of the second kind and that the cardinality of a maximum \(1\)-intersecting family of \(\mathcal{T}_{n}\) is \(n^{n-1}\). Moreover, the maximum \(1\)-intersecting families of \(K(n,r)\) is characterized. Finally, using this characterization, the number of maximum intersecting families of \(K(n,r)\) are determined.
- Classical finite transformation semigroups. An introduction.
- Counting families of mutually intersecting sets
- scientific article; zbMATH DE number 3974960 (Why is no real title available?)
- scientific article; zbMATH DE number 736301 (Why is no real title available?)
- scientific article; zbMATH DE number 789816 (Why is no real title available?)
- scientific article; zbMATH DE number 3365270 (Why is no real title available?)
- Intersecting families of permutations
- Intersecting families of permutations
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Maximal intersecting families
- On the maximum number of permutations with given maximal or minimal distance
- Stable sets of maximal size in Kneser-type graphs
- The diametric theorem in Hamming spaces---optimal anticodes
- The Erdős-Ko-Rado theorem for integer sequences
- Voting fairly: Transitive maximal intersecting families of sets
This page was built for publication: Intersecting families of transformations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6988934)
