Cross-intersecting families and primitivity of symmetric systems
(Citations: 3)
Let $X$ be a finite set and $\mathfrak p\subseteq 2^X$, the power set of $X$,
satisfying three conditions: (a) $\mathfrak p$ is an ideal in $2^X$, that is,
if $A\in \mathfrak p$ and $B\subset A$, then $B\in \mathfrak p$; (b) 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\neq y$; (c) $\{x\}\in \mathfrak p$ for every $x\in X$. The
pair $(X,\mathfrak p)$ is called a symmetric system if there is a group
$\Gamma$ transitively acting on $X$ and preserving the ideal $\mathfrak p$. A
family $\{A_1,A_2,\ldots,A_m\}\subseteq 2^X$ is said to be a
cross-$\mathfrak{p}$-family of $X$ if $\{a, b\}\in \mathfrak{p}$ for any $a\in
A_i$ and $b\in A_j$ with $i\neq j$. We prove that if $(X,\mathfrak p)$ is a
symmetric system and $\{A_1,A_2,\ldots,A_m\}\subseteq 2^X$ is a
cross-$\mathfrak{p}$-family of $X$, then \[\sum_{i=1}^m|{A}_i|\leq\left\{
\begin{array}{cl} |X| & \hbox{if $m\leq \frac{|X|}{\alpha(X,\, \mathfrak p)}$,}
\\ m\, \alpha(X,\, \mathfrak p) & \hbox{if $m\geq \frac{|X|}{\alpha{(X,\,
\mathfrak p)}}$,} \end{array}\right.\] where $\alpha(X,\, \mathfrak
p)=\max\{|A|:A\in\mathfrak p\}$. This 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.
Moreover, the primitivity of symmetric systems is introduced to characterize
the optimal families.