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

  • 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.2012-01-11
  • 0
    @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 :).2012-01-11
  • 0
    @JackSchmidt: *Bravo !*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
    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.2012-01-11
  • 0
    @MarcvanLeeuwen: Yes.2012-01-11
  • 0
    @DidierPiau thanks for your answer. This more formal wording nicely complements the comment by Jack Schmidt. I can sleep again now :).2012-01-11
  • 0
    Roy: Thanks. Indeed, @Jack's formulation is quite telling.2012-01-11