17
$\begingroup$

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)$?

$\endgroup$
  • 4
    $\begingroup$ Congratulations, François, on your recent election to moderator! $\endgroup$ – Joel David Hamkins Jun 23 '10 at 0:34
  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Jun 26 '10 at 3:49
  • $\begingroup$ 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. $\endgroup$ – Tom Goodwillie Jun 26 '10 at 4:42
  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Jun 26 '10 at 6:30
5
$\begingroup$

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}$.)

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thanks for the very interesting reference. I don't quite see how to carry out your plan, but you might be on to something... $\endgroup$ – François G. Dorais Jun 23 '10 at 23:57
3
$\begingroup$

Together with Grzegorz Guśpiel and Piotr Micek, we have come up with another upper bound construction. Our example is simply an $n^{d+1}$ grid with natural product order. Obviously it has a $d$-dimensional subposet of size $n^d$, and we show that this is asymptotically the largest such subposet. This gives $F_2(n) = O(n^{2/3})$, and in general $F_d(n) = O(n^\frac{d}{d+1})$, which improves the upper bound by Ben Reiniger and Elyse Yeager for $d \leq 7$.

Our proof uses a multidimensional version of Marcus-Tardos theorem, and for $d=2$ we also provide a slightly different example, which can be analysed with bare hands.

You can find the details on arXiv: https://arxiv.org/abs/1705.00176

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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