113.
In 1983, Chvátal, Trotter and the two senior authors proved that for any Δ there exists a constant
B such that, for any
n, any 2-colouring of the edges of the complete graph
KN with
N?
Bn vertices yields a monochromatic copy of any graph
H that has
n vertices and maximum degree Δ. We prove that the complete graph may be replaced by a sparser graph
G that has
N vertices and edges, with
N=⌈
B′n⌉ for some constant
B′ that depends only on Δ. Consequently, the so-called
size-Ramsey number of any
H with
n vertices and maximum degree Δ is . Our approach is based on random graphs; in fact, we show that the classical Erd?s–Rényi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic
universal graph for the class of graphs on
n vertices and maximum degree Δ.The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed.
相似文献