Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For my thesis I'm working on a program to count the number of upsets in a lattice. My professor gave me a tip via e-mail that the number of upsets in a lattice equals the number of antichains in a lattice. (Antichains are often shorter so when you're just interested in the number it can be faster to go for this approach).

I've tried finding some proof or at least to get a general idea why the above is true, it seems true enough in my program anyway. Of course I will speak to my professor next week and he will be able to explain it but I'm curious now (you know how it feels :D).

So does anyone have an explanation why #anti-chains == #upsets given any partially ordered set? I'm not necessarily looking for a formal proof, I'm just trying to guide my intuition :).

share|improve this question
2  
Imagine you wanted to list all of the up sets. Instead of listing every element in each up set, you might notice some are redundant: if you list x and x <= y, then we know y is in the set, so why list it explicitly? If you take this to the extreme, you only list the minimal elements of the upset, and you know they are minimal because you cannot compare them with each other: none of them was ever a "y". In other words to list up sets, you might prefer to list the anti chains that generate them. If you were using backtracking to find the up sets, then in some sense you were already doing this. –  Jack Schmidt Jan 11 '12 at 12:07
    
@JackSchmidt that's a brilliant answer, I hadn't looked at it that way at all but now you've explained it its perfectly logical. Too bad I can't accept comments as answer :). –  Roy T. Jan 11 '12 at 12:16
    
@JackSchmidt: Bravo ! –  Did Jan 11 '12 at 12:20
add comment

1 Answer 1

up vote 3 down vote accepted

For every anti-chain $a$ in a lattice $L$, define $a^+$ as the set of elements of $L$ greater or equal than at least one element of $a$. Then $a^+$ is an upset of $L$ and the function $a\mapsto a^+$ is one-to-one between the set of anti-chains in $L$ and the set of upsets of $L$.

share|improve this answer
    
I suppose you mean greater than or equal. Then the inverse mapping is given by taking the set of minimal elements of an up-set. Note that the existence of minimal elements, and therefore the fact that this is an inverse mapping, depends on the (implicit) assumption that the poset is finite (or at least well-founded: it satisfies the descending chain condition), but not on the assumption that it is a lattice. –  Marc van Leeuwen Jan 11 '12 at 11:14
    
@MarcvanLeeuwen: Yes. –  Did Jan 11 '12 at 11:19
    
@DidierPiau thanks for your answer. This more formal wording nicely complements the comment by Jack Schmidt. I can sleep again now :). –  Roy T. Jan 11 '12 at 12:18
    
Roy: Thanks. Indeed, @Jack's formulation is quite telling. –  Did Jan 11 '12 at 12:20
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.