oo very slowly as a function of t, then with probability 1 - 2 exp(- 22 ), Xt lies in an interval around X0 of length 2AV/t-.

Chapter 3 Random Graphs God does not play dice. -Albert Einstein So God does play dice with the universe. All the evidence points to him being an inveterate gambler, who throws the dice on every possible occasion. 1. Introduction Graphs and probability mix well. Random graphs are important in the study of the web graph, and are a central tool in modern graph theory and theoretical computer science. The models of W that we will study in Chapter 4 incorporate randomness in their design. Knowledge of random graphs is, therefore, an important adjunct to understanding web graph models.

There are (q - 1) - 1 = (q - 3) many squares in 2 GF(q) distinct from I. Let a be such a square. As 2there is a unique solution to z-u_l+v-u=a zv z-v it follows that s(u, v) = 2 (q - 3). Hence, E Is(u) v) u,vEV (Gn) 1 (q-3) 2 q 2 u,vEV (G q 2) 3 (q2 3 2 o(q3). q 2 - q) 4 D The next result demonstrates that sufficiently large Paley graphs are n-e. c. 7 Q299 38]). c. 7 in [29, 38] each use a famous result from number theory on character sum estimates, namely Weil's proof of the Riemann hypothesis over finite fields.