Let
X = {1, . . . ,
n}, and let
$
{\user1{A}}
$
{\user1{A}}
be a family of subsets
of
X. Given the size of
$
{\user1{A}}
$
{\user1{A}}
, at least how many pairs
of elements of
$
{\user1{A}}
$
{\user1{A}}
must be disjoint? In
this paper we give a lower bound for the number of disjoint
pairs in
$
{\user1{A}}
$
{\user1{A}}
. The bound we obtain is
essentially best possible. In particular, we give a new proof of
a result of Frankl and of Ahlswede, that if
$
{\user1{A}}
$
{\user1{A}}
satisfies
$
{\left| {\user1{A}} \right|} = {\left| {X^{{{\left( { \geqslant r} \right)}}} } \right|}
$
{\left| {\user1{A}} \right|} = {\left| {X^{{{\left( { \geqslant r} \right)}}} } \right|}
then
$
{\user1{A}}
$
{\user1{A}}
contains at least as
many disjoint pairs as
X($
{\user1{A}} \subset X^{{{\left( r \right)}}}
$
{\user1{A}} \subset X^{{{\left( r \right)}}}
: then we are asking for
the minimum number of edges spanned by a subset of the Kneser
graph of given size. We make a conjecture on this lower bound,
and disprove a related conjecture of Poljak and Tuza on the
largest bipartite subgraph of the Kneser graph.