Combinatorics of Finite Sets

By Ian Anderson

Coherent treatment provides comprehensive view of basic methods and results of the combinatorial study of finite set systems. The Clements-Lindstrom extension of the Kruskal-Katona theorem to multisets is explored, as is the Greene-Kleitman result concerning k-saturated chain partitions of general partially ordered sets. Connections with Dilworth's theorem, the marriage problem, and probability are also discussed. Each chapter ends with a helpful series of exercises and outline solutions appear at the end. "An excellent text for a topics course in discrete mathematics." — Bulletin of the American Mathematical Society.

• Language: English
• Publisher: Dover Publications
• Release date: Apr 30, 2012
• ISBN: 9780486143712

Ian Anderson

Ian Anderson is professional geologist with a long-standing interest in history and archaeology, who has lived and travelled extensively in SE Asia for over 25 years. He has previously published papers in geology and an article on travel by light aircraft in Mexico, and lives immersed in a ‘foodie’ environment as his wife is a cordon bleu chef. He lives in Suffolk.

Book preview

1 Introduction and Sperner’s theorem

1.1 A simple intersection result

of subsets of a finite set Sis described in terms of intersection, union, or inclusion conditions. An amazing richness and variety of results will be discovered, developed, and extended in various directions. Although our main initial theme will be a study of a theorem of Spemer which could be said to be the inspiration of all that follows, we get into training by first of all asking what must surely be one of the simplest questions possible.

Problem be a collection of subsets of an n-element set S (or an n-set S) such that Ai ∩ Aj ≠ ∅ for each pair i, j. | be? The answer, and more besides, is given by the following theorem.

Theorem 1.1.1 is a collection of distinct subsets of the n-set S such that Aj ≠ ∅ for all Ai Aj | ≤ 2n| < 2ncan be extended to a collection of 2n–1 subsets also satisfying the given intersection property.

Proof If A then the complement A’ = S – A , since A ∩ A2n = 2n–1. This bound cannot be improved upon since the collection of all subsets of {1, …, n} containing 1 satisfies the intersection condition and has 2n–1 members.

| < 2n–1. Then there must be a subset A with A and also A. We can then add A unless there exists B such that A ∩ B = ∅. But then B ⊆ A’ and so we could add A. If the resulting collection has fewer than 2n

of subsets of S |? These are the sort of questions which we shall study.

1.2 Sperner’s theorem

We now consider the property: if Ai, Aj, then Ai Aj. A collection of subsets of S with this property is called a collection of incomparable sets, or an antichain, or sometimes a clutter. It is an antichain in the sense that its property is the other extreme from that of a chain in which every pair of sets is comparable.

Theorem 1.2.1 be an antichain of subsets of an n-set S. Then

This result is clearly best possible since the subsets of size [n/2] form an antichain. The original proof given by Sperner will be analysed in Chapter 2, but we start here by giving a simple elegant proof due to Lubell which is pregnant with generalizations and extensions. Altogether we shall give three different proofs, not just because they exist, but because each in its own way presents us with ideas which can be developed to suit a wider range of ordered structures.

