How different can two intersecting families be?

Balázs Patkós

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

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$.

Détail

DOI : 10.37236/1921

Classification : 05D05
Mots-clés : hypergraph