Size and structure of large \((s,t)\)-union intersecting families

Ali Taherkhani¹

¹Institute for Advanced Studies in Basic Sciences(IASBS)

The electronic journal of combinatorics, Tome 29 (2022) no. 2

Résumé

A family $F$ of $k$-sets on an $n$-set $X$ is said to be an $(s,t)$-union intersecting family if for any $A_1,\ldots,A_{s+t}$ in this family, we have $\left(\cup_{i=1}^s A_i\right)\cap\left(\cup_{i=1}^t A_{i+s}\right)\neq \varnothing.$ The celebrated Erdős-Ko-Rado theorem determines the size and structure of the largest intersecting (or $(1,1)$-union intersecting) family. Also, the Hilton-Milner theorem determines the size and structure of the second largest $(1,1)$-union intersecting family of $k$-sets. In this paper, for $t\geq s\geq 1$ and sufficiently large $n$, we find out the size and structure of some large and maximal $(s,t)$-union intersecting families. Our results are nontrivial extensions of some recent generalizations of the Erdős-Ko-Rado theorem such as the Han and Kohayakawa theorem~[Proc. Amer. Math. Soc. 145 (2017), pp. 73--87] which finds the structure of the third largest intersecting family, the Kostochka and Mubayi theorem~[Proc. Amer. Math. Soc. 145 (2017), pp. 2311--2321], and the more recent Kupavskii's theorem [arXiv:1810.009202018, (2018)] whose both results determine the size and structure of the $i$th largest intersecting family of $k$-sets for $i\leq k+1$. In particular, when $s=1$, we confirm a conjecture of Alishahi and Taherkhani [J. Combin. Theory Ser. A 159 (2018), pp. 269--282]. As another consequence, our result provides some stability results related to the famous Erdős matching conjecture.

Détail

DOI : 10.37236/10490

Classification : 05D05
Mots-clés : Erdős-Ko-Rado theorem, Hilton-Milner theorem, Kupavskii's theorem