Chapter 1 Graphs and Probability Mathematical discoveries, small or great, are never born of spontaneous gen- eration. They always presuppose a soil seeded with preliminary knowledge and well prepared by labour, both conscious and subconscious. -Henri Poincare He who has not first laid his foundations may be able with great ability to lay them afterwards, but they will be laid with trouble to the architect and danger to the building. -Niccolo Machiavelli 1.1. Introduction Graphs are the central objects we study, and a number of the results we present on the web graph are probabilistic. This chapter supplies the reader with the necessary background and notation in both graph theory and dis- crete probability theory to read the remainder of this book. Since both subjects are so expansive, we will focus on material that we will use later in the text. The reader who would like additional background in graph theory is directed to [31], [84], or [195], while a good discrete probability reference is [122]. The reader with background in both subjects may safely move on to the next chapter. We will use the following notation throughout. The set of natural num- bers (which contains 0) is written N, while the rationals and reals are denoted by Q and R, respectively. The cardinality of N is Ko, while the cardinality of K. is 2K°. If n is a positive natural number, then we define [n] = { 1 , . . . , n}. 1 http://dx.doi.org/10.1090/gsm/089/01

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.