Big Ramsey degrees in binary free amalgamation classes

Abstract: In structural Ramsey theory, one considers a "small" structure $A$, a "medium" structure $B$, a "large" structure $C$ and a number $r$, then considers the following combinatorial question: given a coloring of the copies of $A$ inside $C$ in $r$ colors, can we find a copy of $B$ inside $C$ all of whose copies of $A$ receive just one color? For example, when $C$ is the rational linear order and $A$ and $B$ are finite linear orders, then this follows from the finite version of the classical Ramsey theorem. More generally, when $C$ is the Fraisse limit of a free amalgamation class in a finite relational language, then for any finite $A$ and $B$ in the given class, this can be done by a celebrated theorem of Nesetril and Rodl. Things get much more interesting when both $B$ and $C$ are infinite. For example, when $B$ and $C$ are the rational linear order and $A$ is the two-element linear order, a pathological coloring due to Sierpinski shows that this cannot be done. However, if we weaken our demands and only ask for a copy of $B$ inside $C$ whose copies of $A$ receive "few" colors, rather than just one color, we can succeed. For the two-element linear order, we can get down to two colors. For the three-element order, $16$ colors. This number of colors is called the big Ramsey degree of a finite structure in a Fraisse class. Recently, building on groundbreaking work of Dobrinen, I proved a generalization of the Nesetril-Rodl theorem to binary free amalgamation classes defined by a finite forbidden set of irreducible structures (for instance, the class of triangle-free graphs), showing that every structure in every such class has a finite big Ramsey degree. My work only bounded the big Ramsey degrees, and left open what the exact values were. In recent joint work with Balko, Chodounsky, Dobrinen, Hubicka, Konecny, and Vena, we characterize the exact big Ramsey degree of every structure in every binary free amalgamation class defined by a finite forbidden set.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.