Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Dushnik–Miller dimension of a partial order $(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 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)$?

share|improve this question
4  
Congratulations, François, on your recent election to moderator! –  Joel David Hamkins Jun 23 '10 at 0:34
    
Thanks Joel! ${}$ –  François G. Dorais Jun 23 '10 at 1:34
    
Both of the answers posted so far (by John Lenz and Tom Goodwillie) seem to use a different notion of "dimension 2" from the one in the question. In particular, an antichain has dimension 2, as you said, but if it has at least 3 elements then it doesn't satisfy the characterizations used in the answers. –  Andreas Blass Jun 26 '10 at 3:49
    
I did not assert that every 2-dimensional poset can be partitioned into at most two chains. I asserted that any poset that can be partitioned into two chains has dimension at most 2. –  Tom Goodwillie Jun 26 '10 at 4:42
    
Sorry, I misread your "if" as a characterization, perhaps because of the similarity to the characterization (with "if and only if") used in the other answer. –  Andreas Blass Jun 26 '10 at 6:30
add comment

3 Answers

Here is a slight improvement: by observing that a poset has dimension $\le 2$ if it can be partitioned into two chains, you can improve $\sqrt n$ to $\sqrt {2n}$ for $n>1$. (Let the width be $w$. If $w\ge \sqrt {2n}$ then there is an antichain of size $w\ge \sqrt {2n}$. Otherwise there is a partition into $w$ chains of average size $\frac{n}{w}\ge\sqrt{\frac {n} {2} }$, so that the union of the largest two of these chains has size $\ge\sqrt {2n}$.)

share|improve this answer
add comment

Here, I think it is better to think about the dimension in terms of the hypergraph of incomparable pairs. For posets of dimension 2, a poset has dimension 2 if and only if the graph of incomparable pairs is bipartite. (see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.339 for a proof)

Thus you would want to construct posets whose graph of incomparable pairs had no large induced bipartite subgraphs (since a subposet will correspond to an induced subgraph of the graph of incomparable pairs). You could look at the constructions of graphs with no large independent sets (for example, random ones) since those will have no large bipartite subgraphs.

For larger k you can recast the problem as an extremal hypergraph coloring problem and probably there exist some existing hypergraph coloring results?

share|improve this answer
    
Thanks for the very interesting reference. I don't quite see how to carry out your plan, but you might be on to something... –  François G. Dorais Jun 23 '10 at 23:57
add comment

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

share|improve this answer
    
Wonderful! Thank you both! –  François G. Dorais Apr 7 at 21:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.