## Posts Tagged ‘**finite sets**’

## Another intersecting families result

We have previously discussed the following result of Kleitman concerning intersecting families of sets: if are monotone decreasing families of subsets of , then . Suppose that instead of the hypothesis that are monotone decreasing, we instead have that is even for every , . In this case we have the following result of Ahlswede, El Gamal, and Pang (1984).

**Theorem**. If are families of subsets of such that is even for every , , then .

*Proof*. Let and be the vector spaces over GF(2) generated by the sets of characteristic vectors of the sets in and respectively. The assumption that is even for every , means that the inner product is 0 over GF(2) for every , . In other words is contained in the orthogonal complement of . Since , we have , as required.

## 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.

## 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 and be sequences of -element and -element sets respectively. Suppose that and whenever . Then .

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

Now consider an arbitrary pair . For how many permutations of can the elements of precede those of ? Suppose that has elements. Since is of size and is of size , we may choose the positions of that contain in ways. Since the elements of must precede those of , we must place the elements of in the first positions chosen, and there are ways to do so. Similarly, there are ways to place the elements of in the permutation . Finally, there are ways to fill in the remaining elements of . Thus there are

permutations where the elements of precede those of . By our earlier observation, if we sum this quantity over all pairs , we cannot exceed the total number of permutations of . We thus have , which implies , as required. This completes the proof.