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 :
- Let denote the largest number such that every poset of size has a -dimensional subposet of size . What is the asymptotic growth of ?
- Every (countably) infinite poset has an infinite subposet of dimension at most . What is the logical strength of this statement over ?
- Is there an uncountable poset that has no uncountable -dimensional subposet?
In all three cases, dimension refers to the Dushnik–Miller dimension of the poset , which is the smallest number of linear orders on the set such that
for all . In other words, when thinking of each relation as a set of ordered pairs. Equivalently, for countable and finite posets, this is the smallest number such that is embeddable in 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 for sufficiently large . This feels correct for , but it doesn’t feel optimal for . (No, I don’t have a concrete reason why I feel that way.) Goodwillie’s argument (for general ) runs as follows. Let be a poset of size and width . If then, by definition, has an antichain of size at least . Since antichains have dimension at most , we’re done. If then, by Dilworth’s Theorem, can be partitioned into chains of average size at least . If is large enough, the union of the largest chains in this partition forms a -dimensional subposet of with size at least . 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 (), which is the statement that every (countably) infinite poset either has an infinite chain or an infinite antichain. Since chains have dimension and antichains have dimension , this immediately implies that every infinite poset has an infinite subposet of dimension at most . Hirschfeldt and Shore also studied the Ascending-Descending Sequence Principle (), which they show is equivalent to the restriction of to -dimensional posets (Theorem 5.3). A straightforward induction shows that is equivalent to the restriction of to -dimensional posets for any standard integer . Although Hirschfeldt and Shore show that is strictly weaker than Ramsey’s Theorem for pairs and two colors (), it is still an open question whether is strictly weaker than . This is where the second problem comes in. If proves that every infinite poset has an infinite subposet of dimension at most then is equivalent to , if not then we have a separation of and .
The third question may be a little surprising. In the infinite case, the partition relation guarantees that every infinite poset has an infinite subposet of dimension at most . Since is false, it may seem unlikely that every uncountable poset has an uncountable -dimensional subposet. However, Sierpiński’s classical argument to prove that simply shows that there is an uncountable -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 or its reverse
- An -dense set of reals
- A Countryman line or its reverse
Sierpiński’s counterexample is the comparability graph of the two-dimensional poset obtained by combining and . Similar counterexamples can be made by combining and , or and , or all three , , and . 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!
F. G. Dorais, 2010: Subposets of small Dushnik-Miller dimension, MathOverflow question 29169.
T. Goodwillie, 2010: Subposets of small Dushnik-Miller dimension, MathOverflow answer 29570.
D. R. Hirschfeldt, R. A. Shore, 2007: Combinatorial principles weaker than Ramsey’s theorem for pairs, J. Symbolic Logic 72, no. 1, 171–206.
J. T. Moore, 2006: A five element basis for the uncountable linear orders, Ann. of Math. (2) 163, no. 2, 669–688.
Peter Krautzberger wrote
Assaf Rinot wrote
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 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 argument also sounds likely though that probably won’t help understanding the PFA situation.
Micheal Pawliuk wrote
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 “ 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 , of course, so an infinite chain in a poset is an infinite subposet of dimension at most . The equality relation on any set is a partial order of dimension since is the intersection of any linear ordering of with the reverse of that linear ordering. Therefore, an infinite antichain in a poset is an infinite subposet of dimension at most . The partition relation 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 .
The Sierpinski coloring that witnesses comes from an uncountable -dimensional poset. Recall that this coloring is defined as follows: pick real numbers then, for each pair , define when and when . Thus precisely when and are comparable in the poset , where is the intersection of the usual linear order on and the linear order on defined by iff . This is a poset of dimension with no uncountable chains nor uncountable antichains.