Ramsey Theory on Infinite Graphs

Abstract: The Finite Ramsey Theorem states that given any positive integers k, m, and r, there is an integer n such that for any coloring of the k-element subsets of n into r colors, there is a subset of size m on which the coloring is constant. The Infinite Ramsey Theorem states that given any positive integer k, for any coloring of the k-element subsets of the natural numbers into finitely many colors, there is an infinite set of natural numbers on which the coloring is constant. Ramsey theory on graphs can be studied from both of these vantage points. While finite graphs support outright analogues of the finite Ramsey theorem, the infinite case turns out to be extra intriguing. Vertex colorings may be reduced to one color on a sub-graph isomorphic to original infinite graphs, but already colorings of pairs of vertices preclude direct analogues of the infinite Ramsey theorem. However, bounds on the number of colors on an isomorphic copy of the infinite graph can still sometimes be found. We will present ideas of how upper bounds are found for the Rado graph (infinite random graph) using the structure of binary trees. This involves various works of Laflamme, Larson, Sauer, and Vuksanovic. Recently, the speaker developed methods for handling Henson graphs (the k-clique-free random graphs). We will present some of the basic ideas of these methods, which open up investigation of other relational structures with forbidden configurations.