A note on non-empty cross-intersecting families

Menglong Zhang; Tao Feng

paper

A note on non-empty cross-intersecting families

arXiv:2306.04330

Abstract

The families $F_{1} \subseteq (k _{1} [ n ]), F_{2} \subseteq (k _{2} [ n ]), \dots, F_{r} \subseteq (k _{r} [ n ])$ are said to be cross-intersecting if $∣ F_{i} \cap F_{j} ∣ \geq 1$ for any $1 \leq i < j \leq r$ and $F_{i} \in F_{i}$ , $F_{j} \in F_{j}$ . Cross-intersecting families $F_{1}, F_{2}, \dots, F_{r}$ are said to be non-empty if $F_{i} \neq = \emptyset$ for any $1 \leq i \leq r$ . This paper shows that if $F_{1} \subseteq (k _{1} [ n ]), F_{2} \subseteq (k _{2} [ n ]), \dots, F_{r} \subseteq (k _{r} [ n ])$ are non-empty cross-intersecting families with $k_{1} \geq k_{2} \geq \dots \geq k_{r}$ and $n \geq k_{1} + k_{2}$ , then $\sum_{i = 1}^{r} ∣ F_{i} ∣ \leq max {(k _{1} n) - (k _{1} n - k _{r}) + \sum_{i = 2}^{r} (k _{i} - k _{r} n - k _{r}), \sum_{i = 1}^{r} (k _{i} - 1 n - 1)}$ . This solves a problem posed by Shi, Frankl and Qian recently. The extremal families attaining the upper bounds are also characterized.

14 pages