Timeline for The size of maximal antichain for a given partial order
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2022 at 18:55 | comment | added | Jukka Kohonen | If the problems are solved, it would be nice to wrap them up into a genuine answer so that the question is no longer "unanswered". (You can even answer your own question.) | |
| Dec 28, 2021 at 23:34 | comment | added | SY.Xu | Thank you for all your comments sincerely! I think my problems are solved. | |
| Dec 28, 2021 at 17:16 | comment | added | Max Alekseyev | See oeis.org/A025591 | |
| Dec 28, 2021 at 17:15 | comment | added | Richard Stanley | 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. | |
| Dec 28, 2021 at 14:27 | comment | added | SY.Xu | 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？ | |
| Dec 28, 2021 at 13:52 | comment | added | Christian Gaetz | 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. | |
| Dec 28, 2021 at 13:45 | comment | added | Fedor Petrov | 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. | |
| Dec 28, 2021 at 13:14 | history | edited | SY.Xu | CC BY-SA 4.0 |
added 306 characters in body
|
| S Dec 28, 2021 at 13:05 | review | First questions | |||
| Dec 28, 2021 at 13:29 | |||||
| S Dec 28, 2021 at 13:05 | history | asked | SY.Xu | CC BY-SA 4.0 |