Caltech Logo

Logic Seminar

Monday, March 29, 2021
12:00pm to 1:00pm
Add to Cal
Online Event
Fraïssé classes with simply characterized big Ramsey degrees
Natasha Dobrinen, Department of Mathematics, University of Denver,

Analogues of the infinite Ramsey Theorem to infinite structures have been studied since the 1930s, when Sierpiński gave a coloring of pairs of rationals into two colors such that, in any subset of the rationals forming a dense linear order, both colors persist. In the 1970s Galvin showed that two is the optimum number for pairs of rationals, while Erdős, Hajnal and Pósa extended Sierpiński's result to colorings of edges in the Rado graph. The next several decades saw a steady advance of results for other structures, a pinnacle of which was the 2006 work of Laflamme, Sauer, and Vuksanović, characterizing the exact number of colors for unavoidable colorings of finite graphs inside the Rado graph, and for similar Fraïssé structures with finitely many binary relations, including the generic tournament. This exact number is called the "big Ramsey degree", a term coined by Kechris, Pestov, and Todorčević.

In this talk, we will provide a brief overview of the area of big Ramsey degrees infinite structures. Then we will present recent joint work with Coulson and Patel, showing that free amalgamation classes, in which any forbidden substructures are 33-irreducible, have big Ramsey degrees which are simply characterized. These results extend to certain strong amalgamation classes as well, extending the results of Laflamme, Sauer, and Vuksanović. This is in contrast to the more complex characterization of big Ramsey degrees for binary relational free amalgamation classes with forbidden 22-irreducible substructures, obtained in joint work of the speaker with Balko, Chodounský, Hubička, Konečný, Vena, and Zucker. The work with Coulson and Patel develops coding trees of quantifier-free 11-types and uses forcing to do an unbounded search for monochromatic finite objects. Furthermore, we work with skew subtrees with branching degree two which still code the Fraïssé limit. This allows for more ease when working with relations of arity greater than two, and also allows us to give the first proof of exact big Ramsey degrees bypassing the standard method of "envelopes". It also sets the stage for current work of the speaker on infinite-dimensional Ramsey theory, in the vein of Galvin-Příkrý, for Fraïssé limits of free amalgamation classes in which any forbidden substructures are 33-irreducible.

For more information, please email A. Kechris at [email protected].