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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented May 5, 2014 at 17:45

You must log in to answer this question.

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