Induced Ramsey Numbers

   We investigate the induced Ramsey number of pairs of graphs (G, H). This number is defined to be the smallest possible order of a graph Γ with the property that, whenever its edges are coloured red and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that, for any G and H with , we have where is the chromatic number of H and C is some universal constant. Furthermore, we also investigate imposing some conditions on G. For instance, we prove a bound that is polynomial in both k and t in the case in which G is a tree. Our methods of proof employ certain random graphs based on projective planes. Received: October 10, 1997