Logic Seminar
Natasha Dobrinen
Denver
Fraisse classes with simply characterized big Ramsey degrees
Abstract: Analogues of the infinite Ramsey theorem to infinite structures have been studied since the 1930’s, when Sierpinski 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. Such a coloring is called “unavoidable” since both colors persist in any infinite substructure isomorphic to the original (in this case the rationals as a linear order). In the 1970’s Galvin showed that two is the optimum number for pairs of rationals, while Erdos, Hajnal and Posa extended Sierpinski’s result to colorings of edges in the Rado graph. These results instigated a steady stream of results for the next several decades, a pinnacle of which was the work of Laflamme, Sauer, and Vuksanovic finding the exact number of colors for unavoidable colorings of finite graphs inside the Rado graph, as well as other Fraisse 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 Todorcevic.
In this talk, we will provide a brief overview of the area of big Ramsey degrees on Fraisse limits. Then we will present recent joint work with Rebecca Coulson and Rehana Patel characterizing the big Ramsey degrees for some seemingly disparate Fraisse classes. We formulate an amalgamation property, which we call the Substructure Free Amalgamation Property, and show that every Fraisse relational class with finitely many relations satisfying SFAP has big Ramsey degrees which are characterized in a manner as simply as those of the Rado graph. A more general property for disjoint amalgamation classes, which we call SDAP^+, also ensures the same simple characterization of big Ramsey degrees. One of the novelties of our approach is that we build trees of quantifier-free 1-types with special nodes coding the vertices in a given enumerated Fraisse limit. Then we use the method of forcing to do an unbounded search for a finite object, which produces in ZFC the exact big Ramsey degrees for these structure. SDAP^+ holds for unrestricted relational structures, relational structures with forbidden 3-irreducible substructures, and others, producing new lines of results while recovering in a streamlined manner several previous results, including those of Laflamme, Sauer, and Vuksanovic.
If you are interested in attending the seminar and joining the mailing list, please write jfreitag@uic.edu an email.
Tuesday March 9, 2021 at 4:00 PM in the internet