Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations (Q2133641): Difference between revisions

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.