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.