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 ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: