The structure of hereditary properties and colourings of random graphs

We answer two fundamental questions about hereditary properties of random g raphs. First, does there exist a simple and easily described property that closely approximates the hereditary property P in the probability space G(n ,p)? Second, does there exist a constant c(p)(P) such that the P-chromatic number of the random graph G(n,p) is almost surely (c(p)(P) + o(1))n/2log(2 ) n? The second question was posed by Scheinerman (SIAM J. Discrete Math. 5 (1992) 74-80). The two questions are closely related and, in the case p=1/2, have already been answered. Promel and Steger (Contemporary Mathematics 147, Amer. Math. Sec., Providence, 1993, pp. 167-178), Alekseev (Discrete Math. Appl. 3 (19 93) 191-199) and the authors (Algorithms and Combinatorics 14 Springer-Verl ag (1997) 70-78) provided an approximation which was used by the authors (R andom Structures and Algorithms 6 (1995) 353-356) to answer the P-chromatic question for p=1/2. However, the approximating properties that work well f or p=1/2 fail completely for p not equal 1/2. In this paper we describe a class of properties that do approximate P in G( n,p), in the following sense: for any desired accuracy of approximation, th ere is a property in our class that approximates p to this level of accurac y. As may be expected, our class includes the simple properties used in the case p=1/2. The main difficulty in answering the second of our two questions, that conc erning the P-chromatic number of G(n,p), is that the number of small P-grap hs in G(n,p) has, in general, large variance. The variance is smaller if we replace p by a simple approximation, but it is still not small enough. We overcome this by considering instead a very rigid nonhereditary subproperty Q of the approximating property; the variance of the number of small Q-gra phs is small enough for our purpose, and the structure of Q is sufficiently restricted to enable us to show this by a fine analysis.