A bipartite analogue of Dilworth's theorem for multiple partial orders (Q1041604): Difference between revisions

If \(\prec\) is a partial order in \(P\) and \(A,B\subset P\), then \(A\prec B\) (resp. \(A\perp B\)) means \(a\prec b\) (resp. \(a\perp b\)) for all \(a\in A\), \(b\in B\), where \(\perp\) means incomparable. Then the authors prove several Ramsey-type theorems for multiple partial orders: Let \(r\), \(n\) be positive integers and \(<_1,\dots,<_r\) partial orders on an \(n\)-element set \(P\). Then there are two disjoint subsets \(A,B\subset P\), each with at least \(n/2^{(1+ o(1))(\log\log n)^r}\) elements such that either \(A<_i B\) for at least one \(i\), or \(A\perp_i B\) for all \(1\leq i\leq r\). Another theorem shows that this is not very far from best possible: Let \(r\) be a positive integer, \(0<\varepsilon< 1\). There is a constant \(C(r, \varepsilon)> 0\) such that for all sufficiently large positive integers \(n\) there are \(r\) partial orders \(<_1,\dots,<_r\) on an \(n\)-element set \(P\) with the following properties: {\parindent=6mm \begin{itemize}\item[1.)] \(<_1,\dots,<_r\) have a common linear extension. \item[2.)] For any \(u\in P\) and for any \(i\) \((1\leq i\leq r)\) the number of elements in \(P\) comparable with \(u\) in the partial order \(<_i\) is at most \(n^\varepsilon\). \item[3.)] For any pair of disjoint subsets \(A,B\subset P\), each with at least \(C(r,\varepsilon) n{(\log\log n)^{r-1}\over(\log n)^r}\) elements, there exist \(x\in A\), \(y\in B\), and \(i\) \((1\leq i\leq r)\) such that \(x<_i y\) or \(y<_i x\). \end{itemize}} As a corollary the following is obtained: Any family \(C\) of \(n\) convex compact sets in the plane has two disjoint subfamilies \(A,B\subset C\), each with at least \(n^{1-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\).