Published May 9, 2017
| Version Submitted
Book Section - Chapter
Open
A Note on Induced Ramsey Numbers
-
1.
University of Oxford
-
2.
Emory University
-
3.
Universität Hamburg
Contributors
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.
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
1601.01493.pdf
Additional details
Identifiers
- Eprint ID
- 97826
- DOI
- 10.1007/978-3-319-44479-6_13
- Resolver ID
- CaltechAUTHORS:20190812-162959255
Related works
- Describes
- 10.1007/978-3-319-44479-6_13 (DOI)
- https://arxiv.org/abs/1601.01493 (URL)
Funding
- Royal Society
- NSF
- DMS-1102086
- NSF
- DMS-1301698
- Deutsche Forschungsgemeinschaft (DFG)
Dates
- Created
-
2019-08-14Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
Caltech Custom Metadata
- Caltech groups
- Mathematics Department