Disjoint pairs in set systems with restricted intersection

Abstract

The problem of bounding the size of a set system under various intersection restrictions has a central place in extremal combinatorics. We investigate the maximum number of disjoint pairs a set system can have in this setting. In particular, we show that for any pair of set systems $(\mathcal{A},\mathcal{B})$ which avoid a cross-intersection of size $t$, the number of disjoint pairs $(A,B)$ with $A\in \mathcal{A}$ and $B\in \mathcal{B}$ is at most ${\sum }_{k=0}^{t-1}\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{n-k}$. This implies an asymptotically best possible upper bound on the number of disjoint pairs in a single $t$-avoiding family $\mathcal{F}\subset \mathcal{P}[n]$. We also study this problem when $\mathcal{A}$, $\mathcal{B}\subset [n{]}^{(r)}$ are both $r$-uniform, and show that it is closely related to the problem of determining the maximum of the product $|\mathcal{A}||\mathcal{B}|$ when $\mathcal{A}$ and $\mathcal{B}$ avoid a cross-intersection of size $t$, and $n\ge n_0(r,t)$.

arXiv comment18 pages