2
$\begingroup$

Task: Let $(P, ⩽_{1} ), (P, ⩽_{2} )$ be such partial orders on one set (nonempty) that the size of the maximum antichain in the first is $k_{1}$ , in the second is $k_{2}$ . Is it true that the size of the maximum antichain at the intersection of these orders does not exceed $(k_{1} + 1)(k_{2} + 1)$?

My thoughts: Well, we know that each partial order is defined on some one set, in which a certain number of elements. It turns out that these orders will consist of the same elements, but their partial order relations are different. Therefore, at the intersection of these orders, we will get a new order in which the number of elements is the same as that of the original orders, but in this order it turns out that two partial order relations are fulfilled at once? (is it possible?) Then it turns out that at the intersection of two orders, the antichain that was in the first order, it will remain an antichain at the intersection of these orders, the same is true for antichains inside the second order. I don't understand how to get $(k_{1} + 1)* (k_{2} + 1)$? Only intuition suggests that the size of the antichain obtained at the intersection can be no more than $(k_{1} + k_{2})$.

Please help me figure this out, if there are any ideas or hints for solving tasks or comments about my solution, then specify them.

$\endgroup$
4
  • $\begingroup$ This is false: Consider a linear order on a 5-element set and its reverse order. $\endgroup$
    – Ulli
    Feb 4 at 11:29
  • $\begingroup$ If it’s not difficult, could you please explain your comment in more detail? $\endgroup$ Feb 5 at 15:02
  • 1
    $\begingroup$ Let $P = \{0,1,2,3,4 \}$, $\le_1$ the usual order on $P$, $\le_2$ the reverse order, i.e. $4 \le_2 3 \le_2 2 \le_2 1 \le_2 0$. Since both are linear orders, it is $k_1 = k_2 = 1$. The intersection $\le_3$ of $\le_1$ and $\le_2$ is the trivial order, i.e., $x \le_3 y$ only if $x = y$. Hence $P$ is an antichain with respect to $\le_3$ with $(k_1 +1) * (k_2+1) < 5$ elements. $\endgroup$
    – Ulli
    Feb 5 at 17:35
  • $\begingroup$ Thank you very much for the clarification! Your comment can be used as a counterexample to solve this task! $\endgroup$ Feb 5 at 18:04

0

You must log in to answer this question.

Browse other questions tagged .