Cross-intersecting families and primitivity of symmetric systems (Q618301): Difference between revisions

Let \(X\) be a finite set and \(\mathfrak{p} \subseteq 2^X\) the power set of \(X\). The pair \((X, \mathfrak{p})\) is called a \(\mathfrak{p}\)-system, or a system for short, if the following three conditions hold. {\parindent=9mm \begin{itemize}\item[(i)]If \(A \in \mathfrak{p}\) and \(B \subset A\), then \(B \in \mathfrak{p}\). \item[(ii)]For \(A \in 2^X\) with \(|A| \geq 2\), \(A \in \mathfrak{p}\) if \(\{x,y\} \in \mathfrak{p}\) for any \(x,y \in A\) with \(x \not= y\). \item[(iii)]For every \(x \in X\), \(\{x\} \in \mathfrak{p}\). \end{itemize}} Given a system \((X, \mathfrak{p})\), we can construct a simple graph, denoted \(G(X, \mathfrak{p})\), whose vertex set is \(X\), and \(\{a,b\}\) is an edge if and only if \(\{a,b\} \not \in \mathfrak{p}\). We call \((X, \mathfrak{p})\) connected (disconnected) if the graph \(G(X, \mathfrak{p})\) is connected (disconnected). An element of \(\mathfrak{p}\) is also called a \(\mathfrak{p}\)-subset of \(X\). A family \(\{A_1, A_2, \dots ,\) \(A_m\} \subseteq 2^X\) is said to be a cross-\(\mathfrak{p}\)-family over \(X\) if \(\{a,b\} \in \mathfrak{p}\) for any \(a \in A_i\) and \(b \in A_j\) with \(i \not= j\). Let \(\alpha(X, \mathfrak{p})\) denote \(\max \{|A| : A \in \mathfrak{p}\}\). We call a system \((X, \mathfrak{p})\) symmetric if there is a group \(\Gamma\) transitively acting on \(X\) and preserving the property \(\mathfrak{p}\), i.e., for every pair \(a,b \in X\) there is a \(\gamma \in \Gamma\) such that \(b = \gamma(a)\), and \(A \in \mathfrak{p}\) implies \(\delta(a) \in \mathfrak{p}\) for every \(\delta \in \Gamma\). The main result established in this paper is the following. Let \((X, \mathfrak{p})\) be a connected symmetric system, and let \(\{A_1, A_2, \dots ,\) \(A_m\}\) be a cross-\(\mathfrak{p}\)-family over \(X\) with \(A_1 \not= \emptyset\). Then \[ \sum^m_{i=1}|A_i| \leq \begin{cases} |X| & \text{ if \(m \leq \frac{|X|}{\alpha(X, \mathfrak{p})}\)}; \\ m \alpha (X, \mathfrak{p}) & \text{ if \(m \geq \frac{|X|}{\alpha(X, \mathfrak{p})}\)}. \end{cases} \] Moreover, the primitivity of symmetric systems is introduced to fully characterize when the upper bound is attained. This result generalizes Hilton's theorem on cross-intersecting families of finite sets, and provides analogs for cross-\(t\)-intersecting families of finite sets, finite vector spaces, and permutations, etc.