Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations
Ever since the famous Erdös-Ko-Rado theorem initiated the study of intersecting families of subsets, extremal problems regarding intersecting properties of families of various combinatorial objects have been extensively investigated. Among them, studies about families of subsets, vector subspaces, and permutations are of particular concern. Recently, a new quantitative intersection measure for these various families is proposed, that is, the notion of the total intersection number of a family. Let \(X\) be \(\binom{[n]}{k},\left[\begin{smallmatrix}{V}\\ {k}\end{smallmatrix}\right]\) for an \(n\)-dimensional vector space \(V\) over \(\mathbb{F}_q\) or the symmetric group \(S_n\). By considering a family \(\mathcal{F}\subseteq X\), the total intersection number of \(\mathcal{F}\) is defined by \(\mathcal{I}(\mathcal{F})=\sum_{A\in \mathcal{F}}\sum_{B\in \mathcal{F}} \operatorname{int}(A,B)\), where \(\operatorname{int}(A,B)\) has different meanings for different \(X's\). When \(X=\binom{[n]}{k}\), \(\operatorname{int}(A,B)=|A\cap B|\); when \(X=\left[\begin{smallmatrix}{V}\\ {k}\end{smallmatrix}\right]\), \(\operatorname{int}(A,B) = \dim(A\cap B)\); when \(X=S_n\), \(\operatorname{int}(A,B)=|\{i\in [n]:A(i)=B(i)\}|\). Moreover define \(\mathcal{M}\mathcal{I}(X,\mathcal{F})=\max_{\mathcal{G}\subseteq X,|\mathcal{G}|=|\mathcal{F}|}\mathcal{I}(\mathcal{G})\) as the maximal total intersection number among all the families in \(X\) with the same size of \(\mathcal{F}\). In this paper, the authors seek for structural characterisations for optimal families satisfying \(\mathcal{I}(\mathcal{F})=\mathcal{M}\mathcal{I}(X,\mathcal{F})\). When \(X=\binom{[n]}{k}\), it is shown in [\textit{X. Kong} and \textit{G. Ge}, ``On an inverse problem of the Erdős-Ko-Rado type theorems, Preprint, \url{arXiv.2004.01529}], that when \(|\mathcal{F}|=\binom{n-t}{k-t}\) which is the maximal size of a \(t\)-intersecting family, and \(\mathcal{I}(\mathcal{F})=\mathcal{M}\mathcal{I}(X,\mathcal{F})\), the full t-star (the family consisting of all \(k\)-sets in \(\binom{[n]}{k}\) containing \(t\) fixed elements) is indeed the only structure of \(\mathcal{F}\). The authors answer analogous questions when \(X=\left[\begin{smallmatrix}{V}\\ {k}\end{smallmatrix}\right]\) and \(X=S_n\) in Theorem 1.5 and Theorem 1.6. For certain ranges of family sizes, they provide structural characterizations for both families of subspaces and families of permutations having maximal total intersection numbers. To some extent, these results determine the unique structure of the optimal family for certain values of \(|\mathcal{F}|\) and characterize the relationship between having the maximal total intersection number and being intersecting. Besides in Theorem 1.7 and Theorem 1.8, they also show upper bounds on the total intersection numbers for both families of subspaces and families of permutations of given sizes using the linear programming method over association schemes.
- Intersection theorems for \(\{0,\pm1\}\)-vectors and \(s\)-cross-intersecting families
- The Erdős-Ko-Rado theorem for vector spaces
- Intersecting families of discrete structures are typically trivial
- The number of k-intersections of an intersecting family of r-sets
- An Erdős--Ko--Rado theorem for partial permutations
- A Hilton-Milner theorem for vector spaces
- A note on supersaturated set systems
- A quasi-stability result for dictatorships in S_n
- Algebraic Graph Theory
- Cayley graph on symmetric group generated by elements fixing k points
- Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs
- Compressions and probably intersecting families
- Disjoint pairs in set systems with restricted intersection
- Erdős-Ko-Rado theorems. Algebraic approaches
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 3341050 (Why is no real title available?)
- scientific article; zbMATH DE number 2232233 (Why is no real title available?)
- Intersecting families of discrete structures are typically trivial
- Intersecting families of permutations
- Intersecting families of permutations
- LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
- Lower bound on the dimensions or irreducible representations of symmetric groups and on the exponents of varieties of Lie algebras
- Most probably intersecting families of subsets
- On the maximum number of permutations with given maximal or minimal distance
- On the partition associated to the smallest eigenvalues of the k-point fixing graph
- Removal and stability for Erdős-Ko-Rado
- Shadows and intersections in vector spaces
- Stability for t-intersecting families of permutations
- Stable sets of maximal size in Kneser-type graphs
- Structure and supersaturation for intersecting families
- The Erdős-Ko-Rado theorem for vector spaces
- The Hook Graphs of the Symmetric Group
- The minimum number of disjoint pairs in set systems and related problems
- The representation theory of the symmetric groups
This page was built for publication: Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2133641)