Proof of Theorem 1.2.1 (Lubell 1966) First of all note that there are n! permutations of the elements of S. We shall say that a permutation π of the elements of S begins with A if the first |A| members of π are the elements of A in some order. Now the number of permutations beginning with A must be |A|!(n – |Aare distinct. Thus

If we let pk of size k, we have

whence

Thus

Note that Lubell’s proof actually gives a stronger result than Sperner’s theorem. The inequality (1.1) is called a LYM inequality is the proportion of all those subsets of S of size k if k = [n/2], pk = 0 otherwise, shows that the bound can be attained.

We have thus shown that the maximum size of an antichain of subsets of an n-set S only it pk . Therefore, if n is even, there is only one maximum-sized antichain, namely the collection of all n/2-subsets. If n (n (n (n (n + 1).

Theorem 1.2.2 If n subsets of the n-set S is made up of all the n/2-subsets of S. If n (n (n + 1)-subsets.

Proof (Lovász 1979) The case of even n has been dealt with. Suppose now that n = 2m with which it begins.

must consist only of sets of size m or m + 1. Suppose that X, Y are subsets of size m, m +1 respectively and that X ⊂ Y. If X = {x1, …, xm} and Y = {x1, … ,xm, xm+1} then since any permutation beginning with x1, …, xm, X or Y .

consists of all m-sets or all (m contains some but not all of the (m + l)-sets. Then we can find sets E, F such that |E| = |F| = m +1, E , F . By relabelling the elements of S if necessary we can suppose that E = {x1, …, xm+1) and F = {xi, …, xm+i} for some i. Since E and F there must be a largest integer j < i with {xj, …, xm+j. Then E* = {xj, …, xm+jand F* = {xj+1, …, xm+j. We now have an impossible situation. Since E* ∩ F* ⊂ E* where E, we must have E* ∩ F. However, E* ∩ F* ⊂ F* where |E* ∩ F*| = m and |F*| = m + 1, so by an earlier part of the proof one of E* ∩ F* and F

1.3 A theorem of Bollobds

As another example of how the permutation approach of Lubell’s proof can be used to obtain elegant proofs of results obtained originally by more complicated arguments, we now give a generalization of Spemer’s theorem due to Bollobás (1965). The result was also independently proved by Katona (1974), Tarjan (1975), and Griggs, Stahl, and Trotter (1984). This repeated discovery of results by authors working independently is a frequent occurrence in this area of mathematics!

Theorem 1.3.1 (Bollobás 1965) Let A1, …, Am, B1, …, Bm be subsets of an n-set S such that Ai ∩ Bj = ∅ if and only if i = j. Let ai = |Ai| and bi = |Bi|. Then

Proof Consider each of the n! permutations of the elements of S, and say that a permutation π contains A followed by B if all the elements of A occur in π before all the elements of B. If a particular permutation π contains Ai, followed by Bi, and also contains Aj followed by Bj then Ai ∩ Bj = ∅ (if Ai ends before Bj begins) or Aj ∩ Bi = ∅ (if Ai ends after Bj begins), and either of these contradicts the hypotheses. So, for each permutation π, there is at most one i for which π contains Ai followed by Bi. However, given i, the number of permutations containing Ai followed by Bi can be found as follows. Choose the ai + bi positions to be filled by the elements of Ai and Biways. Then place the ai members of Ai in some order in the first ai of the chosen positions and then the members of Bi in some order in the remaining bi positions; this can all be done in ai!bi! ways. Finally order the remaining n – ai – bi elements of S and place then in the remaining places of the permutation; this can be done in (n – ai – bi)! ways. Thus the number of permutations π containing Ai followed by Bi is

Summing over all i we now obtain

Note that Sperner’s theorem follows on taking Bi , the complement of Ai, for the condition Ai ∩ Bi = ∅ becomes Ai = ∅, the condition Ai ∩ Bj , and the conclusion yields

Theorem 1.3.1 has been generalized in a number of ways. Frankl (1982) and Kalai (1984) weakened the condition to Ai ∩ Aj ≠ 0 for 1 ≤ i < j ≤ m and obtained the same conclusion. Lovász (1977) generalized the theorem to subspaces of a linear space. As a recent application, we now apply Theorem 1.3.1 to the following generalization of the Sperner situation. Suppose we are given m chains of subsets of an n-set S which are incomparable in the sense that no member of one chain is contained in a member of any other chain. How large can m be? In the case where all the chains have k +1 members, let f(n, k) denote the largest possible value of m. Then Spemer’s theorem corresponds to the case k .

Theorem 1.3.2 (Griggs et al. 1984) Let f(n, k) denote the largest value of m for which it is possible to find m chains of k +1 distinct subsets of an n-set S such that no member of any chain is a subset of a member of any other chain. Then

Proof Suppose that we have m chains

satisfying the conditions of the theorem. In Theorem 1.3.1 take Ai = Ai,0 and Bi = S – Ai,k. Then ai = |Ai,0| and bi = n – |Ai,k|. It is clear that |Ai,k| ≥ ai + k, so bi ≤ n – k – ai; thus

Now we certainly have Ai ∩ Bi = ∅. Also, if we had Ai ∩ Bj = ∅ for some i ≠ j we would then have Ai,0 ⊂ Aj,k, contradicting the hypotheses. So the sets Ai and Bi satisfy the conditions of Theorem 1.3.1, and we have

Thus

chains with the required properties. Consider the [(n – k)/2]-subsets X of {k + 1, …, nsuch subsets. For each such X take the chain

Further generalizations of Sperner’s theorem will be discussed later, particularly in Chapter 8 and in the study of the Littlewood- Offord problem in Chapter 11.

Exercises 1

1.1 Prove that if A1, …, Am are distinct subsets of an n-set S such that for each pair i, j, Ai ∪ Aj ≠ S then m ≤ 2n–1.

1.2 Can we have equality in Theorem 1.1.1 without all the Ai having a common element?

is an antichain of subsets of an n-set with |A| ≤ h n for all A

1.4 How many antichains of subsets of S are there if (a) |S| =2, (b) |S| = 3? (This will be followed up in Chapter 3.)

1.5 Show that the number of pairs X, Y of distinct subsets of an n-set S with X ⊂ Y is 3n – 2n.

of subsets of an n-set S is called a cross-cut if every subset of S .

1.7 Let x1, …, xn be real numbers, |xi| ≤ 1 for each i, and let I with εi = 0 or 1 lying inside I . (Hint: First explain why we may assume that each xithe corresponding set of indices i for which (2εi, – 1)xi>0.) (Erdös 1945)

1.8 Let A1, …, Am, B1, …, Bm be subsets of an n-set S such that Ai ⊆ Bi for each i and Ai Bj whenever i ≠ j. Show that

= {A1, …, Am} be a collection of subsets of an n-set S and let ai = |Ai|. Call a subset Bi of Ai an own-subset of Ai if Bi Aj for all j ≠ ihas an own-subset then

where bi = |Bi|.

(Tuza 1984)

= {A1, …, Am} and let r) = min{|B| :B ∩ Ai ≠ ∅ for each icritical if r– {Ai}) < r) for all i. is critical with r) = t + 1, then

Deduce that, if |Ai| = k for each i is critical with r) = t members.

(Tuza 1984)

= {A1, …, Am} is a completely separating system of subsets of S = {x1, …, xn} if for any two elements xi ≠ xj of S there exist sets Ak and Ah such that xi ∈ Ak, xj ∉ Ak, xi ∉ Ah, xj ∈ Ah* = {X1, …, Xn) of subsets of {1, …, m} given by Xi = {k:xi ∈ Akis completely separating if and only if A* is an antichain.

(Cai 1984)

is an antichain of subsets of S, define the blocker b to be the collection of all minimal subsets of S . Clearly b) is an antichain. Show that b(b.

(ii) Similarly define the antiblocker cto be the collection of all maximal subsets of S . Give an example to show that the assertion that c(cis not always true.

is a Menger antichain is equal to the minimum size of a member of the blocker b). Verify that

but that b) is not a Menger antichain.

1.14 Menger’s theorem in graph theory asserts that if x and y are non-adjacent vertices of a graph then the maximum number of vertex-disjoint paths from x to y is equal to the minimum number of vertices whose removal from the graph separates x from y. Re-express this result in terms of Menger antichains. (For further details see, for example, Woodall (1978) or Seymour (1977).)

2 Normalized matchings and rank numbers

2.1 Sperner’s proof

The aim of this chapter is to present Sperner’s original proof of his theorem and to study a property of sets, called the normalized matching property, which arises in that proof. In doing so we shall discuss one of the basic theorems of combinatorics, the so-called marriage theorem, and we shall finish by having a look at the lattice of partitions of a set, about which some interesting conjectures have both risen and fallen.

is an antichain of subsets of an n-set Shas Pi members of size i, 0 ≤ i ≤ n. If there is an i (n – 1) for which Pi > 0, we consider the smallest such i and show how to replace the pi sets of size i by pi sets of size i of size < (n – 1) replacing them by sets of size n/2 if n (n – 1) if n is odd. We then consider sets of size greater than nbut with all sets having size [n/2]. The theorem will then follow immediately.

The entire process described above depends upon the following simple lemma about the shade and the shadow of a collection of k-sets.

Definition be a collection of k-subsets of an n-set S, k < n. The collection

is called the shade consists of all subsets of S . Similarly the shadow is defined to be

consists of all subsets of S .

Lemma 2.1.1 be a collection of k-subsets of an n-set S. Then

and

Proof Consider the pairs (B, D) with B , D , B ∈ D. We use a common combinatorial technique and count these pairs in two different ways. For each B there are n – k elements of S not in B which can be added to B to obtain a set D; therefore the number of pairs (B, D) is (n – k|. However, each D is of size k + 1 and so has k + 1 subsets of size k ). Therefore the number of pairs (B, D) is at most (k |. Thus

as required.

Corollary 2.1.2

Proof of Spemer’s theorem has i, members of size i, and suppose that the smallest value of i for which Pi > 0 is i(n – 1). By the corollary above we can find pi0 sets of size i. Therefore we can replace the piof size i(n (n + 1) by an equal number of sets of size [nl consists entirely of sets of size [n

Note that the conclusion of Lemma 2.1:1 can be written in the form

The lemma therefore asserts that the proportion of sets of size k is at least as big as the proportion of sets of size k . This property of sets is known as the normalized matching property. We shall see later that the analogous property holds for divisors of an integer, where inclusion is replaced by divisibility and size by the number of prime factors. It will also be shown that the normalized matching property is intimately related to the LYM property discussed in Chapter 1.

2.2 Systems of distinct representatives

The normalized matching property is reminiscent of a fundamental theorem in combinatorics due to König and P. Hall which is often known by its popular title of the ‘marriage problem’. Given a collection of subsets A1,…, Ar of an n-set S, we define a system of distinct representatives (s.d.r.) for A1,…, Ar to be a system of distinct elements a1,… ,ar of S such that ai∈Ai, for each i. For example, the sets

possess an s.d.r. since we can select 3, 2, 1, 5 respectively to ‘represent’ the sets. However, the sets

cannot possess an s.d.r. since, for example, the four sets {1,2,3}, {1,3}, {1,2}, {2,3} have only three distinct elements in their union, which is not enough to represent four sets. It is clear that if an s.d.r. exists then, for each k, any k of the sets must have at least k elements in their union. Perhaps surprisingly, this obviously necessary condition turns out to be sufficient.

Before stating the theorem, we remark that the title ‘marriage problem’ arises from the following interpretation. Imagine that r men are each asked to make a list of the ladies they would be willing to marry. Then (assuming that the ladies have no say in the matter) it is possible to marry each man to a lady on his list if and only if the lists possess an s.d.r.

Theorem 2.2.1 (König 1931, P. Hall 1935) The sets A1 …, Ar possess an s.d.r. if and only if, for each m ≤ r, the union of any m of the sets Ai contains at least m elements.

Proof (Halmos and Vaughan 1950) Since the condition is clearly necessary, we prove the ‘if’ part, and proceed by