On two problems in graph Ramsey theory

DOI10.1007/S00493-012-2710-3MaRDI QIDQ377800zbMATH OpenOpenAlexFDO

Authors David Conlon, Jacob Fox, Benny Sudakov

Publication date 7 November 2013

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1002.0045, https://resolver.caltech.edu/CaltechAUTHORS:20190812-162958859

zbMATH Keywords

bounded degree induced Ramsey Ramsey theory

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph

K_{N}

contains a monochromatic copy of H. A famous result of Chv'atal, R"{o}dl, Szemer'edi and Trotter states that there exists a constant c(Delta) such that r(H) leq c(Delta) n for every graph H with n vertices and maximum degree Delta. The important open question is to determine the constant c(Delta). The best results, both due to Graham, R"{o}dl and Ruci'nski, state that there are constants c and c' such that 2^{c' Delta} leq c(Delta) leq 2^{c Delta log^2 Delta}. We improve this upper bound, showing that there is a constant c for which c(Delta) leq 2^{c Delta log Delta}. The induced Ramsey number r_{ind}(H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. ErdH{o}s conjectured the existence of a constant c such that, for any graph H on n vertices, r_{ind}(H) leq 2^{c n}. We move a step closer to proving this conjecture, showing that r_{ind} (H) leq 2^{c n log n}. This improves upon an earlier result of Kohayakawa, Pr"{o}mel and R"{o}dl by a factor of log n in the exponent.

Review text

It is proved that if \(G\) is a graph of order \(n\) and with maximum degree \(\Delta\), then the Ramsey number \(r(G) \leq c(\Delta)n\) with \(c(\Delta) \leq 2^{c\Delta\log \Delta}\). This improves the bound \(c(\Delta) \leq 2^{c\Delta\log^2 (\Delta)}\) proved by \textit{R. L. Graham} et al. in [J. Graph Theory 35, No. 3, 176--192 (2000; Zbl 0965.05073)]. The induced Ramsey number \(r_{\mathrm{ind}}(G)\) is the least positive integer \(n\) for which there exists a graph \(H\) on \(n\) vertices such that in any \(2\)-coloring of the edges of \(H\) there is a monochromatic induced copy of \(G\). It was conjectured by Erdős that there is a constant \(c\) such that \(r_{\mathrm{ind}}(G) \leq 2^{cn}\). The authors prove that \(r_{\mathrm{ind}}(G) \leq 2^{cn \log n}\), which improves on the previous best bound of \textit{Y. Kohayakawa} et al. in [Combinatorica 18, No. 3, 373-404 (1998; Zbl 0913.05074)]. They also prove the following result: There is a constant \(c\) such that for any positive integer \(n\) and any \((1/2,\lambda)\)-pseudo-random graph \(G\) on \(N\) vertices with \(\lambda \leq 2^{-cn \log n}N\), every graph on \(n\) vertices occurs as an induced monochromatic copy (in the same color) in all \(2\)-edge colorings of \(G\).

Recommendations

Cites work

Cited in

(36)

This page was built for publication: On two problems in graph Ramsey theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q377800)