Proof of Frankl's conjecture on cross-intersecting families

Yongjiang Wu; Lihua Feng; Yongtao Li

doi:10.1016/j.jcta.2025.106062

paper

Proof of Frankl's conjecture on cross-intersecting families

arXiv:2411.09490 · doi:10.1016/j.jcta.2025.106062

Abstract

Two families $F$ and $G$ are called cross-intersecting if for every $F \in F$ and $G \in G$ , the intersection $F \cap G$ is non-empty. For any positive integers $n$ and $k$ , let $(k [ n ])$ denote the family of all $k$ -element subsets of ${1, 2, \dots, n}$ . Let $t, s, k, n$ be non-negative integers with $k \geq s + 1$ and $n \geq 2 k + t$ . In 2016, Frankl proved that if $F \subseteq (k + t [ n ])$ and $G \subseteq (k [ n ])$ are cross-intersecting families, and $F$ is $(t + 1)$ -intersecting and $∣ F ∣ \geq 1$ , then $∣ F ∣ + ∣ G ∣ \leq (k n) - (k n - k - t) + 1$ . Furthermore, Frankl conjectured that under an additional condition $(k + t [ k + t + s ]) \subseteq F$ , the following inequality holds: $∣ F ∣ + ∣ G ∣ \leq (k + t k + t + s) + (k n) - i = 0 \sum s (i k + t + s) (k - i n - k - t - s) .$ In this paper, we prove this conjecture. The key ingredient is to establish a theorem for cross-intersecting families with a restricted universe. Moreover, we derive an analogous result for this conjecture.

Final version, any comments are welcome

References in corpus (1)

Stabilities for non-uniform $t$ -intersecting families