How Different Can Two Intersecting Families Be?

Abstract

To measure the difference between two intersecting families ${\cal F},{\cal G} \subseteq 2^{[n]}$ we introduce the quantity $D({\cal F} ,{\cal G})=|\{ (F,G):F \in {\cal F}, G \in {\cal G}, F\cap G =\emptyset \}|$. We prove that if ${\cal F}$ is $k$-uniform and ${\cal G}$ is $l$-uniform, then for large enough $n$ and for any $i \neq j$ ${\cal F}_i=\{F \subseteq [n]: i \in F, |F|=k \}$ and ${\cal F}_j=\{F \subseteq [n]: j \in F, |F|=l\}$ form an optimal pair of families (that is $D({\cal F},{\cal G}) \leq D({\cal F}_i,{\cal F}_j)$ for all uniform and intersecting ${\cal F}$ and ${\cal G}$), while in the non-uniform case any pair of the form ${\cal F}_i=\{F \subseteq [n]: i \in F \}$ and ${\cal F}_j=\{F \subseteq [n]: j \in F\}$ is optimal for any $n$.