21
$\begingroup$

After reading some books about ordinals I had an impressions that area below $\omega_1$ is thoroughly studied and there is not much new research can be done in it. I hope my impression was wrong. Recently I stumbled upon the sequences A005348 and A199812 in OEIS and was surprised by unexpected connection between ordinals and combinatorics.

So now I am looking for interesting open problems related to countable ordinals, possible having connection to combinatorics or other fields of mathematics. Could you please point me to some resources that can help me, or formulate some problems here?

$\endgroup$
  • 4
    $\begingroup$ There are probably open problems regarding proof theoretic ordinals. I don't really know much on the topic, but it should be a fairly wide topic. Another thing open, I think, is non-computable ordinals by infinite time Turing machines. $\endgroup$ – Asaf Karagila May 3 '13 at 1:25
27
$\begingroup$

There is still much to explore in the area of partition calculus.

The notation $$\alpha\to(\beta,\gamma)^2$$ means that if one colors the $2$-element subsets of $\alpha$ with two colors, red and blue, then there is an $H\subseteq\alpha$, all of whose $2$-sized subsets have the same color and, either the color is red and $H$ has order type $\beta$, or the color is blue and $H$ has order type $\gamma$. (If the superscript if $n$ rather than $2$, then we instead color the $n$-sized subsets, and ask for sets all of whose $n$-sized subsets have the same color.)

The smallest $\alpha$ such that $\alpha\to(\beta,\gamma)^2$ is called the Ramsey number of $\beta$ and $\gamma$, usually denoted $r(\beta,\gamma)$. For example, $r(3,3)=6$, usually stated by saying that in any party of $6$ people, there are at least $3$ that know each other, or at least $3$ that do not know one another, and that this is not the case if the party only has $5$ people. Ramsey proved that $r(\omega,\omega)=\omega$ (the arrow notation itself is due to Rado).

The Erdős-Rado theorem ensures that for every $\beta,\gamma$, there is some $\alpha$ such that $\alpha\to(\beta,\gamma)^2$, so $r(\beta,\gamma)$ exists. One has that $r(\omega,\omega+1)=\omega_1$ but, by a result of Erdős-Milner, $r(\beta,n)$ is countable if $\beta<\omega_1$ and $n<\omega$.

a. The general problem is the study of the numbers $r(\beta,n)$. Their exact determination is known, for example, for $\beta<\omega^2$, in the sense that their computation reduces to problems of finite combinatorics (on the other hand, these problems seem just as hard as the computation of the finite Ramsey numbers, which is a notoriously hard question), but very few precise values have been tabulated. What is known is mostly due partly to Erdős-Rado (the standard reference is A partition calculus in set theory, available here), and partly to Haddad-Sabbagh. Sadly, the proofs of several key results were never published, though there is a series of announcements by Haddad-Sabbagh, available online through Gallica: la bibliothèque numerique, here:

Labib Haddad and Gabriel Sabbagh. Calcul de certains nombres de Ramsey généralisés. C. R. Acad. Sci. Paris Sér. A-B, 268:A1233–A1234, 1969,

Labib Haddad and Gabriel Sabbagh. Nouveaux résultats sur les nombres de Ramsey généralisés. C. R. Acad. Sci. Paris Sér. A-B, 268:A1516–A1518, 1969, and

Labib Haddad and Gabriel Sabbagh. Sur une extension des nombres de Ramsey aux ordinaux. C. R. Acad. Sci. Paris Sér. A-B, 268:A1165–A1167, 1969.

(I am working on a survey that should present proofs of these results. A draft should be available at the end of Summer, 2014.)

Beyond $\omega^2$, Thilo Weinert recently characterized $r(\omega^2m,n)$, in the sense that its computation reduces to problems of finite combinatorics. Thilo's preprint, wonderfully titled Idiosynchromatic Poetry, will soon appear in Combinatorica. Meanwhile, it can be downloaded from his page, currently hosted here. His paper closes with a table containing all explicitly known $r(\alpha,n)$. I think that the table can be considerably expanded, but new ideas are required as $\alpha$ climbs to $\omega^\omega$.

