| Summary: | 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 twocoloring
of the edges of the complete graph KN contains a monochromatic copy of H. A famous
result of Chv atal, Rodl, Szemer edi and Trotter states that there exists a constant c( Delta) such that
r(H) c(Delta )n for every graph H with n vertices and maximum degree . The important open
question is to determine the constant c(Delta ). The best results, both due to Graham, Rodl and
Ruci nski, state that there are constants c and c0 such that 2c0 Delta[less than or equal to] c( Delta) 2c Deltalog2Delta . We improve this upper bound, showing that there is a constant c for which c(Delta )[less than or equal to] 2cDelta log Delta.
The induced Ramsey number rind(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. Erdos conjectured the existence of a constant c such that,
for any graph H on n vertices, rind(H) 2cn. We move a step closer to proving this conjecture,
showing that rind(H)[less than or equal to] 2cn log n. This improves upon an earlier result of Kohayakawa, Promel and Rodl by a factor of log n in the exponent.
|
|---|