Is there a "universal LYM inequality?" - MathOverflow

Is there a "universal LYM inequality?"

2009-10-15T18:55:22Z

This question is based on a blog post of Qiaochu Yuan.

Let P be a locally finite* graded poset with a minimal element, and w be a weight function on the elements of P. Suppose that the total weight of the elements of rank k is bounded by 1. Then is the total weight of any antichain bounded by 1, or some constant c (independent of P or w?) The answer, of course, is no, and it's not hard to construct a counterexample. So what are the minimal conditions on P and/or w needed for such a result?

Note that this should specialize to several well-known theorems. Taking the poset to be a Boolean lattice and w to be 1/(n \choose k), we obtain the LYM inequality, hence the question title. Taking the poset to be the set of finite-length binary words with X \leq Y if X is a prefix of Y, and w to be 1/2^k, we get back Kraft's inequality. And finally, for arbitrary P and setting w to be the constant function 1, we get back (half of a special case of) Dilworth's theorem.

A secondary question: assuming such a result exists, is there a probabilistic proof of it, similar to the probabilistic proofs of Kraft and LYM?

Edit 4: Most of the counterexamples I've constructed thus far have had trees as the underlying poset (i.e., if X \leq Z and Y \leq Z, then either X \leq Y or Y \leq X). This subcase seems to simplify the analysis somewhat, so it might be worth considering only trees.

In fact, here's a toy problem which itself seems rather difficult: Can we characterize the weight functions on the infinite rooted binary tree, with the weight of each graded part equal to 1, that satisfy the strong property that the weight of any antichain is at most 1?

*Edit: Actually we want something somewhat stronger than local finiteness, namely that every element is covered by finitely many elements, so that there are are only finitely many elements of any given rank.

Edit^2: Of course we also want the weight function to be nonnegative, or else scary bad things can start happening.

The obvious restriction on the weight function requires it to be dependent only on the rank; interestingly, this is neither necessary nor sufficient for the strong form of the conjecture (i.e. the maximal weight of any antichain \leq the maximal weight of all the elements of rank k) to hold. (Counterexamples available upon request.) I'm still searching for a counterexample in this situation to the weak form of the conjecture (Edit^3: Counterexample found.), where every rank has bounded total weight but there are arbitrarily heavy antichains.

Answer by Harrison Brown for Is there a "universal LYM inequality?"

2009-10-16T22:23:06Z

I'm going to write some of my thoughts on the question as separate answers to add a degree of threading.

The first thing to note is that it seems that any weight function that doesn't depend in a rather deep way on the specific properties of P isn't going to work generically. So we might ask: can we find an (infinite) poset such that every weight function fails?

Well, no. Even if we require that the sum of every graded part is 1, we can simply take an infinite chain and take the weight of the elements in that chain to be 1, and the weight of the other elements to be 0. And, in fact, I believe that small-enough perturbations of this weight function will also satisfy at least the weak form of the conjecture.

So the question is: how can we even ask for a "maximally bad" poset? One approach might be to disregard weight functions that have "high correlation" with the characteristic function of a chain, but it's still not clear how to make this rigorous...

Answer by Harrison Brown for Is there a "universal LYM inequality?"

2009-10-17T01:52:28Z

An approach to the strong form of the property, based on a probabilistic proof of the LYM inequality (apparently due to Bollobas, can be found in Tao and Vu, Ch. 7):

Consider a graded poset P and let G be a compact topological group that acts on P. Construct a weight function as follows. Fix a distinguished (saturated) chain C of P, and for each X, let S(X) be the set of elements in G that take X into C. Then w(X) is the normalized Haar measure of S(X).

It's clear that the total weight of every graded part is 1; now if A is an antichain of P, no automorphism of P can take two elements X, Y \in A to C simultaneously. So the sets S(X) are distinct for all elements X \in A, and the total weight is therefore at most 1.

The only obvious problem with this approach is that I don't see why the sets S(X) should be measurable. However, if P is finite, no such difficulty arises, and in particular this answers Qiaochu's question (from the comments) in the affirmative, at least for finite posets.

This also specializes, for finite posets, to the examples already discussed. Does every weight function on a finite poset with the strong property arise in this way?