2 edited body

This is an elaboration of a comment on Suvrit's answer.

Ramsey numbers can be defined for (infinite) ordinals, just as in the finite case: $r(\alpha,\beta)$ is the least $\gamma$ such that for any $2$-coloring of the edges of the complete graph on $\gamma$ vertices there is a set of vertices of type $\alpha$ whose induced graph is red, or a set of vertices of type $\beta$ whose induced graph is blue.

Ramsey's theorem gives that $r(\omega,\omega)=\omega$, but already $r(\omega+1,\omega)=\omega_1$. On the other hand, if $\alpha\lt\omega_1$ and $n$ is finite, then $r(\alpha,n)\lt\omega_1$, and for reasonably small infinite values of $\alpha$, one can attempt to compute $r(\alpha,n)$ explicitly. It turns out that this computation reduces to (Ramsey-theoretic) finite problems, which, just as with the classic computation of finite Ramsey numbers, quickly become unfeasible.

For example:

• $r(\omega+3,3)=\omega\cdot2 + 8$. In general, if $0\lt n,m\lt\omega$, then $$r(\omega+n,m)=\omega\cdot(m-1)+(g(n,m)-(m-1)),$$ where $g(n,m)$ is the least $k$ such that any $2$-coloring of the edges of the complete graph on set of vertices $\{1,\dots,k\}$ such that the induced graph on $C=\{1,\dots,m-1\}$ is blue, either admits a blue $K_m$, or a red $K_{n+1}$ with one of its vertices in $C$.

This was first established by Haddad and Sabbagh in 1969. One has $r(n+1,m)\le g(n,m)\lt\infty$, but typically the first inequality is strict. For example, $r(4,3)=9$ but $g(4,3)=10$. g(3,3)=10$. In general, computing$g(n,m)$is similar to, but harder than computing$r(n+1,m)$. •$r(\omega\cdot3,3)=\omega\cdot9$. In general, if$0\lt n,m\lt\omega$, then $$r(\omega\cdot n,m)=\omega\cdot l(n,m),$$ where$l(n,m)$is the least$k$such that any$2$-coloring of the edges of the complete digraph on$k$vertices either contains a red complete digraph on$n$vertices, or a blue transitive tournament on$m$vertices. Here, in complete digraphs we have two arrows (going in opposite directions) between any two distinct vertices. This was shown by Erdős and Rado in 1955. As with$g$, the computation of the values of$l(n,m)$quickly becomes unfeasible. •$r(\omega^2\cdot2,3)=\omega^2\cdot10$. In general, if$0\lt n,m\lt\omega$, then$r(\omega^2\cdot m,n)=\omega^2\cdot h(m,n)$for a Ramsey-theoretic function$h$related to$3$-colorings of the edges of digraphs, though its exact description is somewhat technical to include here. This was shown fairly recently by Thilo Weinert, see here. 1 [made Community Wiki] This is an elaboration of a comment on Suvrit's answer. Ramsey numbers can be defined for (infinite) ordinals, just as in the finite case:$r(\alpha,\beta)$is the least$\gamma$such that for any$2$-coloring of the edges of the complete graph on$\gamma$vertices there is a set of vertices of type$\alpha$whose induced graph is red, or a set of vertices of type$\beta$whose induced graph is blue. Ramsey's theorem gives that$r(\omega,\omega)=\omega$, but already$r(\omega+1,\omega)=\omega_1$. On the other hand, if$\alpha\lt\omega_1$and$n$is finite, then$r(\alpha,n)\lt\omega_1$, and for reasonably small infinite values of$\alpha$, one can attempt to compute$r(\alpha,n)$explicitly. It turns out that this computation reduces to (Ramsey-theoretic) finite problems, which, just as with the classic computation of finite Ramsey numbers, quickly become unfeasible. For example: •$r(\omega+3,3)=\omega\cdot2 + 8$. In general, if$0\lt n,m\lt\omega$, then $$r(\omega+n,m)=\omega\cdot(m-1)+(g(n,m)-(m-1)),$$ where$g(n,m)$is the least$k$such that any$2$-coloring of the edges of the complete graph on set of vertices $\{1,\dots,k\}$ such that the induced graph on $C=\{1,\dots,m-1\}$ is blue, either admits a blue$K_m$, or a red$K_{n+1}$with one of its vertices in$C$. This was first established by Haddad and Sabbagh in 1969. One has$r(n+1,m)\le g(n,m)\lt\infty$, but typically the first inequality is strict. For example,$r(4,3)=9$but$g(4,3)=10$. In general, computing$g(n,m)$is similar to, but harder than computing$r(n+1,m)$. •$r(\omega\cdot3,3)=\omega\cdot9$. In general, if$0\lt n,m\lt\omega$, then $$r(\omega\cdot n,m)=\omega\cdot l(n,m),$$ where$l(n,m)$is the least$k$such that any$2$-coloring of the edges of the complete digraph on$k$vertices either contains a red complete digraph on$n$vertices, or a blue transitive tournament on$m$vertices. Here, in complete digraphs we have two arrows (going in opposite directions) between any two distinct vertices. This was shown by Erdős and Rado in 1955. As with$g$, the computation of the values of$l(n,m)$quickly becomes unfeasible. •$r(\omega^2\cdot2,3)=\omega^2\cdot10$. In general, if$0\lt n,m\lt\omega$, then$r(\omega^2\cdot m,n)=\omega^2\cdot h(m,n)$for a Ramsey-theoretic function$h$related to$3\$-colorings of the edges of digraphs, though its exact description is somewhat technical to include here. This was shown fairly recently by Thilo Weinert, see here.