Min-Max Problems, Sperner System

Sperner System

A sperner system is a collection of subsets F of a set S, such that no subset contains another. If |S| = n, what is the maximum value of |F|? (The minimum is obviously 0.)

The maximum occurs when F includes all subsets of size n/2, and |F| = (n:n/2). To show this is maximal, consider the n! chains produced by succesively adding the elements of S to a growing set. By inclusion, at most one of the n sets in any chain can be in F, and each set in F with size k accounts for k!×(n-k)! chains. If m_k is the number of sets in F with cardinality k, we have the sum of m_k×k!×(n-k)! ≤ n!. Divide through by n!, and the sum of m_k/(n:k) ≤ 1.

Replacing (n:k) with (n:n/2) can only make the left side smaller, so the sum over m_k (which is the size of F) is bounded by (n:n/2). Furthermore, this bound is only realized if each k = n/2, or n/2+1 if n is odd.

When n is even, select the sets of size n/2, as described above. This is the only decomposition that builds a maximal family F.

If n = 2r+1, F contains the sets of size r, or r+1, but not both. Suppose F is a mixed family. Let the small sets have size r, and let the large sets have size r+1. Small sets + large sets = |F| = (n:r). Each small set rules out r+1 large sets, and each large set is killed off by at most r+1 of the small sets. Assume there are u small sets and v large sets in F. If j = (n:r), there are j possible small sets to choose from, and j possible large sets. And u+v = j. So every small set does indeed kill off, on average, one large set. If a large set is not killed off by all r+1 of the small sets inside it, we have a deficit from which we cannever recover. Let the first small set contain the integers 1 through r. This kills off {1,2,3…r+1}, and that means F contains all r+1 small sets drawn from the first r+1 integers. Use this technique to replace r with r+1 in a small set. Or replace any of the first r integers with anything from r+1 to n. Do this again and again, and create an arbitrary small set. Therefore F contains every small set, and kills off every large set. There are two compositions of F when n is odd - all the sets of size r, or all the sets of size r+1.

Ranked Partially Ordered Set

In a partially ordered set, a covers b if b < a, and there is no c with b < c < a. Members of S are ranked, so that rank(a) = rank(b)+1 iff a covers b. Finally assume all elements of the same rank cover, or are covered by, the same number of elements. This is a generalization of the sperner system above, where inclusion implements the partial ordering, and rank = cardinality. Each set of size k covers k sets, and is covered by n-k sets.

Assume there are w chains to choose from. Let e have rank k. No matter which e you choose, there is a fixed number of elements below e, and a fixed number elements below these, and so on. The same is true going up. If there are s_k elements of rank k, then by symmetry, each consumes w/s_k chains.

How many elements can we put into F such that all elements are incomparable? As before, let m_k be the number of elements of rank k in F. The chains consumed is the sum of m_kw/s_k, and this is no larger than w. Divide through by w, and the sum of m_k/s_k ≤ 1. This is called the LYM inequality, after the initials of its discoverers.

To make F large, let most of the sets have rank k, where s_k is large. At its largest, |F| is bounded by the maximum s_k. Without more information, it is difficult to characterize F any further.

If the maximum layer is replicated l times, so that each element is covered by the one above, there could be s_k^l maximal families.

More to come…