Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Just a random thought. My guess is that w should be some generalization of the factors of 1/Aut(X) that appear when you compute groupoid cardinality, but I don't really know enough about this stuff to suggest what that generalization should be. –  Qiaochu Yuan Oct 15 '09 at 21:54
    
Qiaochu, I'm not entirely sure what you mean or why you think that this is the right thing. (Although I'm beginning to think that Aut(P) will have to come into play somehow.) Could you elaborate, preferably as an answer so you don't have to use <600 characters? –  Harrison Brown Oct 16 '09 at 0:14
    
Part of what I mean is that w should be invariant under any automorphisms of P. Is this necessary / sufficient? –  Qiaochu Yuan Oct 16 '09 at 16:47
    
It's neither. Let P be a rooted infinite binary tree (as in Kraft's inequality), and let w be the characteristic function on some infinite chain. Then the strong property holds, but w isn't invariant under automorphisms of P. Conversely, if w(X) depends only on the rank of X, then clearly w(p(X)) = w(X) for any automorphism p, but it's easy to construct an example with an infinite antichain of infinite weight. –  Harrison Brown Oct 16 '09 at 22:39
    
Okay. What if we also require that the group of automorphisms acts transitively on each rank? –  Qiaochu Yuan Oct 16 '09 at 22:46
show 1 more comment

3 Answers

up vote 1 down vote accepted

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?

share|improve this answer
add comment

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...

share|improve this answer
add comment

Don't know if you are aware of this, but there is an LYM-style inequality for the partition lattice, published in Advances In Applied Mathematics 19, pp 431-443, 1997.

Can be found here- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.5191&rep=rep1&type=pdf

This is useful for me in the context of generating exactly the partitions that satisfy some simple characteristics.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.