Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Could you, please, recall the definition of a strongly connected poset? –  Michał Kukieła Apr 25 at 8:16
    
After checking, what I meant was connected (sorry, I am not an expert of combinatorics and posets in general). –  Seb Destercke Apr 25 at 8:29

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
1  
@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. –  Emil Jeřábek Apr 25 at 16:12
2  
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$$ –  Seb Destercke Apr 26 at 8:24
    
@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. –  Michał Kukieła May 5 at 17:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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