An Acyclic Spin on the Classical Ramsey Numbers

Marshall Kaatz (University of Manitoba)

Ramsey numbers have gained notoriety over the last century for the difficulty of computing exact values or even improving known bounds, and have given rise to a large family of Ramsey-type problems. The classical theorem of Ramsey can be rephrased in terms of independent sets: in large enough graphs, either the graph or its complement will have a large independent set.

In this talk, I present a natural analogous problem to that of the classical Ramsey numbers. Observing that an independent set is a special case of an acyclic set in a graph — that is, a set of vertices which induces no cycles — we instead study how in large enough graphs, either the graph or its complement will have a large acyclic set. In addition to presenting key theorems and constructions, I will discuss some small non-trivial exact values and best-known bounds.

 Overview  Program