2
$\begingroup$

Now I have a partial order relation among elements in $\mathbb{Z}_2^{n}$, where $\mathbb{Z}_2=\{0,1\}$. For $x, y \in \mathbb{Z}_2^n$, denote \begin{equation*} \begin{aligned} \text{supp}(x) &= \{i \ | \ x[i] = 1, 0\le i\le n-1\} = \{i_1, i_2, \cdots, i_s\},\\ \text{supp}(y) &= \{j \ | \ x[j] = 1, 0\le j\le n-1\} = \{j_1, j_2, \cdots, j_t\}, \end{aligned} \end{equation*} where $s$ and $t$ are positive integers, $i_1 < i_2 < \cdots < i_s$, $j_1 < j_2 < \cdots < j_t$. Say $x \preceq y$ if $s \leq t$ and $i_{s-k} \leq j_{t-k}$ for all $0 \leq k \leq s - 1$.

I want to know the formula of the size of maximal antichain according to $n$, the maximal cardinality of set in which any two distinct elements are incomparable.

Here are some conclusions I have obtained. Denote $S_n$ as the size of maximal antichain, then $S_n\leq \tbinom{n}{\lfloor n / 2\rfloor}$ since the partial order in Sperner’s theorem is weaker. However I can't fix out the exact formula for $S_n$. I wonder if there exist some conclusions or references.

Thanks a lot!

Improve this question
$\endgroup$
7
  • $\begingroup$ It is not much less, at most by a $\sqrt{n}$ factor, since you may consider all subsets with given sum like $n(n+1)/4$, and by certain CLT there are about $\Theta(2^n/n)$ such subsets. $\endgroup$
    – Fedor Petrov
    Commented Dec 28, 2021 at 13:45
  • 3
    $\begingroup$ I think your poset is isomorphic to the one in this question: mathoverflow.net/questions/76723/…. If So then it is known to be strongly Sperner by a result of Stanley, so the maximal antichain size is just the maximal rank size, and the rank generating function is known. $\endgroup$
    – Christian Gaetz
    Commented Dec 28, 2021 at 13:52
  • $\begingroup$ Thanks for comments. I think the poset $M(n)$ in Stanley's article "Some applications of algebra to combinatorics" is exactly what I described above. However I have a pool knowledge about the rank generating function, is there any way to get the maximal rank size from this function? There are only some conclusions about $M(n)$ in this article, is there any reference books which can help me understand better？ $\endgroup$
    – SY.Xu
    Commented Dec 28, 2021 at 14:27
  • 3
    $\begingroup$ One reference is pages 67-71 of my book Algebraic Combinatorics, second ed. $S_n$ is the middle coefficient of the polynomial $(1+q)(1+q^2)\cdots (1+q^n)$. There is unlikely to be an explicit formula, but there is a known asymptotic formula $S_n \sim \sqrt{\frac{6}{\pi}}n^{-3/2}2^n$. See OEIS A025591. $\endgroup$
    – Richard Stanley
    Commented Dec 28, 2021 at 17:15
  • $\begingroup$ See oeis.org/A025591 $\endgroup$
    – Max Alekseyev
    Commented Dec 28, 2021 at 17:16

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .