Feb 182012
 

Behind the scenes at Boole’s Rings, there was some talk on asking more open questions related to our research. I have three related problems that I would like to share. They are strikingly similar in nature, but they properly belong in three different branches of mathematics: the first problem is about finite combinatorics, the second problem is about reverse mathematics, and the third problem is about infinite combinatorics. To me they are three faces of the same question and I currently don’t know how to answer any of them.

Three Problems. Let $d \geq 2$:

  1. Let $F_d(n)$ denote the largest number such that every poset of size $n$ has a $d$-dimensional subposet of size $F_d(n)$. What is the asymptotic growth of $F_d(n)$?
  2. Every (countably) infinite poset has an infinite subposet of dimension at most $d$. What is the logical strength of this statement over $\mathsf{RCA}_0$?
  3. Is there an uncountable poset that has no uncountable $d$-dimensional subposet?

In all three cases, dimension refers to the Dushnik–Miller dimension of the poset $(P,{\leq})$, which is the smallest number $d$ of linear orders ${\leq_1},\dots,{\leq_d}$ on the set $P$ such that $$x \leq y \IFF x \leq_1 y \land \cdots \land x \leq_d y$$ for all $x,y \in P$. In other words, ${\leq} = {\leq_1} \cap \cdots \cap {\leq_d}$ when thinking of each relation as a set of ordered pairs. Equivalently, for countable and finite posets, this is the smallest number $d$ such that $(P,{\leq})$ is embeddable in $\mathbb{R}^d$ with the coordinatewise ordering (which explains the name).

I asked the first question on MathOveflow in Summer 2010 [1]. Observing that the dimension of a finite poset never exceeds its width, Tom Goodwillie showed that $F_d(n) \geq \sqrt{dn}$ for sufficiently large $n$ [2]. This feels correct for $d = 2$, but it doesn’t feel optimal for $d \gt 2$. (No, I don’t have a concrete reason why I feel that way.) Goodwillie’s argument (for general $d$) runs as follows. Let $(P,{\leq})$ be a poset of size $n$ and width $w$. If $w \geq \sqrt{dn}$ then, by definition, $(P,{\leq})$ has an antichain of size at least $\sqrt{dn}$. Since antichains have dimension at most $2$, we’re done. If $w \lt \sqrt{dn}$ then, by Dilworth's Theorem, $(P,{\leq})$ can be partitioned into $w$ chains of average size at least $\sqrt{n/d}$. If $n$ is large enough, the union of the $d$ largest chains in this partition forms a $d$-dimensional subposet of $(P,{\leq})$ with size at least $\sqrt{dn}$. My main motivation for asking this question on MathOverflow was to get some inspiration to attack the other two questions. I was hoping that this question had already been answered in the finite combinatorics literature, perhaps in a different guise, but this does not appear to be the case.

The second question is a ramification of a problem from Hirschfeldt and Shore. In their paper [3], they studied the Chain-Antichain Principle ($\mathsf{CAC}$), which is the statement that every (countably) infinite poset either has an infinite chain or an infinite antichain. Since chains have dimension $1$ and antichains have dimension $2$, this immediately implies that every infinite poset has an infinite subposet of dimension at most $2$. Hirschfeldt and Shore also studied the Ascending-Descending Sequence Principle ($\mathsf{ADS}$), which they show is equivalent to the restriction of $\mathsf{CAC}$ to $2$-dimensional posets (Theorem 5.3). A straightforward induction shows that $\mathsf{ADS}$ is equivalent to the restriction of $\mathsf{CAC}$ to $d$-dimensional posets for any standard integer $d \geq 2$. Although Hirschfeldt and Shore show that $\mathsf{CAC}$ is strictly weaker than Ramsey’s Theorem for pairs and two colors ($\mathsf{RT}^2_2$), it is still an open question whether $\mathsf{ADS}$ is strictly weaker than $\mathsf{CAC}$. This is where the second problem comes in. If $\mathsf{ADS}$ proves that every infinite poset has an infinite subposet of dimension at most $d$ then $\mathsf{ADS}$ is equivalent to $\mathsf{CAC}$, if not then we have a separation of $\mathsf{CAC}$ and $\mathsf{ADS}$.

