THE SIZE-RAMSEY NUMBER OF TREES

If G and H are graphs, let us write G --> (H)(2) if G contains a monochromatic copy of H in any 2-colouring of the edges of G. The size-Ramsey number r(e)(H) of a graph H is the smallest possible number of edges a graph G may have if G --> (H)(2). Suppose T is a tree of order \T\ greater than or equal to 2, and let t(0), t(1) be the cardinalities of the vertex classes of T as a bipartite graph, and let Delta(T) be the maximal degree of T. Moreover, let Delta(0), Delta(1) be the maxima of the degrees of the vertices in the respective vertex classes, and let beta(T) = t(0) Delta(0) + t(1) Delta(1). Beck [7] proved that beta(T)/4 less than or equal to r(e)(T) = O{beta(T)(log\T\)(12)}, improving on a previous result of his [6] stating that r(e)(T) less than or equal to Delta(T)\T\(log\T\)(12). In [6], Beck conjectures that r(e)(T) = O{Delta(T)\T\}, and in [7] he puts forward the stronger conjecture that r(e)(T) = O{beta(T)}. Here, we prove the first of these conjectures, and come quite close to proving the second by showing that r(e)(T) = O{beta(T) log Delta(T)}.