Multi-part cross-intersecting families

Abstract

Let $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{a}\right)$ and $\mathcal{B}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{b}\right)$ be two families of subsets of $[n]$, we say $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting if $A\cap B\ne \varnothing$ for all $A\in \mathcal{A}$, $B\in \mathcal{B}$. In this paper, we study cross-intersecting families in the multi-part setting. By characterizing the independent sets of vertex-transitive graphs and their direct products, we determine the sizes and structures of maximum-sized multi-part cross-intersecting families. This generalizes the results of Hilton's and Frankl--Tohushige's on cross-intersecting families in the single-part setting.

17 pages