2 1. Graphs and Probability The Cartesian product of two sets A and B is written A x B , while their difference is written A\B. As the results we present are often asymptotic, let us formalize some notation. Let / and g be functions whose domain is some fixed subset of R. We write / G 0(g) if v / ( * ) hm sup —— exists and is finite. This is equivalent to saying that there is a constant c 0 (not depending on x) and an integer N 0 such that for x N, f(x) cg(x). We will abuse notation and write / = O(g). We write / = il(g) if g = O(f), and / = 9(g) if / = O(g) and / = Q(g). If li m 4 4 = 0, a—o o g(a J then / = o(g) (or g = u(f)). So if / = o(l), then / tends to 0. We write f ~ 9 if li m M _ !. x^oo g[x) Let x and y be non-negative, real-valued variables. We write logx for the natural logarithm of x (sometimes called \nx). If x is a real number, then 1 + x ex. We will sometimes write ex as exp(x), especially if x is a complicated expression. If 0 m n are integers with n 0, then ( - ) • \ U ) - T n r .ml ml 1.2. Graph Theory Graphs are beautiful combinatorial objects, whose recorded history stretches back to work by Leonhard Euler, who used graphs to solve the Konigsberg bridge problem [101]. A graph G consists of a non-empty vertex set V(G), and an edge set E(G) of unordered 2-element sets from V(G). A graph is sometimes called network, especially with regards to real-world examples. More formally, we may consider E{G) as a binary relation on V(G) which is irreflexive and symmetric. We often write G = (V(G),E(G)), or if G is clear from the context, G — (V, E). The set E may be empty. Elements of V(G) are vertices, and elements of E(G) are edges. Vertices are occasionally referred to as nodes or points, while edges are referred to as lines or links. We write uv for an edge {u, v}, and say that u and v are joined or adjacent we say that u and v are incident to the edge uv, and that u and v are the endpoints of uv. The most important graph for us is the web graph, where vertices rep- resent web pages, and the edges correspond to links between the pages. We

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2008 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.