CaltechAUTHORS
  A Caltech Library Service

A Note on Induced Ramsey Numbers

Conlon, David and Dellamonica, Domingos and La Fleur, Steven and Rödl, Vojtěch and Schacht, Mathias (2017) A Note on Induced Ramsey Numbers. In: A Journey Through Discrete Mathematics. Springer International Publishing , Cham, Switzerland, pp. 357-366. ISBN 9783319444789. https://resolver.caltech.edu/CaltechAUTHORS:20190812-162959255

[img] PDF - Submitted Version
See Usage Policy.

481Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190812-162959255

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/978-3-319-44479-6_13DOIArticle
https://link.springer.com/chapter/10.1007/978-3-319-44479-6_13PublisherArticle
https://link.springer.com/book/10.1007/978-3-319-44479-6PublisherBook
https://arxiv.org/abs/1601.01493arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
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.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
NSFDMS-1102086
NSFDMS-1301698
Deutsche Forschungsgemeinschaft (DFG)UNSPECIFIED
Record Number:CaltechAUTHORS:20190812-162959255
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190812-162959255
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97826
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:14 Aug 2019 16:53
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page