CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar


ACO/Logic Seminar
Natasha Dobrinen
University of Denver
Title: The big Ramsey degrees for the universal triangle-free graph

Abstract: 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Üetril 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.

Date: Thursday, April 27, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Note: before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220