Generalized LYM inequalities

I’ve been thinking about this problem ever since an old post of Qiaochu’s first raised the question, and I’ve been frustrated by my inability to solve it. I could post it on MO, but I sort of already have, and anyway it raises questions which are too ill-formed right now to be right for MO. So anyway, here we go:

A lot of problems in extremal combinatorics correspond to finding large antichains in partially ordered sets. (By the way, all posets in this post will be assumed to have a least element.) Classically speaking, Dilworth’s theorem completely characterizes the size of antichains in posets; however, this is often tricky to apply, since it’s not always clear whether a partition into chains is minimal. In addition, it’s sometimes the case (particularly with infinite posets) that there are infinitely long antichains, but a nontrivial bound should still be attainable. The way to get by both of these obstacles is to assign weights to the elements of the poset, and rather than looking for large antichains, we look for antichains with high total weight.

The classical example of this solves the problem of finding the largest antichain in the lattice of subsets of a given finite set — the content of Sperner’s theorem. Suppose that the base set has cardinality n. Then to each subset of cardinality k, we assign a weight of 1/ {n \choose k}. Then the LYM inequality states that every antichain has weight at most 1. There are a number of ways to prove this, but here’s my favorite: Fix some saturated chain C of the poset, and consider a random automorphism of the lattice. A set of cardinality k gets mapped into C with probability 1/ {n \choose k}. Furthermore, no two elements of an antichain can be simultaneously mapped into C. So the probability that at least one of the elements of the antichain gets mapped into C is the sum of the probabilities for each individual element (the later terms in inclusion-exclusion all vanish), and this probability is trivially at most 1.

It follows from this, then, that the largest antichain in the poset is the one where you take all the subsets of size n/2, since this is the largest binomial coefficient. This proves Sperner’s theorem.

Inequalities of this type — bounding the weights of antichains in posets — are sometimes called “generalized LYM inequalities,” after the foundational example above. I’ll call a weight function \omega on some poset P “LYM” if it has the property that any antichain has total weight at most 1. The content of the LYM inequality is then that a certain weight function is LYM.

Okay, so now the obvious question arises.

Question. Which weight functions on a given poset are LYM?

In general, this is probably too much to ask in general. But we have some classes of weight functions that are easily seen to be  LYM. If C is a chain of P, then the characteristic function of C is LYM. Furthermore, if f_1, \ldots, f_m are all LYM, then any convex combination a_1 f_1 + \ldots + a_m f_m, a+1 + \ldots + a_m = 1, a_i \geq 0, is also LYM.

If you check special cases, then for finite posets it seems that this generates every possible LYM function. So:

Conjecture. Every LYM function on a finite poset is a convex combination of characteristic functions of chains (possibly including the empty chain).

A conjecture this simple, one would think, would be in the literature somewhere; but a search turns up nothing. Furthermore, my attempts to prove it have all been for naught. My first line of attack was an inductive argument; the hope was that I could write \omega = a 1_C + \omega', where \omega' would be supported on a smaller poset and 1/(1-a) \omega' would be LYM. But alas, this petered out — the “combinatorial” way to do this would be to have a chain that intersected every maximal (as opposed to maximum) antichain, but this doesn’t exist in general.

My next hope was that perhaps there was an algorithmic decomposition, but the convex decomposition isn’t completely rigid, particularly when the 0 weight function has a nonzero coefficient, so this is unlikely.

However, it does suffice to prove the conjecture for the power set lattice, since every poset can be embedded into a power set lattice. That said, I’m still stumped — anyone have any ideas?

By the way, assuming the conjecture is true, there’s another question which seems interesting, although it’s a little more open-ended. I alluded to it above, but here it is stated a little more formally.

Question. What are necessary and sufficient conditions for a decomposition of \omega as a convex combination of characteristic functions to be rigid? Is there a unique such decomposition with smallest coefficient of the constant zero function? Is there a “canonical” decomposition, akin to the Fourier transform?

Finally, I want to say a little bit about infinite posets. Certainly every convex combination of characteristic functions is still LYM on infinite posets, but this is definitely not necessary — think about Kraft’s inequality.  However, the given inequality can be proved in the same way that we proved the LYM inequality above — by fixing a distinguished chain and assigning each element a weight equal to the probability that it gets mapped to the chain under a random automorphism. This works because the automorphism group of the relevant poset is profinite, hence compact. Interestingly, the characteristic functions of chains can be thought of in a similar way — they’re the weight functions arising from taking a compact subgroup of the full automorphism group, namely the trivial group, and proceeding as above. So a few final questions:

Questions. Does every LYM function on a poset with compact automorphism group arise as a convex combination of functions like the above obtained from compact subgroups? What about posets whose automorphism group is non-compact?

Advertisements

Tags: , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: