It is known that Ramsey property is a kind of generalizition of pigeon hole principle, and some kinds of Ramsey properties have lots of equivalent forms. We often deal with the case $a\rightarrow (b)^r_c $,when $a,b,c$ are cardinals; however, if we consider the ordertype of the homogeneous set, the question becomes much more complicated.

For instance, we can prove that any two-coloring of $\omega_1$ must have a homogeneous subset of ordertype $\omega+1$, rather than only stating that can have a countable homogeneous subset. And also it's easy to show that for any countable ordinal $\alpha$, $\alpha\rightarrow (\omega+1)^2_2$ fails.

I wonder: what is the least ordinal $c$ such that any 2-coloring of $c$ must have a homogeneous set of ordertype $\omega+2$? And can one prove that for any ordinal $b$, the least ordinal $a$ with $a\rightarrow b^2_2$ must be a cardinal?

In this case, the properties of such $a$ is quite different from Erdős cardinal, any tricks used to show an Erdős cardinal must be inaccessible fail here.

  • $\begingroup$ Related. $\endgroup$ – Andrés E. Caicedo Aug 6 '13 at 4:01
  • $\begingroup$ If $b$ is a cardinal, then the least $a$ such that $a\rightarrow b^2_2$ holds must also be a cardinal. Suppose otherwise, let $a$ be the least such ordinal with cardinality $a'<a$. Fix a bijection $f: a\cong a'$. Then given a 2-coloring $c$ of $a'$, we get an induced 2-coloring on $a$ by pulling back along $f$. Let $H$ be a hom. set for $c'$ of ordertype $b$; then $f(H)$ is homogeneous for $c$, and has cardinality $\vert b\vert$, so must have order type at least $b$. If $b$ is not a cardinal, though, I think this might fail: consider $a\rightarrow b^1_2$ with $b=\omega+1$. $\endgroup$ – Noah Schweber Aug 6 '13 at 4:04
  • $\begingroup$ @NoahS Namely, $a=\omega_1$. $\endgroup$ – Andrés E. Caicedo Aug 6 '13 at 4:05
  • $\begingroup$ The least such $a$ is $\omega2+1$, which is not a cardinal. Now, coloring pairs is different from coloring points, but I take this as evidence that if $b$ is not a cardinal, the statement that the minimal such $a$ must be a cardinal is probably false in general. $\endgroup$ – Noah Schweber Aug 6 '13 at 4:06
  • 1
    $\begingroup$ Jiachen, welcome to MathOverflow! ...and when I am next in Shanghai again, let's be sure to make proper time for a full game of go. $\endgroup$ – Joel David Hamkins Aug 6 '13 at 5:11

For $b=\omega+2$, see

