7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Oct 10 '16 at 3:35
  • $\begingroup$ I am asking for a mathematical argument, not a POV. $\endgroup$ – Igor Pak Oct 10 '16 at 3:51
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Oct 10 '16 at 4:06
  • $\begingroup$ 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. $\endgroup$ – Igor Pak Oct 10 '16 at 4:16
3
$\begingroup$

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}\}$).

$\endgroup$
  • $\begingroup$ Great! Exactly what I was looking for. Thanks so much. $\endgroup$ – Igor Pak Oct 10 '16 at 16:40
  • $\begingroup$ Thanks for seeing what I missed. Gerhard "Back To The Drafting Board" Paseman, 2016.10.10. $\endgroup$ – Gerhard Paseman Oct 10 '16 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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