2
$\begingroup$

I am not an expert in combinatorics, but I need to count (or to approximate) the number of antichains of a poset.

The idea relies on approximating this number by embedding my poset into another one, that I call "rectangular" but actually I don't know if there is already a standard definition.

Let's say that my poset has depth $d$ (t.i. the maximal lenght of a chain) and spread $a$ (t.i., the max of cardinalities among all maximal antichains). Then I embedd this poset into another one, that has $d$ independent chains of lenght $a$, not considering the $0$ and $1$ elements. I claim that the second one contains more antichains than the first one, and that this number is $d \cdot 2^a$.

Is this idea correct? May I have a better upper bound of the number of antichains in a general poset?

Thank you all in advance for any answer!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What does "embed" mean to you? $\endgroup$
    – JBL
    Commented Dec 15, 2010 at 14:03
  • $\begingroup$ nothing very serious, actually. That for each direct dependency of the given poset there is a direct dependency in the rectangular poset. For example, if my poset is given by $\{a\geq b, a\geq c\}$, then I can embed this one into $\{a\geq b, a^\prime\geq c\}$. In the first case I have $4$ antichains, t.i. $\{c\},\{b\}, \{a\}, \{b,c\}$; in the second one I have $8$ antichains, t.i. $2\cdot 2^2$. I only need this "embedding" to count antichains, so I don't search for anything powerful... $\endgroup$
    – klaraspina
    Commented Dec 15, 2010 at 16:25
  • $\begingroup$ Here is a paper that proves that the problem is #P-complete, which means that for large posets there is no general algorithm that would work fast (unless...): epubs.siam.org/doi/abs/10.1137/0212053 $\endgroup$
    – domotorp
    Commented Nov 20, 2017 at 8:20
  • $\begingroup$ Well, it's been 13 years, but what was the poset, exactly? $\endgroup$
    – Tri
    Commented Sep 13, 2023 at 23:11

2 Answers 2

Reset to default
4
$\begingroup$

You appear to switch the usage of $d$ and $a$ when you identify your poset with a subset of the other; in what follows, I am using $d$ and $a$ as you defined them, i.e., $d$ is the maximum chain length and $a$ is the maximum antichain size.

Elaborating on Dave Pritchard's point 1: by Dilworth's Theorem, there exist $a$ disjoint chains whose union (as sets) is the (ground set of the) poset. Suppose these chains have lengths $c_1, c_2, \ldots, c_a$. Every antichain contains at most one vertex from each of these chains, so the number of antichains is at most $(c_1 + 1)(c_2 + 1)\cdots(c_a + 1) \leq (n/a + 1)^a$, where $n$ is the number of elements of the poset. We can also use $n \leq da$ to get your upper bound $(d + 1)^a$, which is sharp for a disjoint union of $a$ chains of length $d$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks! I'm sorry, I didn't double check the formula in Dave's comment, that it's clearly a typo. Anyway, on wiki I've seen that it's possible to partition a poset in this way in polynomial time by using the Koenig's theorem. So I can really estimate an upper bound for every (finite) poset with the formula $(c_1+1)\cdot\ldots\cdot(c_a+1)$. Thank you all very much, it has been very helpful! $\endgroup$
    – klaraspina
    Commented Dec 15, 2010 at 19:22
4
$\begingroup$

  1. To me, if the goal is upper-bounding the number of antichains in the original poset, doing an "embedding" seems more complex than necessary. Can't you use just use Dilworth's theorem and then appeal to the fact that any antichain contains at most one element of each chain?

  2. It looks to me that the formula you give for the number of antichains in your "rectangle" is wrong, for example, choosing one element from each of the chains, gives at least $a^d$ different antichains, and this doesn't even count all of them.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 1. I didn't know the Dilworth's theorem, thanks for pointing it out. However, since I'm not an expert, at a first sight I still don't see how to use it... 2. yes, I definitely miscounted! anyway, I think that the number of antichains is bounded by $a^{d+1}$: this number comes if we add a "phantom" element to all chains, meaning that if I choose that one, I'm not taking into account any element of that chain. However, this number is too big for my purposes. So, I have to go back to Dilworth's theorem and understand how to use it. Unless someone knows some better upper bound... Thanks! $\endgroup$
    – klaraspina
    Commented Dec 15, 2010 at 18:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .