Structural results for conditionally intersecting families and some applications

Xizhi Liu¹

¹University of Illinois at Chicago, Department of Mathematics, Statistics, and Computer Science

The electronic journal of combinatorics, Tome 27 (2020) no. 2

Résumé

Let $k\ge d\ge 3$ be fixed. Let $\mathcal{F}$ be a $k$-uniform family on $[n]$. Then $\mathcal{F}$ is $(d,s)$-conditionally intersecting if it does not contain $d$ sets with union of size at most $s$ and empty intersection. Answering a question of Frankl, we present some structural results for families that are $(d,s)$-conditionally intersecting with $s\ge 2k+d-3$, and families that are $(k,2k)$-conditionally intersecting. As applications of our structural results we present some new proofs to the upper bounds for the size of the following $k$-uniform families on $[n]$: (a) $(d,2k+d-3)$-conditionally intersecting families with $n\ge 3k^5$; (b) $(k,2k)$-conditionally intersecting families with $n\ge k^2/(k-1)$; (c) Nonintersecting $(3,2k)$-conditionally intersecting families with $n\ge 3k\binom{2k}{k}$. Our results for $(c)$ confirms a conjecture of Mammoliti and Britz for the case $d=3$.

Détail

DOI : 10.37236/8894

Classification : 05D05, 05C65, 05C35
Mots-clés : extremal set theory, intersecting sets, Erdős-Ko-Rado theorem