A bipartite analogue of Dilworth’s theorem for multiple partial orders
- Fox, Jacob
- Pach, János
DOIAbstract
AbstractLet r be a fixed positive integer. It is shown that, given any partial orders <1, …, <r on the same n-element set P, there exist disjoint subsets A,B⊂P, each with at least n1−o(1) elements, such that one of the following two conditions is satisfied: (1) there is an i(1≤i≤r) such that every element of A is larger than every element of B in the partial order <i, or (2) no element of A is comparable with any element of B in any of the partial orders <1, …, <r. As a corollary, we obtain that any family C of n convex compact sets in the plane has two disjoint subfamilies A,B⊂C, each with at least n1−o(1) members, such that either every member of A intersects all members of B, or no member of A intersects any member of B
Add to ORKG