The Dushnik–Miller [dimension of a partial order](http://en.wikipedia.org/wiki/Order_dimension) $(P,{\leq})$ is the smallest possible size $d$ for a family ${\leq\_1},\ldots,{\leq\_d}$ of total orderings of $P$ whose intersection is ${\leq}$, i.e. $x \leq y$ iff $x \leq\_i y$ holds simultaneously for all $i = 1,\ldots,d$. Equivalently, the dimension is the smallest $d$ such that $P$ embeds in $L^d$ of some total ordering $L$, where $L^d$ is endowed with the coordinatewise partial ordering.


Since chains have dimension 1 and antichains have dimension 2, [Dilworth's Theorem](http://en.wikipedia.org/wiki/Dilworth%27s_theorem) guarantees that every poset of size $n$ contains a $2$-dimensional subposet of size at least $\sqrt{n}$. Is this optimal? In general, what can we say about subposets of dimension $d$?




---


Tom Goodwillie's argument below shows that for sufficiently large $n$, every poset of size $n$ either has an antichain of size $\sqrt{dn}$ or a $d$-dimensional subposet of size $\sqrt{dn}$. This result is optimal for $d = 1$; stated this way, this could also be optimal for $d > 1$ too. For $d = 2$, this improves my lower bound $\sqrt{n}$ above by a factor of $\sqrt{2}$.


In view of this, let me reformulate the question as follows. Let $F\_d(n)$ be the largest integer such that every poset of size $n$ has a $d$-dimensional subposet of size $F\_d(n)$. Note that $F\_1(n) = 1$ for all $n$ and, when $d > 1$, $F\_d(n) \geq \sqrt{dn}$ for large enough $n$.



> 
> Is $F\_2(n) \leq C\sqrt{n}$ for some constant $C$? In general, what is the asymptotic behavior of $F\_d(n)$?
> 
> 
> 



Subposets of small Dushnik-Miller dimension
Elyse Yeager and I have constructed examples for an upper bound. Basically, if you understand the dimension of subposets of $P$, then you understand the dimension of the subposets of the lexicographic power $P^k$. Starting with an appropriate standard example then gets you a sublinear upper bound on $F\_d(n)$; this bound depends on $d$, and in particular we have $F\_2(n)\leq n^{0.8295}$.


Our note is on the arXiv: <http://arxiv.org/abs/1404.0021>


