Natasha Dobrinen: Ramsey Theory of the Henson graphs

Abstract: A central question in the theory of ultrahomogeneous relational structures asks, How close of an analogue to the Infinite Ramsey Theorem does it carry? An infinite structure S is ultrahomogeneous if any isomorphism between two finitely generated substructures of S can be extended to an automorphism of S. We say that S has finite big Ramsey degrees if for each finite substructure A of S, there is a number n(A) such that any coloring of the copies of A in S can be reduced to no more than n(A) colors on some substructure S of S, which is isomorphic to the original S.

The two main obstacles to a fuller development of this area have been lack of representations and general Milliken-style theorems. We will present new work proving that the Henson graphs, the kk-clique free analogues of the Rado graph for k3, have finite big Ramsey degrees. We devise representations of Henson graphs via strong coding trees and prove Milliken-style theorems for these trees. Central to the proof is the method of forcing, building on Harrington’s proof of the Halpern-Läuchli Theorem.


Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.