A multipartite analogue of Dilworth's Theorem

Abstract

We prove that every partially ordered set on $n$ elements contains $k$ subsets $A_1,A_2,\dots ,A_k$ such that either each of these subsets has size $\Omega (n/k^5)$ and, for every $i<j$, every element in $A_i$ is less than or equal to every element in $A_j$, or each of these subsets has size $\Omega (n/(k^2\log n))$ and, for every $i\ne j$, every element in $A_i$ is incomparable with every element in $A_j$ for $i\ne j$. This answers a question of the first author from 2006. As a corollary, we prove for each positive integer $h$ there is $C_h$ such that for any $h$ partial orders ${<}_1,{<}_2,\dots ,{<}_h$ on a set of $n$ elements, there exists $k$ subsets $A_1,A_2,\dots ,A_k$ each of size at least $n/(k\log n{)}^{C_h}$ such that for each partial order ${<}_{\ell }$, either $a_1{<}_{\ell }{a}_2{<}_{\ell }\cdots {<}_{\ell }{a}_k$ for any tuple of elements $(a_1,a_2,\dots ,a_k)\in A_1\times A_2\times \cdots \times A_k$, or $a_1{>}_{\ell }{a}_2{>}_{\ell }\cdots {>}_{\ell }{a}_k$ for any $(a_1,a_2,\dots ,a_k)\in A_1\times A_2\times \cdots \times A_k$, or $a_i$ is incomparable with $a_j$ for any $i\ne j$, $a_i\in A_i$ and $a_j\in A_j$. This improves on a 2009 result of Pach and the first author motivated by problems in discrete geometry.