Min-Max Problems, Partitioning the Powerset of S

Partitioning the Powerset of S

As often happens in combinatorics, an alternate proof exists for the sperner system. We will partition the powerset of S into (n:n/2) chains. These chains don't necessarily go all the way up and down, but each one is symmetric about size n/2, so that the sum of the cardinality of the first and last member is n. Thus each chain includes a set of size n/2. When n = 1, The chain {∅,1} does the trick. When n = 2, use the chains {2} and {∅,1,12}.

Proceed by induction on n. If x is the new element, shorthand for n+1, add it to each set in each chain, making a new family of chains. Delete the top members, so the chains are again symmetric. Then make another set of chains by appending x union the top sets to the original chains. All subsets, with or without x, are present, and we have indeed partitioned the powerset of S. As an exercise, bring in 3, and obtain the following family of chains.

{} {3,13} {2,23} {∅,1,12,123}

What happened to the first chain? We started with the singleton chain {2}, brought in 3 to make 23, then deleted the top set, leaving an empty chain. An empty chain is meaningless, and can be discarded. It only happens when n is even.

Each chain has a set of size n/2, and the partition includes all such sets, hence the number of chains is (n:n/2). F can take at most one member from each chain, and by taking the middle member of each chain, of size n/2, the members of F are incomparable, and |F| = (n:n/2).

Partitioning with Parentheses

One can explicitly construct the chain containing any given set, as defined by the above procedure. Create a string of parentheses of length n, placing right parentheses in positions corresponding to elements included in the set. For instance, the set 12, when n = 3, becomes ))(.

Any string of parentheses consists of continuous blocks of parentheses that balance, with intervening strings of right parentheses, followed by intervening strings of left parentheses. Here is an example, with pipes delimiting the blocks.

))|(()())|)|()|()|(((|((())())|((((

The rights that have balancing lefts are said to be basic, and correspond to basic elements. Let the set of basic elements be the bottom of the chain. When the string is ))( there are none, so we must start with the empty set. Then succesively add elements in order, stepping through the unbalanced right parentheses, until the original set is produced. That brings in 1 and then 2. Finally add elements in order that correspond to unbalanced left parentheses. That brings in 3, and we're done. We basically step from 1 to n and skip over the balancing blocks. The only integers omitted are the balancing lefts, and there are as many of these as basic elements, so the chain is symmetric.

Every set in a chain has the same blocks, and the same basic elements. From there the chain grows in a prescribed manner, as you step through the unbalanced parentheses from left to right. If a set produces a chain, every other set in the chain produces the same chain. Parenthetical chains do indeed partition the powerset of S.

When n = 1, both sets, ∅ and 1, with strings "(" and ")", create the chain that was described at the top of this page. Proceed by induction and show that the parenthetical chains are indeed the chains we built recursively.

Represent a set with parentheses, analyze its chain, and bring in x. This puts a right parenthesis at the end. If this does not balance a left somewhere in the string, then the string is full of rights between the balancing blocks. This is the top of its chain, and is deleted. So we may assume x becomes a balancing brace, and a basic element. The chain proceeds as before, with x added to every set. The last left, which balances x, can never be added to the chain, because, well, it has become a balancing left. That's ok, because that would become the top of the chain, which we deleted.

Next, append a left parenthesis, for a set that has not been tampered with. This is an unbalanced left at the end of the string. The basic elements are the same, and the chain grows as it did before, until the last left is brought in, becoming the top of the chain augmented by x.

In a Shorter Chain

If ai-1 and ai+1 are members of a chain, there is a set b contained in ai+1 and containing ai-1 that is part of a shorter chain. Instead of flipping the first left parenthesis and then the second to get from ai-1 to ai+1, flip the second only, and call the resulting string b. The flipped parenthesis now balances the earlier left, and introduces another basic element. Therefore b belongs to another, shorter chain.

Symmetric Decomposition

A partition of the powerset of S into collections whose sizes are distributed as the chain lengthss were above is called a symmetric decomposition. Let c(n,k) be the number of partitions of size k, given n elements.

A chain of length n+1 has to start with the empty set and end with S. There can be only one such chain, since the empty set can participate only once. And there is indeed one such chain, indicated by a string of left parentheses. Therefore c(n,n+1) = 1.

Since chains are symmetric, their lengths are all even, or all odd. Half the values of c(n,k) are 0. I'm going to assume n and k have opposite parity.

If n is even, c(n,1) = cat(n/2), the number of strings with balanced parentheses.

If n is odd, say 2r+1, then the shortest chain has length 2, a set of size r and a set of size r+1. All parentheses are balanced except 1, which could be in the beginning, or 2 characters in, or 4 characters in, etc. Therefore c(n,2) is the sum of cat(j)cat(r-j), as j runs from 1 to r.

For j ≤ r, every set of size j is the start of a chain with j basic elements, or a member of a longer chain. Thus the number of chains with j basic elements is (n:j) - (n:j-1). Write k in terms of j, and solve for j, and get j = (n+1-k)/2. Since n and k have opposite parity, this always works. Therefore c(n,k) = (n:(n+1-k)/2) - (n:(n-1-k)/2).

Counting Antichains

An antichain is a collection of incomparable sets. In other words, an antichain is a sperner system; and we have determined the size and structure of the largest antichain. But how many antichains are possible?

For a fixed k, all the sets of size k are incomparable. Any collection of these sets becomes an antichain. This becomes 2 to the (n:k). Take the sum as k runs from 0 to n. At least this many antichains are possible, so this is a lower bound.

An obvious upper bound is 2 to the 2n, the powerset of the powerset of S, but that isn't very interesting. Let's see if we can improve on this.

Let a function from the powerset of S into 0 or 1 be nondecreasing if the function never decreases as you move up a chain. Turn an antichain into such a function by mapping the members of the antichain, and all subsets thereof, to 0. All other sets map to 1. This process can be reversed. The maximal sets that map to 0 become the antichain.

Bound the nondecreasing functions by assigning 0 or 1 to sets, starting with sets in the shortest chains and proceeding through longer chains. Let r = n/2. The shortest chains have length 1 or 2, depending on the parity of n. If n is even, the singleton set in the chain can be assigned 0 or 1. If n is odd, a chain can be mapped to 00, 01, or 11. Now move on to a chain of length 3 or 4. Everything between the bottom and top belongs to a shorter chain, and has already been assigned a value. The bottom and top sets can be assigned 00, 01, or 11. This may not jive with the sets in between, but I'm only trying to find an upper bound. Do this for all the chains, and the new bound is 3 to the (n:r).

Is this an improvement? It almost has to be, but let's find out. The log of the brute-force upper bound is 2n times log(2). The log of our new upper bound is (n:r) times log(3). Since (n:r) is like 2n/sqrt(n), we have definitely made progress.