The ACO Seminar (2016–2017)

The Rado graph (aka the countable random graph) is the unique countable graph G which is:

1. Universal, that is G contains an induced copy of every finite graph.
2. Homogeneous, that is any isomorphism between finite induced subgraphs of G extends to an automorphism of G.

The construction of the Rado graph works with many classes of finite structures (the Fraïssé classes), assigning to each Fraïssé class a countable, universal and homogeneous structure called the Fraïssé limit.

Ramsey theory on relational structures can be studied from two vantage points. The first, more classical, is to study when, given two finite structures A and B and given any k greater than 1, there is another finite structure C such that for any coloring of all copies of A in C into k colors, there is a copy of B in C in which all copies of A have the same color. A Fraïssé class of finite relational structures has the Ramsey property if this holds for any two structures A and B in the class. Nešetřil and Rödl have shown that many classes of finite ordered relational structures have the Ramsey property, including finite ordered graphs and finite ordered triangle-free graphs.

The second, and of much recent interest, is to study colorings of copies of a finite structure inside an infinite homogenous structure, usually the Fraïssé limit of some Fraïssé class of finite structures. It has been shown that any finite coloring of the vertices of the Rado graph can be reduced to one color on a subgraph which is also a Rado graph. For edges and other structures with more than one vertex, Sauer has proved this to be impossible. However, he also proved that given a finite graph A, there is a number n(A) such that any coloring of all copies of A in the Rado graph into finitely many colors may be reduced to n(A) colors on a copy of the Rado graph. We say, then, that the Rado graph has finite big Ramsey degrees. Similar results have been obtained for other countable homogeneous structures, though many are still open.

We have looked at the problem of finite big Ramsey degrees for the universal triangle-free graph H, that is, the homogeneous graph with no triangles into which every countable triangle-free graph embeds. This is the first homogeneous structure omitting a subtype to be addressed for big Ramsey degrees. Using the method of forcing, but in ZFC, we prove a new Ramsey theorem on trees which code H, and apply it to deduce that H has finite big Ramsey degrees.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.