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!
Best Answer
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$.