\documentclass[12pt]{article}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\textheight}{8.7in}
\setlength{\textwidth}{6.3in}
\usepackage{latexsym,amssymb,amsmath}
\setlength{\topmargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}

\makeatletter
\newfont{\footsc}{cmcsc10 at 8 truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10 truept}
\renewcommand{\ps@plain}{%
\renewcommand{\@oddfoot}{\footsc the electronic journal of
  combinatorics {\footbf 12} (2005), \#R24\hfil\footrm\thepage}}
\makeatother
\pagestyle{plain}

\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
\newcommand{\D}{\Delta}
\newcommand{\N}{{\cal N}}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}

\title{{How different can two 
intersecting families be?}}

\author{Bal\'azs Patk{\'o}s\\
\small Department of Mathematics and its Applications\\[-0.8ex]
\small Central European University, Budapest, Hungary\\[-0.8ex]
\small \texttt{patkos@renyi.hu}}

\date{\small
Submitted: Mar 7, 2005; Accepted: May 9, 2005; Published: May 16, 2005\\
\small Mathematics Subject Classification: 05D05}

\begin{document}
\maketitle

\begin{abstract}
To measure the difference between two intersecting families $\F,\G
  \subseteq 2^{[n]}$ we introduce the quantity $D(\F ,\G)=|\{ (F,G):F \in \F, 
G \in \G, F\cap G =\emptyset \}|$. We prove that if $\F$ is $k$-uniform and
$\G$ is $l$-uniform, then for large enough $n$ and for any $i
\neq j$ $\F_i=\{F \subseteq [n]: i \in
F, |F|=k \}$ and $\F_j=\{F \subseteq [n]: j \in F,
|F|=l\}$  form an optimal pair of families (that is 
$D(\F,\G) \leq D(\F_i,\F_j)$ for all uniform and intersecting $\F$
and $\G$), while in the non-uniform case any pair of the form 
$\F_i=\{F \subseteq [n]: i \in F \}$ and $\F_j=\{F \subseteq [n]: j
\in F\}$ 
is optimal for any $n$.
\end{abstract}
\section{Introduction}
To answer the question of the title, we first have to find out how to measure
the difference between two intersecting set systems 
$\F,\G \subseteq 2^{[n]}$. If for any $F \in \F$ and $G \in \G$ we have $F \cap
G \neq \emptyset$, then $\F \cup \G$ is still an intersecting system of sets,
so $\F$ and $\G$ are not really different as they are subfamilies of the same
maximal intersecting family. So the evidence of being different (at least in
this sense) is a pair $(F,G): F \in \F, G \in \G, F \cap G =
\emptyset$. Therefore it seems natural to introduce
$$D(\F ,\G)=|\{ (F,G):F \in \F, G \in \G, F\cap 
G =\emptyset \}|$$ to measure the difference between $\F$ and $\G$. Our
purpose is to get optimal set systems $\F^*, \G^*$ (i.e. ones with the 
following property: $D(\F,\G) \leq D(\F^*,\G^*)$ for any pair of intersecting
families).

In fact, we will handle two different cases: first, when 
there is a restriction 
on the cardinality of the sets belonging to $\F$ and 
$\G$ ($\F$ and $\G$ will 
be uniform set systems), and secondly, when there is 
not. In both cases one can consider
these hypergraphs:
$$\F_i=\{F \subseteq [n]: i \in F\}$$
Observe that, when considering the pair $\F_i,\F_j$, all the sets
containing 
both $i$ and $j$ are not contained in any disjoint
pairs, so the $D$-number won't decrease if we throw these sets away getting
$$\F_{i,j} =\{F \subseteq [n]:i \in F, j \notin F\},  
\F_{j,i} =\{F \subseteq
[n]: j \in G, i \notin G\}$$
These pairs of hypergraphs will be referred as the 
conjectured hypergraphs/set
systems. In section 2, we will show that in the uniform
 case the conjectured
set systems fail to be maximum with respect to 
$D(\F , \G)$ for small $n$, but
they are optimal if $n$ is large enough 
(depending on the cardinality of the
elements of $\F$ and $\G$). Note that in the uniform case
$D(\F_i,\F_j)=D(\F_{i,j},\F_{j,i})={n-2 \choose k-1}{n-k-1 \choose
  l-1}$. In section 3, we will prove 
that in the non-uniform
case the conjectured set systems are optimal for all $n$. This time 
$D(\F_i,\F_j)=D(\F_{i,j},\F_{j,i})=3^{n-2}$, because when considering
a disjoint pair of sets $F_i \in \F_{i,j}, F_j \in \F_{j,i}$, then any $k \in [n]
\setminus \{i,j\}$ can be either in $F_i$ or in $F_j$ or in none of them. 

\section{The Uniform Case}

Throughout this section we will assume that $\F$ is 
$k$-uniform and $\G$ is
$l$-uniform. Now if $k+l> n$, then there are no 
disjoint $k$ and $l$
element subsets. 

If $k+l\leq n$, but, say, $l > {n \over 2}$, then any 
two
$l$-element subsets meet each other. For any fixed 
$k$-element subset there are
${n-k \choose l}$ $l$-element subsets disjoint from this 
fixed set. So the best
one can do is to let $\F$ be the largest intersecting 
$k$-uniform set system,
and let $\G$ consist of all $l$-element subsets disjoint 
from at least one set
in $\F$. The Erd\H{o}s-Ko-Rado theorem \cite{EKR} says 
that $\F$ should be all $k$-element
sets containing a fixed element, so then $\G$ should be all 
$l$-element sets not
containing this fixed element. Thus in this case the conjectured set 
systems are not optimal.

If $2k=n$ and $k=l$ then any set has only one disjoint 
pair (considering now
only the $k$-element sets), its complement. So one can 
put from each pair one
set into $\F$ and one into $\G$, and since in this way 
subsets containg $1$
{\it and} $n$ together (or containing none of them) will 
be put into $\F$ or
$\G$, these families will have more disjoint pairs, than 
the conjectured
systems (and clearly will be maximal ones).

Despite these failures of the conjectured systems, one can 
state the following
\vskip 0.3truecm
{\bf Theorem 2.1.}
{\it For any $k$ and $l$, there exists an $n(k,l)$ such that if
$n \geq n(k,l)$ and $\F$, $\G$ are $k$ and $l$-uniform 
hypergraphs , then $D(\F,\G)\leq D({\F_0,\G_0})$ where
${\F_0,\G_0}$ are the conjectured hypergraphs.}
\vskip 0.1truecm
{\bf Proof:} Case A \hskip 0.2truecm $\bigcap \F \neq 
\emptyset$
and $\bigcap \G \neq \emptyset$. 
\vskip 0.15truecm
In this case $\bigcap \F$ and 
$\bigcap \G$ must be disjoint, since otherwise there 
would be no disjoint sets in $\F$ and $\G$. Let's pick an
$i \in \bigcap \F$ and a $j \in \bigcap \G$, and add 
$\{F \subseteq [n]: i \in F\}$ to $\F$ and $\{G \subseteq 
[n]:j \in G\}$ to $\G$. In this way we get the 
conjectured hypergraphs, and clearly $D(\F,\G)$ can't 
decrease.
\vskip 0.2truecm
Case B \hskip 0.2truecm $\bigcap \F =\emptyset$. (or similarly $\bigcap \G =\emptyset$)
\vskip 0.15truecm
Observe
the following two things: 

1, if $n \geq k+2l$ then again by \cite{EKR} one gets 
that for a fixed $F \in \F$ the number of sets in $\G$ 
from which $F$ is disjoint is at most 
${n-k-1 \choose l-1}$, which is the case in the 
conjectured hypergraphs for all sets in $\F_{i,j}$. So if 
$|\F|\leq |{\F_{i,j}}|= {n-2 \choose k-1}$ then we are 
done.

2, Since $\bigcap \F =\emptyset$ then as a special case 
of Theorem3 of \cite{HM} we get that 
$$|\F|\leq 1+{n-1 \choose k-1}- {n-k-1 \choose k-1}$$
and as for large enough $n$
$${n-2 \choose k-1} > 1+{n-1 \choose k-1}- {n-k-1 \choose 
k-1}$$
holds, by the remark made after the first observation 
we are done.
$\square$
\section{The Non-Uniform Case}
Considering the non-uniform case one can assume that the
pair $(\F,\G)$ is maximal with respect to the property
that all $F \in \F$ have at least one $G \in \G$ disjoint
from it (and the same holds for any $G \in \G$). First we state our main
theorem. 
\vskip0.3truecm
{\bf Theorem 3.1.} {\it For any  $\F, \G \subseteq 2^{[n]}$ and for any $n\geq
2$, 
$D(\F,\G) \leq D(\F_{i,j},\F_{j,i})$ holds, where $\F_{i,j},\F_{j,i}$
are one of the conjectured pairs.}
\vskip 0.1truecm
{\bf Proof:} We begin with
\vskip 0.2truecm
{\bf Claim 3.2.} {\it $F \in \F \Leftrightarrow F^c \in \G$, 
where $F^c$ denotes the complement of $F$.}
\vskip 0.1truecm
{\bf Proof:} If $F \in \F$ then there is some $G \in \G$ 
such that $F\cap G =\emptyset$. This means $G \subseteq
F^c$, and as $G$ meets all sets in $\G$, $F^c$ meets 
them, too. So by maximality $F^c \in \G$. The other 
direction follows, since we can change the role of $\F$
and $\G$. $\square^{3.2.}$
\vskip 0.2truecm
By virtue of the above claim, we can ``forget about'' 
$\G$. But what should we count, and are there any 
additional conditions on $\F$? Concerning the first 
question: as for a fixed $F$ we counted the $G$s 
disjoint from it, and since $F\cap G =\emptyset 
\Leftrightarrow F \subseteq G^c$, by the claim we get, 
that now for a fixed $F$ we should count the number of
$F' \in \F: F \subseteq F'$. (Note that $F \subseteq F$ also
counts, because this is for the pair $(F, F^c)$!)
Let's denote this number by 
$\rho_{\F}(F)$ (and we will omit $\F$ from the index, if it is clear from the
context), and put $\rho (\F)=\sum_{F \in \F}\rho_{\F}(F)$.

Now to the other question: since by the above claim we 
know that
$\G=\F^c=\{F^c:F \in \F \}$ and the original conditions
were that both $\F$ and $\G$ should be intersecting, 
we get that $\F$
should be intersecting {\it and} co-intersecting. So we 
conclude the following
\vskip 0.2truecm
{\bf Claim 3.3.} {\it max$\{D(\F,\G): \F,\G$ are 
intersecting$\}=\max \{\rho(\F):\F$ is intersecting and
co-intersecting$\}$.} $\square$
\vskip 0.2truecm
By this claim
we are left to show that $\rho(\F)\leq \rho({\F_{i,j}})$ 
whenever $\F$ is an intersecting and co-intersecting 
family.

Now note that, when counting $\rho(\F)$ one counts the 
pairs $(F,F')$ where $F,F'\in \F$ and $F \subseteq F'$.
But this can be done from the point of view of $F'$, that
is, if we put $\delta_{\F}(F')=|\{F \in \F: F' \supseteq F\}|$ 
and $\delta(\F)=\sum_{F \in \F}\delta_{\F}(F)$, then $\rho(\F)
=\delta(\F)$. With this remark we are able to prove
\vskip 0.3truecm
{\bf Lemma 3.4.} {\it If $\F$ is intersecting and 
co-intersecting, furthermore $\bigcap \F \neq \emptyset$,
then $\delta(\F)\leq \delta(\F_{i,j})$.}
\vskip 0.1truecm
{\bf Proof:} W.l.o.g. one can assume that $1 \in F$ for 
all $F \in \F$. Consider the hypergraph $\F^* =\{F 
\setminus \{1\}:F \in \F \}$. Since we removed $1$,
this need no longer be intersecting, but it is clearly 
co-intersecting on $[2,...,n]$, furthermore 
$\delta_{\F}(F)=\delta_{\F^*}(F\setminus \{1\})$.

It is well-known, that if a hypergraph is maximal 
co-intersecting, then it contains one set from any pair of 
complements, and if $F \subseteq F' \in \F^*$, then $F \in 
\F^*$. So $\delta_{\F^*}(F\setminus \{1\})=2^{|F\setminus 
\{1\}|}$, hence to obtain the largest $\delta(\F^*)$ one
should put the most possible large sets into $\F^*$. 
Again, by \cite{EKR}, we know that for fixed $k\geq {n-1
\over 2}$ we can put at most ${n-2 \choose k}$ 
$k$-element sets into $\F^*$, but in the case of any 
conjectured hypergraph (any $\F_{i,j}$, or as we assume now that $1
\in \bigcap \F$ any $\F_{1,j}$) exactly that many sets (now with $k+1$-elements, as we
put back $1$ to all the sets) are there. So for all $k$ we put the most
possible number of large sets into our family when considering the $k$ and
$n-1-k$-element complementing pairs. $\square^{3.4.}$
\vskip 0.2truecm
So we will be done, if we can prove
\vskip 0.2truecm
{\bf Lemma 3.5.} {\it For any intersecting and co-intersecting
family $\F$, there exists another $\F'$ with $\bigcap
\F' \neq \emptyset$ and $\rho(\F)\leq \rho(\F')$.}
\vskip 0.2truecm
Before starting the proof of Lemma 3.5., we introduce some
notation: the shift operation $\tau_{i,j}$ is defined by
\begin{eqnarray}
\tau_{i,j}(F)=\left\{
\begin{array}{cc} %rr ll cr lc
F\setminus \{j\} \cup \{i\} & \textnormal{if}\ ~ j \in F,
i \notin F \textnormal{and} F\setminus \{j\} \cup \{i\} \notin \F\\
F & \textnormal{otherwise}
\end{array}
\right.
\end{eqnarray}
Put $\tau_{i,j}(\F)=\{\tau_{i,j}(F):F \in \F \}$.
\vskip 0.1truecm
It is well-known that the shift operation preserves 
the intersecting and co-intersect\-ing property.  It is also known, that 
starting from any family of sets, performing finitely many shift operation, 
one can obtain a so-called {\it left-shifted} family, that is a 
family for which $\tau_{i,j}(\F)=\F$ for all $i<j$. So 
in what follows, we can assume that $\F$ is left-shifted, if we can prove the
following
\vskip 0.1truecm
{\bf Claim 3.6.} {\it $\rho(\F)\leq \rho(\tau_{i,j}(\F))$.}

{\bf Proof:} We will consider how $\rho(F)$ changes when performing the
operation $\tau_{i,j}$.

Case A \hskip 0.2truecm If $i,j \in F$ or $i,j \notin F$, then $\tau_{i,j}(F)=F$ and for all $F'
\in \F$ with $F \subseteq F'$ we have $F \subseteq \tau_{i,j}(F')$. So
$\rho_{\F}(F) \leq \rho_{\tau_{i,j}(\F)}(F)=
\rho_{\tau_{i,j}(\F)}(\tau_{i,j}(F))$. 
\vskip 0.2truecm
Case B \hskip 0.2truecm Let $A \subseteq [n]$ with $i,j \notin A$. Put $F=A \cup \{i\}$ and $F'=A
\cup \{j\}$. 
\vskip 0.15truecm
Subcase B1 \hskip 0.2truecm $F \in \F, F' \notin \F$

Now for all $G \supseteq F$ $i \in G$, therefore $G=\tau_{i,j}(G)\supseteq
\tau_{i,j}(F)=F$, thus $\rho_{\F}(F) \leq
\rho_{\tau_{i,j}(\F)}(F)=\rho_{\tau_{i,j}(\F)}(\tau_{i,j}(F))$. 
\vskip 0.15truecm
Subcase B2 \hskip 0.2truecm $F \notin \F, F' \in\F$

Now $\tau_{i,j}(F')=F$, and if $F' \subset G \in \F$ with $i \notin G$, then
$(G \setminus \{j\} \cup \{i\})=G' \in \tau_{i,j}(\F)$ and clearly $F \subseteq
G'$. If $F' \subseteq G$ with $i,j \in G$, then $G=\tau_{i,j}(G) \supseteq F$,
thus we conclude, that $\rho_{\F}(F') \leq \rho_{\tau_{i,j}(\F)}(F)=
\rho_{\tau_{i,j}(\F)}(\tau_{i,j}(F'))$.
\vskip 0.15truecm
Subcase B3 \hskip 0.2truecm $F,F' \in \F$ (thus $\tau_{i,j}(F)=F,\tau_{i,j}(F')=F'$)

Now let $G \in \F$ contain at least one of $F,F'$. If $i \in G$, then
$\tau_{i,j}(G)=G$ contains as many of $F,F'$ as before performing the
$\tau$-operation. Otherwise $i \notin G, j \in G$ and $G$ contains only $F'$.
So, putting $G'=G \setminus \{j\} \cup \{i\}$, if $G' \notin \F$, then
$\tau_{i,j}(G)=G'$ and $G' \supseteq F$, while if $G' \in\F$, then
$\tau_{i,j}(G)=G$ and still $F' \subseteq G$. So we get $\rho_{\tau_{i,j}(\F)}(F)+
\rho_{\tau_{i,j}(\F)}(F') \geq \rho_{\F}(F)+ 
\rho_{\F}(F')$. 
\vskip 0.2truecm
So for sets of type of the first case $\rho(F)$ doesn't decrease, and we can
partition the sets of type of the second case into  ``pairs" (of which one may be
missing) for which the sum of $\rho(F)$s doesn't decrease.
$\square^{3.6.}$ 
\vskip 0.2truecm
Further notations:
$$\F +\G =\{F \cup G:F\in \F, G \in \G\}, \hskip 0.1truecm \F - \G 
=\{F \setminus G: F \in\F,  G \in \G \}$$ 
$$\D \F =\F - \F;\hskip 0.2truecm \textnormal{Sub}\F=\{S:S \subseteq F \in \F\}$$
And we will write ${\bf 1}+\F$ if $\G$ consists of one single set containing
only $1$.

Now we can return to the proof of Lemma 3.5. In the proof
we will use the basic ideas of \cite{MSch}.
\vskip 0.1truecm
{\bf Proof of Lemma 3.5.} For arbitrary $\F$ intersecting and co-intersecting
family we have to define another one of which each set has an element in 
common. Now let $\F=\F^0 \cup^* \F^1$, where $\F^1 = \{F \in \F: 1 \in F\}$
and $\F^0 =\{F \in \F: 1 \notin F\}$. Put $\F'=\F^1 \cup ({\bf 1}+
\textnormal{Sub}  \F^0)$.

We have to prove that i, $\bigcap \F' \neq \emptyset$ (and therefore it is 
intersecting), ii, $\F'$ is co-intersecting and iii, $\rho(\F')\geq \rho(\F)$.
 
i, is clear, as by definition $1 \in F$ for all $F \in \F'$.
\vskip 0.1truecm
To prove ii, we will use that $\F$ is left-shifted (and maximal).

{\bf Claim 3.7.} {\it ${\bf 1}+\F^0 \subset \F^1$}

{\bf Proof:} Since for any $F \in \F^0$ $F'=\{1\}\cup F \supset
F$, $F'$ meets all sets in $\F$. We have to show, that there is no $G \in \F$
such that $F' \cup G=[n]$. Suppose to the contrary that such a $G$
exists. Note that $1 \notin G$, because otherwise $G \cup F=[n]$ would hold,
contradicting the co-intersecting property of $\F$. Now as $\F$ is
intersecting, there is $j \in F \cap G$. But since $\F$ is left-shifted, 
$G\setminus \{j\} \cup \{1\}=G' \in \F$. But then $G' \cup F =[n]$ would hold
- a contradiction. $\square^{3.7.}$
\vskip 0.1truecm
By Claim 3.7. we know that all new
sets in $\F'$ are subsets of one of the old sets (that is a set from $\F$), 
therefore as $\F$ was co-intersecting, so is $\F'$.
\vskip 0.1truecm
It remains to prove iii,. For this purpose we will define an injective mapping 
$f:\F^0 \rightarrow {\bf 1}+\D \F^0$ (observe that $\D \F^0 \subseteq
\textnormal{Sub}\F^0$!) such that for all $F \in \F^0$
$\rho_{\F'}(f(F))\geq \rho_{\F}(F)$. This is clearly enough, because $\F^1
\subseteq \F'$, so $\rho (F)$ can't decrease for any $F \in \F^1$ (and if
$F_1,F_2 \in \F^0$, then $\{1\} \cup F_1 \setminus F_2$ is disjoint from $F_2$,
so, by the intersecting property of $\F$, it is not an element of $\F^1$, so
we won't count twice any $\rho(F)$).

To define $f$ (using the notation of \cite{MSch}) let $k=\min \{|I|: I=F_1
\cap F_2; F_1,F_2 \in \F^0\}$ (note, that $I$ is not empty, as $\F$ is
intersecting!) and fix $F_1,F_2$ with $I=F_1 \cap F_2: |I|=k$.

Now consider the following partition of $\F^0$: $$\C =\{F \in \F^0: I
\not\subseteq F  \}; \A=\{ F \in \F^0: I \subseteq F, \textnormal{there
  is}\ F' \in \F^0 \hskip 0.1truecm \textnormal{with}\ F \cap F'=I\};$$
$$ \B=\F^0 \setminus (\A \cup \C)$$
For a better understanding, $F \in \B$ if $I \subset F$ and whenever 
there is a set $F' \in \F^0$ with $I \subseteq F'$, then $F$ should meet
$F'$ outside $I$, as well. 
Note that $\A$ is not empty, since $F_1,F_2 \in
\A$. Now for any $A\in \A$ let $f(A)=(A \setminus I)\cup \{1\}$. (Observe that
 for any $A \in \A$ there is $A'\in \A \subseteq \F^0$ with $A \cap
A' =I$, $A \setminus I= A \setminus A'$, so $f(A) \in {\bf 1}+\D \F^0$ as
required!) As all $A \in \A$ contain $I$, $f$ is injective restricted to $\A$.

To show that $\rho_{\F'}(f(A))\geq \rho_{\F}(A)$, observe that $f(A) \subset A \cup
\{1\}$. Therefore if $A \subset F \in \F$ and $1 \in F$ (that is $F \in \F^1$,
therefore $F \in \F'$, too) , then $f(A) \subset F$, as well, so the part of
$\rho(A)$ which comes from the $F$s in $\F^1$ can't decrease. 

We have to
handle the sets $A \subset F \in \F^0$. To do this let $(F \setminus I)\cup
\{1\}=F'$. Then $F' \in \F'$ and $f(A) \subseteq F'$ by definition. If $F\neq G$ then $F'
\neq G'$, because we took the same set $I$ away from both (and $I \subseteq F,G$), and $1$ was
neither in $F$ nor in $G$. We still have to point out that $F'$ is not equal
to any $G \in F^1$ , $G$ containing $A$ for
any $F \in \F^0$ (because in that case we would take into account that
containing relation twice when counting $\rho(f(A))$). But this is
clear, because a $G$ of this form contains $I$ (as $I \subseteq A$), and $F'
\cap I = \emptyset$ by definition (and as we pointed out $I$ is not empty).
\vskip 0.2truecm
To finish the proof we need to continue this procedure now considering the
remaining sets, that is $\B \cup \C$. So we define a new $I'$ and a new $k'$ 
now only considering sets in $\B \cup \C$, then get a new partition 
$\A',\B',\C'$ with respect to this new $I'$ and new $k'$, and define 
$f$ on $\A'$ with the help of $I'$, and then start again with $\B' \cup
\C'$... This procedure ends after finitely many steps, as the $\A$s are never
empty, so there is strictly less and less remainder. In each step $f$ is
injective, the only difficulty is to assure for sets $A,B$ on which
 $f$ is defined at different steps $f(A)=f(B)$ can't happen. 
This is clearly done by
\vskip 0.1truecm
{\bf Claim 3.8.} {\it $(\A - \{I\}) \cap \D (\B \cup \C) = \emptyset$}
\vskip 0.1truecm
$\A - \{I\}$ is the set of the $f$-images defined at a step (if we don't count
1, which is an element of all images). For a set $B$ on
which $f$ is defined later, the image  is of the form $B \setminus I'= B
\setminus B'$ (again without 1), so it is in $\D (\B \cup \C)$. Therefore by
the claim we will be really done.
\vskip 0.1truecm
{\bf Proof:} This is in fact the lemma in \cite{MSch}, but to be
self-contained we repeat the proof. 
\vskip 0.1truecm
Case1: $A \in \A, B \in \B, F \in \B \cup \C$. 

By the definition of $\B$, 
$B$ must meet $A$ outside of $I$, too. Therefore $F\setminus B$ doesn't
contain this (these) element(s), while $A \setminus I$ does.
\vskip 0.1truecm
Case2: $A \in \A, C \in \C, F \in \B \cup \C$

By the definition of $\C$, $C$ doesn't contain $I$, therefore by the 
minimality of $|I|$, $C$ must meet $A$ outside of $I$, too. The rest is as in
Case1. $\square^{3.8.}$ $\square^{3.5.}$ $\square^{3.1.}$

\vskip 0.5truecm

{\bf Acknowledgments.} I would like to thank Gyula Katona for
proposing me the problem and for helpful discussions and \'Akos
Kisv{\"o}lcsey for his useful remarks on the first version of this paper. I 
would also like to thank the anonymous referee for his/her comments on the 
presentation of the proofs.

Research supported by the Hungarian National Research Fund 
(OTKA) T046991.
\begin{thebibliography}{99}
\bibitem{EKR}
P. Erd\H{o}s, Chao Ko, R. Rado, Intersection theorems for 
systems of finite sets, Quart. J. Math. Oxford (2), 12 
(1961) 313-318.
\bibitem{HM}
A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems on finite
sets, Quart. J. Math. Oxford (2), 18 (1967) 369-384.
\bibitem{MSch}
J. Marica and J. Sch{\"o}nheim, Differences of sets and a 
problem of Graham, Can. Math. Bull. 12 (1969) 635-637
\end{thebibliography}
\end{document}

.