András Hajnal. Some results and problems on set theory, Acta Math. Acad. Sci. Hungar., 11, (1960), 277–298. MR0150044 (27 #47).

In this paper, András shows that $\omega_1\to(\omega\cdot n,\omega\cdot 2)^2_2$ for all $n<\omega$. This is best possible, in the sense that if $\alpha$ is countable, then $\alpha\not\to(\omega,\omega+1)^2_2$.

He also shows that $\mathsf{CH}$ implies that $\omega_1\not\to(\omega_1,\omega+2)^2_2$. I seem to remember Stevo saying that the same negative relation follows from adding a Cohen real, though I do not have details of the proof.

On the other hand, Stevo showed that the following statement $(1)$ is consistent: $$\omega_1\to(\omega_1,\alpha)^2_2\mbox{ for all countable ordinals }\alpha $$ (in fact, he established a significant strengthening). His argument uses proper forcing, and it follows that $\mathsf{PFA}$ implies (1) (though no large cardinals are needed to establish its consistency together with $\mathsf{MA}+2^{\aleph_0}=\aleph_2$). See

Stevo Todorcevic. Forcing positive partition relations, Trans. Amer. Math. Soc., 280 (2), (1983), 703–720. MR0716846 (85d:03102).

As Péter Komjáth pointed out in a comment, there is a generalization of András result I should mention: The Baumgartner-Hajnal theorem states that if $\alpha<\omega_1$, then $$ \omega_1\to(\alpha)^2_2, $$ provably in $\mathsf{ZFC}$. This solves your problem, as long as $b$ is countable.

In fact, Baumgartner-Hajnal admits a significant generalization that was pursued by several authors, most notably Fred Galvin and Stevo: Say that a poset $\phi$ is non-special iff $\phi\to(\omega)^1_\omega$. Any such poset satisfies $\phi\to(\alpha)^2_2$ for any countable $\alpha$, and this is best possible, since $\phi\to(\omega,\omega+1)^2_2$ already implies that $\phi$ is non-special. See

James Baumgartner, and András Hajnal. A proof (involving Martin's axiom) of a partition relation, Fund. Math., 78 (3), (1973), 193–203. MR0319768 (47 #8310),


Stevo Todorcevic. Partition relations for partially ordered sets, Acta Math., 155 (1-2),(1985), 1–25. MR0793235 (87d:03126).

For the general case, $b$ an arbitrary ordinal, not much seems known. There is of course the Erdős-Rado theorem, that gives in particular that if $\kappa$ is regular, then $$ (2^{<\kappa})^+\to(\kappa+1)^2_\mu \mbox{ for all }\mu<\kappa, $$ and this is best possible in that no ordinal smaller than $(2^{<\kappa})^+$ works here, even if $\mu=2$.

This has been somewhat extender by James Baumgartner, András, and Stevo. See

James E. Baumgartner, András Hajnal, and Stevo Todorcevic. Extensions of the Erdős-Rado theorem. In Finite and infinite combinatorics in sets and logic (Banff, AB, 1991), pp. 1–17, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 411, Kluwer Acad. Publ., Dordrecht, 1993. MR1261193 (95c:03111).

There, they show that if $\kappa$ is regular and uncountable, then forall $k<\omega$ and $\xi<\log\kappa$ (where $\log\kappa$ is the least cardinal $\mu$ such that $2^\mu\ge\kappa$), we have $$ (2^{<\kappa})^+\to(\kappa+\xi)^2_k. $$ They also show that, under the same assumption on $\kappa$, $(2^{<\kappa})^+\to(\rho,(\kappa+n)_k)^2$, where $\rho=\kappa^{\omega+2}+1$ (ordinal exponentiation) and, improving results of Saharon Shelah, (the only result here where the ordinal on the left is not a cardinal) for all $n<\omega$, $$ (2^{<\kappa})^+·\omega\to(\kappa·n)^2_2. $$ (On the other hand, I do not see any evidence that the ordinal on the left is least possible, or that a cardinal does not work.)

A good reference for the state of the art on partition calculus is

András Hajnal, and Jean A. Larson. Partition relations. In Handbook of set theory. Vols. 1, 2, 3, Akihiro Kanamori, and Matthew Foreman, eds., pp. 129–213, Springer, Dordrecht, 2010.

What follows comes from this paper, to which I refer for additional references (the numbers listed in brackets are as in their bibliography). In page 152, they write:

It was already asked in the Erdős-Hajnal problem lists [12, 13] if the partition relations $\omega_2\to(\alpha)^2_2$ were consistent for $\alpha<\omega_2$. Though there is nothing to refute such consistency, the results going in this direction are weak and rare.

They add that Richard Laver [$40$] showed, under appropriate assumptions of large cardinal character, that $\omega_2\to(\omega_1\cdot2+1,\alpha)^2_2$ for all $\alpha<\omega_2$. In general, Richard showed that $\kappa^+\to(\kappa\cdot2+1,\alpha)^2_2$ for all $\alpha<\kappa^+$, provided that $\kappa$ carries a Laver ideal, that is, a non-trivial, $\kappa$-complete ideal such that given $\kappa^+$ sets not in the ideal, there are $\kappa^+$ of them, the intersection of any fewer than $\kappa$ of these also not in the ideal.

For $\omega_2$, the best result I recall is due to Matthew Foreman and András Hajnal. In [$20$] they show, under appropriate large cardinal assumptions, that $\omega_2\to(\omega_1^2+1,\alpha)^2_2$ for all $\alpha<\omega_2$. They also proved that if $\kappa$ is measurable, there is an ordinal $\Omega(\kappa)$ smaller than $\kappa^+$, but closed under of ordinal addition, multiplication, exponentiation, and taking fixed points of these operations, such that $$ \kappa^+\to(\alpha)^2_m\mbox{ for all }\alpha<\Omega(\kappa).$$ For the precise definition of $\Omega(\kappa)$, see Section 5 of the Hajnal-Larson paper.

Finally, Shelah [$59$] showed that if $\kappa$ is strongly compact, $\lambda>\kappa$ is a cardinal, and either $\lambda$ is regular or $\mathrm{cf}(\lambda)\ge\kappa$, then $$ (2^{<\lambda})^+\to(\lambda+\zeta)^2_\theta\mbox{ for all }\zeta,\theta<\kappa. $$

  • $\begingroup$ The Baumgartner-Hajnal theorem should not be left out: $\omega_1\to(\alpha)^2_2$ for all $\alpha<\omega_1$. $\endgroup$ – Péter Komjáth Aug 6 '13 at 11:25
  • $\begingroup$ (@PéterKomjáth I have expanded the answer, including Baumgartner-Hajnal and a bit more.) $\endgroup$ – Andrés E. Caicedo Aug 6 '13 at 20:37

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.