# Uniformly at Random

## Another intersecting families result

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

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

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 ,