Corrine Yap, Rutgers University

Abstract

A central open problem in Ramsey theory is to determine the behavior of r_3(t), the minimum n such that any 2-coloring of the complete 3-uniform hypergraph on n vertices contains a monochromatic complete subgraph on t vertices. In the 1960's, Erdős, Hajnal, and Rado showed that r_3(t) is bounded between exponential and double-exponential in t, but the correct behavior remains unknown. Erdős and Hajnal surprisingly showed that the double-exponential bound is correct if we use four colors instead of two. This raises the question: how does the number of colors influence the growth of the Ramsey number? Generalizing a result of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower gaps between the 2-color and q-color Ramsey numbers. We utilize results analogous to the Erdős-Hajnal stepping-up lemma, for Ramsey numbers where we relax the "monochromatic" condition to "spanning few colors." Joint work with Quentin Dubroff, Eoin Hurley, and António Girão.