# Uniformly at Random

## Intersecting families of sets

leave a comment »

Let us consider some classical results concerning the combinatorics of finite sets. A family of subsets is called an intersecting family if every pair of subsets in the family has a non-empty intersection. The celebrated Erdos-Ko-Rado Theorem asserts that any intersecting family of k-element subsets of an n-element set contains at most $n-1 \choose k-1$ subsets. We shall however be concerned here with arbitrary intersecting families, rather than just the k-uniform families.

Let us first observe that an arbitrary intersecting family of subsets of an n-element set can have at most $2^{n-1}$ members. To see this, note that if a subset A is a member of the family, then its complement cannot possibly be a member. This observation leads immediately to the claimed bound.

Second, let us observe that any intersecting family can be extended, by the inclusion of additional subsets, to an intersecting family with $2^{n-1}$ members. To see this, observe that if an intersecting family ${\cal A}$ has fewer than $2^{n-1}$ members, then there must exist a set $A$ such that neither $A$ nor its complement $A'$ is in ${\cal A}$. If $A$ intersects every member of ${\cal A}$, then $A$ can be added to ${\cal A}$ to create a larger intersecting family. If there is a set $B \in {\cal A}$ disjoint from $A$, then, noting that $B$ must be contained in $A'$, we may add $A'$ to ${\cal A}$ to again obtain a larger intersecting family. We may repeat the process until we have enlarged ${\cal A}$ to a family with $2^{n-1}$ members.

Now, we shall call a family of subsets monotone increasing if, whenever $A$ is a member of the family, every superset of $A$ is also a member. Similarly, we shall call a family of subsets monotone decreasing if, whenever $A$ is a member of the family, every subset of $A$ is also a member. The following result is due to Kleitman.

Kleitman’s Lemma. Let ${\cal A,B}$ be monotone decreasing families of subsets of $\{1,\ldots,n\}$ and let ${\cal C,D}$ be monotone increasing families of subsets of $\{1,\ldots,n\}$. Then ${\cal |A||B|} \leq 2^n {\cal |A \cap B|}$ ${\cal |C||D|} \leq 2^n {\cal |C \cap D|}$ ${\cal |A||C|} \geq 2^n {\cal |A \cap C|}$.

The result clearly holds when $n=1$, so let us suppose $n>1$. Let ${\cal A}_1$ be the family consisting of all members of ${\cal A}$ not containing $n$, and let ${\cal A}_2 = \{A \setminus \{n\}: A \in {\cal A}, n \in A\}$. Let ${\cal B}_1$ and ${\cal B}_2$ be defined analogously.

Now, ${\cal |A \cap B|} = |{\cal A}_1 \cap {\cal B}_1| + |{\cal A}_2 \cap {\cal B}_2|$ $\geq |{\cal A}_1||{\cal B}_1|/2^{n-1} + |{\cal A}_2||{\cal B}_2|/2^{n-1}$ (by induction) $= (|{\cal A}_1|+|{\cal A}_2|)(|{\cal B}_1|+|{\cal B}_2|)/2^n + (|{\cal A}_1|-|{\cal A}_2|)(|{\cal B}_1|-|{\cal B}_2|)/2^n$ $\geq {\cal |A||B|}/2^n + (|{\cal A}_1|-|{\cal A}_2|)(|{\cal B}_1|-|{\cal B}_2|)/2^n$.

However, since ${\cal A,B}$ are monotone decreasing, we have ${\cal A}_2 \subseteq {\cal A}_1$ and ${\cal B}_2 \subseteq {\cal B}_1$, so that $(|{\cal A}_1|-|{\cal A}_2|)(|{\cal B}_1|-|{\cal B}_2|) \geq 0$. We therefore conclude that ${\cal |A \cap B|} \geq {\cal |A||B|}/2^n$, as claimed.

To obtain the second inequality, simply set ${\cal A,B}$ to be the complements of ${\cal C,D}$ and apply the first inequality.

To obtain the third inequality, set ${\cal B}$ to be the complement of ${\cal C}$ and apply the first inequality to obtain ${\cal |A| - |A \cap C|} = {\cal |A \cap B|} \geq {\cal |A||B|}/2^n$ $= {\cal |A|}(2^n - {\cal |C|})/2^n = {\cal |A|} - {\cal |A||C|}/2^n$, so that ${\cal |A \cap C|} \leq {\cal |A||C|}/2^n$, as claimed.

Let us now apply Kleitman’s Lemma to prove the following result, also due to Kleitman.

Theorem. The union of $m$ intersecting families of subsets of an $n$-element set contains at most $2^n - 2^{n-m}$ members.

We have already dealt with the case $m=1$ in our previous discussion, so let $m>1$. Let ${\cal F}$ be the union of the families ${\cal F}_1,\ldots,{\cal F}_m$. We only seek to obtain an upper bound on the size of ${\cal F}$, so by our previous discussion, we may fatten up each of these families so that it is maximal and hence contains $2^{n-1}$ members. Let ${\cal A}$ be the complement of ${\cal F}_m$ and let ${\cal B}$ be the union of ${\cal F}_1,\ldots,{\cal F}_{m-1}$. Since we have made each of the ${\cal F}_i$ maximal, it follows that ${\cal A}$ is monotone decreasing and ${\cal B}$ is monotone increasing. We may apply our inductive assumption to obtain $|{\cal B}| \leq 2^n - 2^{n-m+1}$. We may also apply Kleitman’s Lemma to obtain $|{\cal A} \cap {\cal B}| \leq {\cal |A||B|}/2^n$ $\leq 2^{n-1}(2^n - 2^{n-m+1})/2^n$ $= 2^{n-1} - 2^{n-m}$.

It follows then that $|{\cal F}| = |{\cal B}| + |{\cal F}_m| - |{\cal B} \cap {\cal F}_m|$ $= |{\cal B}| + |{\cal F}_m| - (|{\cal B}| - |{\cal A} \cap {\cal B}|)$ $= |{\cal F}_m| + |{\cal A} \cap {\cal B}|$ $\leq 2^{n-1} + 2^{n-1} - 2^{n-m} = 2^n - 2^{n-m}$,

as claimed.

Advertisements

Written by uncudh

December 1, 2008 at 12:57 am

Posted in math

Tagged with ,