2
$\begingroup$

Assume we have a connected poset $P$ of $n$ elements, I am searching to know what is the maximal number of antichains such a poset can have?

$2^n$ is obviously an upper bound, and my feeling is that the maximal number is actually $2^{n-1}$, however I could find the answer in related questions (nor after a quick look at related literature).

$\endgroup$
2
  • $\begingroup$ Could you, please, recall the definition of a strongly connected poset? $\endgroup$ Apr 25, 2014 at 8:16
  • $\begingroup$ After checking, what I meant was connected (sorry, I am not an expert of combinatorics and posets in general). $\endgroup$ Apr 25, 2014 at 8:29

1 Answer 1

1
$\begingroup$

The maximal number of antichains in a connected poset on $n$ elements is $2^{n-1}+1$, if you count $\emptyset$ as an antichain.

It is achieved by the poset $Q(n)$ consisting of a single minimal element and an $(n-1)$-element antichain, each element of the antichain greater than the unique minimum.

To show that one cannot do any better consider the upper bound for the number of antichains in a poset (mentioned in this answer): If $P$ can be partitioned into $a$ disjoint chains and those chains consist of $c_1,c_2,\ldots,c_a$ elements, then the number of antichains in $P$ is at most $(c_1+1)(c_2+1)\cdots (c_a+1)$.

Thus, if there is a $3$-element chain in $P$, then the number of antichains is at most $$4\cdot 2^{n-3}=2^{n-1}<2^{n-1}+1.$$ EDIT:
The following is wrong. Thanks to Seb Destercke for noting it.
If there are two disjoint $2$-element chains, then it is at most $$\not 3 \not\cdot \not 3 \not\cdot \not 2^{\not n\not -\not 4}\not <\not 2^{n-1}\not+\not 1.$$

Corrected version:
If there are three disjoint $2$-element chains, then the number of antichains is at most $$3\cdot 3\cdot 3 \cdot 2^{n-6}=(2^5-5)\cdot 2^{n-6}=2^{n-1}-5\cdot 2^{n-6}<2^{n-1}+1.$$

It is easy to see that a connected poset without $3$-element chains and such that every pair of $2$-element chains has nonempty intersection must be $Q(n)$ or its dual. A connected poset without $3$-element chains that has two, but not three disjoint $2$-element chains is, up to duality, one of the following two kinds of posets, plus possibly some extra comparabilities (which decrease the number of antichains).

          [k]  B [n-k-3]
X(n,k):     \ / \ /
             A   C


          [k]  B
Y(n,k):      \ | \
               A  [n-k-2]

Here $A, B, C$ are vertices and $[m]$ denotes an $m$-element antichain. We need to show that $X(n,k)$ and $Y(n,k)$ both have at most as many antichains as $Q(n)$.

We may assume that the partial orders $X(n,k), Y(n,k)$ and $Q(n)$ are all defined on the same $n$-element base set and moreover $A\in Q(n)$ is the unique minimal element (thus $B,C\in Q(n)$ are maximal).

          B  C [n-3]
Q(n):      \ | /
             A 

The following defines an injective map from antichains in $X(n,k)$ or antichains in $Y(n,k)$ to antichains in $Q(n)$: $$ \{x_1,\ldots,x_m\}\mapsto \{x_1,\ldots,x_m\} \quad \text{ if } x_i\not=A \text{ for all } 1\leq i\leq m,\\\{A\}\mapsto \{A\},\\ \{A,y_1,\ldots,y_m\}\mapsto \{B,y_1,\ldots,y_m\}.$$ Thus $X(n,k)$ and $Y(n,k)$ have at most as many antichains as $Q(n)$.

I believe one can find a more elegant proof (and would be happy to see one!). On the other hand, I think this question seems more appropriate for math.SE.

$\endgroup$
3
  • 1
    $\begingroup$ @VinceVatter: $2^{2-1}+2\ne3$. Anyway, there are $2^{n-1}$ antichains that are subsets of the nonminimal elements (including the empty antichain), and one antichain consisting of the minimal element. $\endgroup$ Apr 25, 2014 at 16:12
  • 2
    $\begingroup$ Thank you for the nice proof, yet if I am not wrong for the two disjoint 2-element chains we have $$3\cdot 3 \cdot 2^{n-4}=(2^3+1)\cdot 2^{n-4}=2^{n-1}+2^{n-4} > 2^{n-1}+1$$ $\endgroup$ Apr 26, 2014 at 8:24
  • $\begingroup$ @Seb Destercke: Of course you are right. I corrected the proof, hopefully without introducing new mistakes. However I feel the question deserves a more elegant answer. $\endgroup$ May 5, 2014 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.