## Intersecting families of sets

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 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 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 members. To see this, observe that if an intersecting family has fewer than members, then there must exist a set such that neither nor its complement is in . If intersects every member of , then can be added to to create a larger intersecting family. If there is a set disjoint from , then, noting that must be contained in , we may add to to again obtain a larger intersecting family. We may repeat the process until we have enlarged to a family with members.

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

**Kleitman’s Lemma**. Let be monotone decreasing families of subsets of and let be monotone increasing families of subsets of . Then

.

The result clearly holds when , so let us suppose . Let be the family consisting of all members of not containing , and let . Let and be defined analogously.

Now,

(by induction)

.

However, since are monotone decreasing, we have and , so that . We therefore conclude that , as claimed.

To obtain the second inequality, simply set to be the complements of and apply the first inequality.

To obtain the third inequality, set to be the complement of and apply the first inequality to obtain , so that , as claimed.

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

**Theorem**. The union of intersecting families of subsets of an -element set contains at most members.

We have already dealt with the case in our previous discussion, so let . Let be the union of the families . We only seek to obtain an upper bound on the size of , so by our previous discussion, we may fatten up each of these families so that it is maximal and hence contains members. Let be the complement of and let be the union of . Since we have made each of the maximal, it follows that is monotone decreasing and is monotone increasing. We may apply our inductive assumption to obtain . We may also apply Kleitman’s Lemma to obtain

.

It follows then that

,

as claimed.

## Leave a Reply