A Note on Induced Ramsey Numbers

Abstract

The induced Ramsey number r_(ind)(F) of a k-uniform hypergraph F is the smallest natural number n for which there exists a k-uniform hypergraph G on n vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of F. We study this function, showing that r_(ind)(F) is bounded above by a reasonable power of r(F). In particular, our result implies that r_(ind)(F) ≤ 2_(2_(ct)) for any 3-uniform hypergraph F with t vertices, mirroring the best known bound for the usual Ramsey number. The proof relies on an application of the hypergraph container method.

Files

Additional details