Thilo Weinert: Transfinite Ramsey Numbers

This is first of three posts kindly written by Thilo Weinert

Recently Gil asked me whether I would like to contribute to his blog and I am happy to do so. I enjoy both finite and infinite combinatorics and it seems that these fields drifted apart in recent decades. The latter is a comment not possibly substantiated by personal experience yet rather by my perception of the number and kinds of papers published. I believe that there is no mathematical reason for this separation but that it came about for reasons of the sociology of mathematics—maybe one should create a chair for this subject somewhere sometimes. Anyhow, I would like to write a few words about an area where finite and infinite combinatorics come together, the partition calculus for ordinal numbers.

The Partition Calculus, contemporarily classified as 03E02 under Mathematical Logic/Set Theory was initiated in 1956 with the article A partition calculus in set theory, published by Paul Erdos and Richard Rado in the Bulletin of the American Mathematical Society. \kappa \rightarrow (\lambda, \mu)^\nu asserts that for every set N of \nu-sized subsets of a set K of size \kappa there is an L \subset K of size \lambda such that all subsets of L of size \nu are in N or an M \subset K of size \mu such that no subset of M of size \nu is in N. Many mathematicians are concerned with the case where \kappa, \lambda, \mu, \nu are finite. As in the finite realm the notions of cardinal number and ordinal number coincide, it is there unnecessary to differentiate between these notions of size. Furthermore, via the Well-Ordering-Theorem, the Axiom of Choice implies that for cardinalities \kappa,\lambda,\mu the statement \kappa\rightarrow(\lambda,\mu)^\nu is equivalent to \bar{\kappa}\rightarrow(\bar{\lambda}, \bar{\mu})^\nu where \bar{\zeta} denotes the smallest ordinal number of cardinality \zeta. It also implies that there is no \kappa such that \kappa\rightarrow(\omega, \omega)^\omega. Hence, believing the Axiom of Choice, one may limit ones study to the cases in which \kappa,\lambda,\mu are order-types and \nu is a natural number. Although there are interesting open questions in contexts where the Axiom of Choice fails and also in contexts where not all of \kappa,\lambda,\mu are ordinal numbers, I will for now exclude these from the discussion. That is, what I would like to talk about is the subject of transfinite Ramsey Numbers, \kappa=r_\nu(\lambda,\mu) is to say that \kappa\rightarrow(\lambda, \mu)^\nu but \zeta\rightarrow(\lambda,\mu)^\nu for no \zeta<\kappa.

First I would like to discuss the lower storeys of the transfinite. It is known that generally for a countable ordinal \lambda and a natural number \mu the Ramsey number r_2(\lambda, \mu) is countable (If no subscript appears it is understood to be 2). When \lambda is a finite multiple of \omega or \omega^2, the number’s calculation is similar in character to the case where \lambda is a natural number though it tends to be slightly more involved. For example r_2(\omega\ell, m)=\omega r(I_\ell, L_m) where r(I_\ell, L_m) is the least number n without a digraph on n vertices without an independent \ell-tuple and without an induced transitive subtournament on m vertices. The r(I_2, L_n)'s are the Tournament Ramsey Numbers which have been investigated slightly more intensely in [1], [2] and exact values are known for \ell \leqslant 6. The last paper on these problems was published in 1997 by Jean Larson and William Mitchell in the very first issue of the Annals of Combinatorics. A degree argument yields r(I_\ell,L_3)\leq\ell^2 which gives a good idea about the growth rate of r(I_\ell, L_3) as counterexamples to numbers being finite Ramsey numbers easily carry over. Furthermore they found a digraph on thirteen vertices without a transitive triple or independent quadruple thus establishing r(I_\ell, L_3) \in \{14, 15, 16\}.

Recently I started to discuss these problems with Ferdinand Ihringer and Deepak Rajendraprasad. The latter found a digraph with the two aforementioned properties but on fourteen vertices and shortly thereafter they could establish by a triangle-count that there is no such digraph on 15 vertices. So we know now that r(I_4, L_3) = 15. Generally these problems should provide a nice playground for people in the business of solving Ramsey-type problems with the help of computers, cf. [3].

The situation is slightly more complicated in the case of finite multiples of \omega^2 as a degree argument only yields a cubic upper bound for r(I_\ell,A_3) which is a number defined such that r(\omega^2\ell,m)=\omega^2r(I_\ell,A_m) for all natural numbers \ell and m. This is elaborated on in detail in [4].

Recently Jacob Hilton has considered problems of this kind involving additional topological structure alone (cf. [5]) and together with Andr\'{e}s Caicedo (cf. [6]).

In the next post I am going to elaborate on results and open questions
regarding Ramsey numbers for larger countable ordinals.

[1] Kenneth Brooks Reid, Jr. and Ernest Tilden Parker. Disproof of a conjecture of
Erdos and Moser on tournaments. J. Combinatorial Theory, 9 (1970).

[2] Adolfo Sanchez-Flores. On tournaments and their largest transitive subtournaments.
Graphs Combin., 10, 1994.

[3] Stanislaw P. Radziszowski. Small Ramsey numbers. Electron. J. Combin., 1:Dynamic
Survey 1, 30 pp. (electronic), 1994,

[4] Thilo Volker Weinert, Idiosynchromatic poetry. Combinatorica, 34 (2014).

[5] Andres Eduardo Caicedo and Jacob Hilton, Topological Ramsey numbers and countable ordinals.

[6] Jacob Hilton. The topological pigeonhole principle for ordinals.

Advertisements
This entry was posted in Combinatorics, Guest post, Logic and set theory and tagged . Bookmark the permalink.

3 Responses to Thilo Weinert: Transfinite Ramsey Numbers

  1. Nice post, Thilo. I think there is an extra dot in the URL for [6].

  2. Souktik Roy says:

    This was very interesting, looking forward to the next post. The current link for [3] doesn’t seem to work by the way, but I think this should: http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS1/pdf

  3. Gil Kalai says:

    Dear Peter and Souktik, many thanks –Gil

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s