François G. Dorais

Topics
• Combinatorics
• Reverse Mathematics
• Set Theory

Subposets of small dimension

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

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 MathOverflow (Dorais 2010). Observing that the dimension of a finite poset never exceeds its width, Goodwillie (2010) answered that $F_d(n) \geq \sqrt{dn}$ for sufficiently large $n$. 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 Denis Hirschfeldt and Richard Shore. In their paper (Hirschfeldt–Shore 2007), 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 (Moore 2006), 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, 2010: Subposets of small Dushnik-Miller dimension, MathOverflow question 29169.

   • mathoverflow.net/q/29169

2. T. Goodwillie, 2010: Subposets of small Dushnik-Miller dimension, MathOverflow answer 29570.

   • mathoverflow.net/a/29570

3. D. R. Hirschfeldt, R. A. Shore, 2007: Combinatorial principles weaker than Ramsey’s theorem for pairs, J. Symbolic Logic 72, no. 1, 171–206.

   • mr: 2298478

   • zbl: 1118.03055

   • doi: 10.2178/jsl/1174668391

4. J. T. Moore, 2006: A five element basis for the uncountable linear orders, Ann. of Math. (2) 163, no. 2, 669–688.

   • mr: 2199228

   • zbl: 1143.03026

   • doi: 10.4007/annals.2006.163.669

Originally posted on February 18, 2012, by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.

Comments

• Peter Krautzberger wrote on February 21, 2012, at 05:11

  Great post!

  ---

• Assaf Rinot wrote on February 23, 2012, at 03:11

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

  ---

• François G. Dorais replied to Assaf Rinot on February 23, 2012, at 20:10

  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.

  ---

• Micheal Pawliuk wrote on February 29, 2012, at 18:14

  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.

  ---

• François G. Dorais replied to Micheal Pawliuk on February 29, 2012, at 18:48

  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.

  ---