# Entropy of chain decompositions of posets

Let $P$ be a finite poset and let $\,\mathcal{C}=(C_1,\ldots,C_\ell)\,$ be its decomposition into chains. We can define $$f(\mathcal{C}) = |C_1|! \, \cdots \,|C_\ell|!$$ and ask for what $\mathcal{C}$ we have $f(\mathcal{C})$ maximal. Roughly speaking, the smaller is $\ell$ and the less evenly distributed are $|C_i|$, the better. Specifically, I am interested in the following.

Question: Does $f(\mathcal{C})$ maximize for the number $\ell$ of chains equal to the size of the maximal antichain in $P$?

Motivation: If true, this would be an unusual extension of Dilworth's theorem. I am really interested in bounds on the number $e(P)$ of linear extensions, and it is easy to see that $e(P)\le |P|!/f(\mathcal{C})$ for all chain decompositions $\mathcal{C}$. The connection to entopy is also standard: take $\log e(P)$ in the last equation and think of $|C_i|/|P|$ as a probability distribution.

Refs disclaimer: There is a large number of papers bounding $e(P)$ in terms of the entropy, see e.g. here, here and here. They are not completely unrelated, but do not seem concerned with this type of questions.

• It seems clear to me that it does, and that for finite posets the function must achieve its maximum with a minimal decomposition. I also don't see it as an extension at all, much less an unusual one. Gerhard "What Is The Question Really?" Paseman, 2016.10.09. – Gerhard Paseman Oct 10 '16 at 3:35
• I am asking for a mathematical argument, not a POV. – Igor Pak Oct 10 '16 at 3:51
• Consider a poset P of width L+1, a decomposition of P that maximizes f, and look at a longest chain C in this decomposition. Since f is maximized, C is a maximal length chain. P-C is of width L. Recurse. I can fill it in if needed, but if there is a difficulty I am not seeing it. If you could tell me what prevents you from this POV, we might have a more productive exchange. Gerhard "Willing To Share A POV" Paseman, 2016.10.09. – Gerhard Paseman Oct 10 '16 at 4:06
• The problem is the same as when trying to use the greedy algorithm to solve the knapsack problem. Namely, it is unclear if down the road you don't get into a situation with only short chains when compared to the case when you started with a second-longest chain. – Igor Pak Oct 10 '16 at 4:16

The answer is no. Take a chain $a_1>\dots>a_{100}$ and add two elements $b>a_{51}$ and $c<a_{50}$ (with no relations not implied by these ones). The maximum of $f(\mathcal C)$ is achieved on the decomposition $\{a_1,\dots,a_{100}\}\sqcup\{b\}\sqcup\{c\}$, while the maximal antichain has cardinality 2 (due to the decomposition into two chains $\{a_1,\dots,a_{50},c\}\sqcup \{b,a_{51},\dots,a_{100}\}$).