The third question may be a little surprising. In the infinite case, the partition relation $\aleph_0 \to (\aleph_0)^2_2$ guarantees that every infinite poset has an infinite subposet of dimension at most $2$. Since $\aleph_1 \to (\aleph_1)^2_2$ is false, it may seem unlikely that every uncountable poset has an uncountable $2$-dimensional subposet. However, Sierpiński’s classical argument to prove that $\aleph_1 \not\to (\aleph_1)^2_2$ simply shows that there is an uncountable $2$-dimensional poset that has no uncountable chains and no uncountable antichains, so this is of little help. Is there an uncountable poset that has no uncountable finite-dimensional subposet? I suspect that such monsters do exist, at least in some models of ZFC, but they are certainly very elusive!

There is a little side story to this last question. In [4], Justin Moore showed that, assuming PFA, every uncountable linear ordering contains an isomorphic copy of one of the following five uncountable linear orders:

  • The ordinal $\omega_1$ or its reverse $\omega_1^*$
  • An $\aleph_1$-dense set of reals $X$
  • A Countryman line $C$ or its reverse $C^*$

Sierpiński’s counterexample is the comparability graph of the two-dimensional poset obtained by combining $\omega_1$ and $X$. Similar counterexamples can be made by combining $\omega_1$ and $C$, or $X$ and $C$, or all three $\omega_1$, $X$, and $C$. Moore’s five element basis guarantees that every finite-dimensional poset contains a combination of this kind (assuming PFA). If every uncountable poset has an uncountable finite-dimensional subposet, then we obtain a nice basis for the class of uncountable posets!

References

[1] F. G. Dorais, Subposets of small Dushnik-Miller dimension.
[BibTeX] [URL]
@MISC {Dorais10,    
    TITLE = {Subposets of small Dushnik-Miller dimension},    
    AUTHOR = {François G. Dorais},    
    HOWPUBLISHED = {MathOverflow},    
    NOTE = {\url{http://mathoverflow.net/questions/29169} (version: 2010-09-12)},    
    URL = {http://mathoverflow.net/questions/29169},    
}

[2] T. Goodwillie, Subposets of small Dushnik-Miller dimension.
[BibTeX] [URL]
@MISC {Goodwillie10,    
    TITLE = {Subposets of small Dushnik-Miller dimension},    
    AUTHOR = {Tom Goodwillie},    
    HOWPUBLISHED = {MathOverflow},    
    NOTE = {\url{http://mathoverflow.net/questions/29570} (version: 2010-06-26)},    
    URL = {http://mathoverflow.net/questions/29570},    
}

[3] D. R. Hirschfeldt and R. A. Shore, “Combinatorial principles weaker than Ramsey’s theorem for pairs,” J. Symbolic Logic, vol. 72, iss. 1, pp. 171-206, 2007.
[BibTeX] [DOI: 10.2178/jsl/1174668391]
@article {HirschfeldtShore07,
    AUTHOR = {Hirschfeldt, Denis R. and Shore, Richard A.},
     TITLE = {Combinatorial principles weaker than {R}amsey's theorem for
              pairs},
   JOURNAL = {J. Symbolic Logic},
  FJOURNAL = {Journal of Symbolic Logic},
    VOLUME = {72},
      YEAR = {2007},
    NUMBER = {1},
     PAGES = {171--206},
      ISSN = {0022-4812},
     CODEN = {JSYLA6},
   MRCLASS = {03F35 (03B30)},
  MRNUMBER = {2298478 (2007m:03115)},
MRREVIEWER = {Roman Kossak},
       DOI = {10.2178/jsl/1174668391},
       URL = {http://dx.doi.org/10.2178/jsl/1174668391},
}

[4] J. T. Moore, “A five element basis for the uncountable linear orders,” Ann. of Math. (2), vol. 163, iss. 2, pp. 669-688, 2006.
[BibTeX] [DOI: 10.4007/annals.2006.163.669]
@article {Moore06,
    AUTHOR = {Moore, Justin Tatch},
     TITLE = {A five element basis for the uncountable linear orders},
   JOURNAL = {Ann. of Math. (2)},
  FJOURNAL = {Annals of Mathematics. Second Series},
    VOLUME = {163},
      YEAR = {2006},
    NUMBER = {2},
     PAGES = {669--688},
      ISSN = {0003-486X},
     CODEN = {ANMAAH},
   MRCLASS = {03E35 (03E05 03E40 03E55)},
  MRNUMBER = {2199228 (2007d:03085)},
MRREVIEWER = {Maxim R. Burke},
       DOI = {10.4007/annals.2006.163.669},
       URL = {http://dx.doi.org/10.4007/annals.2006.163.669},
}

  5 Responses to “Subposets of small dimension”

  1. Interesting post!! I mostly liked the third question, and has a feeling that the answer should be affirmative. More specifically, adding a single Cohen real should produce a model of ZFC admitting an uncountable poset with infinite dimension. The uncountable poset would be Todorcevic’s Souslin tree which is obtained as a composition of a coherent system of injections $\langle e_\alpha:\alpha\rightarrow\omega\mid \alpha<\omega_1\rangle$ composed with the generic Cohen real. Use the fact that the forcing notion is countable to diagonalize against any finite collections of linear ordering (of any uncountable subset).

    • Thanks Assaf! The third question is the one that started all of this. I’m mostly thinking about it under PFA, but anything will do. Trees won’t work because they are 2-dimensional (lex-order in two opposite ways) but I really like the idea of using a Cohen real as a diagonalization tool. A $\Diamond$ argument also sounds likely though that probably won’t help understanding the PFA situation.

  2. Like Assaf I am also most interested in the third question. I’m having a hard time grokking this dimension idea though.

    Do you mind giving more detail as to why “$\aleph_0 \rightarrow (\aleph_0)^2_2$ means that every infinite poset has an infinite subposet of dimension at most 2.” From there I should be able to start thinking about this problem.

    • Yes, no problem. I’m glad your interested in thinking about this!

      Any linear order has dimension $1$, of course, so an infinite chain in a poset is an infinite subposet of dimension at most $2$. The equality relation on any set $X$ is a partial order of dimension $2$ since $\{=\}$ is the intersection of any linear ordering of $X$ with the reverse of that linear ordering. Therefore, an infinite antichain in a poset is an infinite subposet of dimension at most $2$. The partition relation $\aleph_0 \to (\aleph_0)^2_2$ guarantees that every infinite poset either contains an infinite chain or an infinite antichain, in either case it contains an infinite suposet of dimension at most $2$.

      The Sierpinski coloring that witnesses $\aleph_1 \not \to (\aleph_1)^2_2$ comes from an uncountable $2$-dimensional poset. Recall that this coloring is defined as follows: pick $\aleph_1$ real numbers $\langle r_\alpha \rangle_{\alpha \lt \omega_1}$ then, for each pair $\alpha \lt \beta \lt \omega_1$, define $c(\alpha,\beta) = 1$ when $r_\alpha \lt r_\beta$ and $c(\alpha,\beta) = 0$ when $r_\alpha \gt r_\beta$. Thus $c(\alpha,\beta) = 1$ precisely when $\alpha$ and $\beta$ are comparable in the poset $(\omega_1,{\leq_S})$, where ${\leq_S}$ is the intersection of the usual linear order ${\leq}$ on $\omega_1$ and the linear order on $\omega_1$ defined by $\alpha \leq_R \beta$ iff $r_\alpha \leq r_\beta$. This is a poset of dimension $2$ with no uncountable chains nor uncountable antichains.

 Leave a Reply

(required)

(required)


2 + = nine

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>