1
$\begingroup$

Covering a poset by minmum number of chains is given by Dilworth's theorem and covering a poset by minimum number of antichains is given by Mirsky's theorem. I was wondering what happens if we allow both chains and antichains.

That is, if a poset $P$ is a union of $s$ chains and $t$ antichains, then what can be said about the minimum value of $s+t$?

Currently I am only aware of the upper bound $2\sqrt{|P|}$ (which apparently is a corollary of the Greene-Kleitman duality theory) but I am more interested in the lower bounds on $s+t$. References, if any, on the above problem will be helpful. I would also be interested in any results for some special class of posets, if the general problem is difficult.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Taking a disjoint union of chains of sizes $1,2,\dots,k$ gives the asymptotic lower bound $\sqrt{2|P|}$. $\endgroup$
    – Richard Stanley
    Commented Apr 28, 2023 at 2:01
  • $\begingroup$ @RichardStanley: Thanks. I believe your claim is that at least $k$ chains/antichains are required to cover the poset you mentioned. Could you please provide an argument to prove this? $\endgroup$
    – Pritam Majumder
    Commented Apr 28, 2023 at 6:20
  • $\begingroup$ Removing any chain or antichain from the $k$th Richard Stanley poset gives you something that contains an isomorphic copy of the $(k-1)$th Richard Stanley poset. By induction, you need to remove at least $k$ chains/antichains to get down to the empty poset. $\endgroup$
    – Adam P. Goucher
    Commented Apr 30, 2023 at 14:45
  • $\begingroup$ @AdamP.Goucher, this is exactly the argument I would give. $\endgroup$
    – Richard Stanley
    Commented Apr 30, 2023 at 15:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .