Skip to main content
edited body
Source Link

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.

ThaiThat 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.

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.

Thai 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.

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.

Source Link

Covering a poset by minimum number of chains and antichains

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.

Thai 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.