Recently (May, 2014), Thilo has drawn my attention to Eva Nosal's work from the 70s, on computing those numbers $k$ such that $\omega^k \to (\omega^3,n)^2$, and $\omega^k\to (\omega^m, n)^2$ for $5\le m \in \omega$. In her PhD thesis, she shows that $\omega^6\not\to(\omega^4,3)^2$. Unfortunately, I have not yet had the chance to study her results.

b. It is common to call partition ordinals those (countable) ordinals $\alpha$ such that $$\alpha\to(\alpha,3)^2$$ (the notation is probably due to Schipperus). Specker proved that $\omega^2$ is the first partition ordinal past $\omega$ and, in fact, $\omega^2\to(\omega^2,m)^2$ for all $m<\omega$.

[A remark is needed here, since an unfortunately inaccurate edit was added by others to my answer: This proof was significantly simplified by Haddad-Sabbagh (in the first of the notes mentioned above). In Haddad's opinion, the note received practically no attention (see Haddad's Ramsey, for Auld Lang Syne, a write-up of a talk given at the Rencontres arithmétique et combinatoire at Saint-Etienne, June 2006, available at the arXiv here):

As it was, the proof was written down, bare, with no comments or hints. Our note got very little attention, in fact it got almost none! So no further details were ever published.

But this is not true. The Haddad-Sabbagh argument was published in Neil Williams's Combinatorial set theory from 1977, and is nowadays considered the standard approach. Later work by Galvin, Larson, and others, can be clearly seen as extending their ideas, while Specker's original proof is usually omitted from presentations or only studied in historical context.

On the other hand, a key concept introduced in Specker's paper that led to much further work is what we now call the notion of pinning, that Specker used to verify that no other partition ordinals exist below $\omega^\omega$. There are interesting questions with this notion as well, but they all involve uncountable ordinals in an essential way, so I will not discuss them here.]

The next partition ordinal is $\omega^\omega$. This was proved by Chang. Milner extended this in unpublished work to $\omega^\omega\to(\omega^\omega,m)^2$ for all $m<\omega$. A nice proof of this result was then given by Jean Larson, who is the driving force behind research in this area.

Galvin proved that if $\alpha$ is a partition ordinal, then $\alpha=\omega^\beta$, where $\beta$ is additively indecomposable. Baumgartner calls partition ordinals those countable $\alpha$ such that $\alpha\to(\alpha,m)^2$ for all $m<\omega$. For a while it was expected that both definitions were equivalent, but now we know this is not the case, for example, Darby showed that $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$, but it is open whether any countable $\alpha>\omega^\omega$ is a partition ordinal in the sense of Baumgartner. This is perhaps the most important open question in the area. Darby, Larson, and Schipperus have found strong restrictions such $\alpha$ must satisfy. For a nice overview, see the first part of these slides, from a talk by Jean.

c. The truth is that there are many very interesting problems here, and I have to force myself to stop. Though it is not strictly in the spirit of the question, let me close by mentioning $\omega_1$, where the question is precisely what partition relations of the form $\omega_1\to(\alpha,\beta)^n$ hold. More generally, there are several interesting questions and results here (mainly due to Baumgartner-Hajnal, Galvin, Todorcevic, and Jones-Larson), about non-special partial orders, of which $\omega_1$ is an example. We say that a partial order $\phi$ is non-special iff $$\phi\to(\omega)^1_\omega,$$ that is, iff whenever $\phi$ is split into countably many pieces, at least one of them contains an infinite increasing chain. The key problem is whether for such a poset $\phi$, we have $\phi\to(\alpha,n)^3$ for all countable $\alpha$ and $n<\omega$.

(Nothing can be proved if the superscript is $4$ or larger, and just about all that can be proved is known if the superscript is $1$ or $2$.)

$\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.