Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 9, 2017 | Submitted
Book Section - Chapter Open

A Note on Induced Ramsey Numbers


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.

Additional Information

© Springer International publishing AG 2017. First Online 09 May 2017. The first author was supported by a Royal Society University Research Fellowship. The fourth author was partially supported by NSF grants DMS-1102086 and DMS-1301698. The fifth author was supported through the Heisenberg-Programme of the DFG. Dedicated to the memory of Jirka Matoušek.

Attached Files

Submitted - 1601.01493.pdf


Files (492.9 kB)
Name Size Download all
492.9 kB Preview Download

Additional details

August 19, 2023
October 18, 2023