no. 13 · Wednesday 11 November 2026
Beyond Frankl's conjecture: Maximum sum of sizes of cross-intersecting families with restricted conditions
Abstract
Let $\mathcal{F}$ and $\mathcal{G}$ be two families of subsets of $[n]$. We say that $\mathcal{F}$ and $\mathcal{G}$ are \emph{cross-intersecting} if $F \cap G \neq \emptyset$ for all $F \in \mathcal{F}$ and $G \in \mathcal{G}$. Let $n, k_1, k_2, m, r, t$ be positive integers satisfying $n > k_1 + k_2$. Suppose that $\mathcal{F} \subseteq \binom{[n]}{k_1}$ and $\mathcal{G} \subseteq \binom{[n]}{k_2}$ are two cross-intersecting families such that $\left\{F \in \binom{[n]}{k_1} : |F \cap [m]| \geq r\right\} \subseteq \mathcal{F}$ and $\mathcal{F}$ is $t$-intersecting. In this paper, we determine the maximum sum $|\mathcal{F}| + |\mathcal{G}|$ under these assumptions. By taking $k_1=k_2+t-1$, $m = k_2+t+s-1$ and $r=k_2+t-1$ for $s\ge 0$, our result recovers a conjecture of Frankl \cite{frankl2016new}, which was recently confirmed by Wu, Feng, and Li \cite{wu2025proof}. Further, we establish a complete characterization of all extremal families. Our approach extends the Ahlswede–Khachatrian generating set method to handle the simultaneous constraints of cross-intersection and $t$-intersection, subject to additional structural conditions.
- comments
- 26 pages
- fields
- Combinatorics