1
$\begingroup$

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

  • 0
    @J$a$ckSchmidt: *Br$a$vo !*2012-01-11

1 Answers 1

3

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

  • 0
    Roy: Thanks. Indeed, @Jack's formulation is quite telling.2012-01-11