Kurt Gödel Research Center

Mini-course “Infinitary Ramsey Theory”, part II: Ramsey theory on trees and applications to big Ramsey degrees

Mini-course given by Natasha Dobrinen (University of Denver, Colorado, USA) at the KGRC seminar on 2019‑01‑09. (See also part I.)

Abstract

The Infinite Ramsey Theorem states that given $n,r\ge 1$ and a coloring of all $n$-sized subsets of $\mathbb{N}$ into $r$ colors, there is an infinite subset of $\mathbb{N}$ in which all $n$-sized subsets have the same color. There are several natural ways of extending Ramsey's Theorem. One extension is to color infinite sets rather than finite sets. In this case, the Axiom of Choice precludes a full-fledged generalization, but upon restricting to definable colorings, much can still be said. Another way to extend Ramsey's Theorem is to color finite sub-objects of an infinite structure, requiring an infinite substructure isomorphic to the original one. While it is not possible in general to obtain substructures on which the coloring is monochromatic, sometimes one can find bounds on the number of colors, and this can have implications in topological dynamics.

Part II will focus on Ramsey theory on trees and their applications to Ramsey theory of homogeneous structures. An infinite structure is homogeneous if each isomorphism between two finite substructures can be extended to an automorphism of the infinite structure. The rationals as a linearly ordered structure and the Rado graph are prime examples of homogeneous structures. Given a coloring of singletons in the rationals, one can find a subset isomorphic to the rationals in which all singletons have the same color. However, when one colors pairs of rationals, there is a coloring due to Sierpinski for which any subset isomorphic to the rationals has more than one color on its pairsets. This is the origin of the theory of big Ramsey degrees, a term coined by Kechris, Pestov and Todorcevic, which investigates bounds on colorings of finite structures inside infinite structures. Somewhat surprisingly, a theorem of Halpern and Läuchli involves colorings of products of trees, discovered en route to a proof that the Boolean Prime Ideal Theorem is strictly weaker than the Axiom of Choice, is the heart of most results on big Ramsey degrees. We will survey big Ramsey degree results on countable and uncountable structures and related Ramsey theorems on trees, including various results of Dobrinen, Devlin, Džamonja, Hathaway, Larson, Laver, Mitchell, Shelah, and Zhang.

There is a video recording of this course on YouTube.

The slides for this talk are available, too.

Time and Place

Course at 10:30am in the KGRC lecture room