Uniformly at Random

Posts Tagged ‘finite sets

Another intersecting families result

leave a comment »

We have previously discussed the following result of Kleitman concerning intersecting families of sets: if {\cal A,B} are monotone decreasing families of subsets of \{1,\ldots,n\}, then {\cal |A||B|} \leq 2^n {\cal |A \cap B|}. Suppose that instead of the hypothesis that {\cal A,B} are monotone decreasing, we instead have that |A \cap B| is even for every A\in{\cal A}, B\in{\cal B}. In this case we have the following result of Ahlswede, El Gamal, and Pang (1984).

Theorem. If {\cal A,B} are families of subsets of \{1,\ldots,n\} such that |A \cap B| is even for every A\in{\cal A}, B\in{\cal B}, then {\cal |A||B|} \leq 2^n.

Proof. Let U and V be the vector spaces over GF(2) generated by the sets of characteristic vectors of the sets in {\cal A} and {\cal B} respectively. The assumption that |A \cap B| is even for every A\in{\cal A}, B\in{\cal B} means that the inner product \langle u,v \rangle is 0 over GF(2) for every u \in U, v \in V. In other words V is contained in the orthogonal complement U^\perp of U. Since \dim U + \dim U^\perp = n, we have |{\cal A}||{\cal B}| \leq |U||V| \leq 2^{\dim U + \dim U^\perp} = 2^n, as required.

Written by uncudh

February 12, 2009 at 4:50 am

Posted in math

Tagged with ,

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.

Written by uncudh

December 1, 2008 at 12:57 am

Posted in math

Tagged with ,

A theorem of Bollobas

with 3 comments

The following theorem of Bollobas is an important result from extremal set theory.  It has apparently been rediscovered several times by others.  It implies certain classical results, such as Sperner’s Theorem, and has some interesting extensions.

Theorem (Bollobas).  Let A_1, \ldots, A_m and B_1, \ldots, B_m be sequences of a-element and b-element sets respectively.  Suppose that A_i \cap B_i = \emptyset and A_i \cap B_j \neq \emptyset whenever i \neq j.  Then m \leq {a+b \choose a}.

Proof.  Let X be the union of all the A_i‘s and B_i‘s.  Consider an arbitrary permutation \pi of X.  We claim that there is at most one pair (A_i, B_i) such that all of the elements of A_i precede those of B_i in the ordering \pi.  Suppose to the contrary that there are two such pairs (A_i, B_i) and (A_j, B_j).  Without loss of generality, suppose that the last element of A_i does not appear after the last element of A_j in the ordering \pi.  However, this implies that all the elements of A_i appear before those of B_j in the ordering \pi.  Thus A_i and B_j are disjoint, contradicting the assumption that A_i \cap B_j \neq \emptyset.

Now consider an arbitrary pair (A_i, B_i).  For how many permutations \pi of X can the elements of A_i precede those of B_i?  Suppose that X has n elements.  Since A_i is of size a and B_i is of size b, we may choose the positions of \pi that contain A_i \cup B_i in {n \choose a+b} ways.  Since the elements of A_i must precede those of B_i, we must place the elements of A_i in the first a positions chosen, and there are a! ways to do so.  Similarly, there are b! ways to place the elements of B_i in the permutation \pi.  Finally, there are (n-a-b)! ways to fill in the remaining elements of \pi.  Thus there are

{n \choose a+b} a! b! (n-a-b)! = \frac{n!a!b!}{(a+b)!} = n!{a +b \choose a}^{-1}

permutations \pi where the elements of A_i precede those of B_i.  By our earlier observation, if we sum this quantity over all pairs (A_i,B_i), we cannot exceed the total number n! of permutations of X.  We thus have m \cdot n!{a +b \choose a}^{-1} \leq n!, which implies m \leq {a +b \choose a}, as required.  This completes the proof.

Written by uncudh

November 15, 2008 at 10:40 pm

Posted in math

Tagged with ,