Textbook in PDF format This is a new edition of the now classic text. The already extensive treatment given in the first edition has been heavily revised by the author. The addition of two new sections, numerous new results and 150 references means that this represents an up-to-date and comprehensive account of random graph theory. The theory estimates the number of graphs of a given degree that exhibit certain properties. It not only has numerous combinatorial applications, but also serves as a model for the probabilistic treatment of more complicated random structures. This book, written by an acknowledged expert in the field, can be used by mathematicians, computer scientists and electrical engineers, as well as people working in biomathematics. It is self contained, and with numerous exercises in each chapter, is ideal for advanced courses or self study. Contents Preface page Xl Notation XVll Probability Theoretic Preliminaries Notation and Basic Facts 1 Some Basic Distributions 5 Normal Approximation 9 Inequalities Convergence in Distribution Models of Random Graphs The Basic Models Properties of Almost All Graphs Large Subsets of Vertices Random Regular Graphs The Degree Sequence The Distribution of an Element of the Degree Sequence Almost Determined Degrees The Shape of the Degree Sequence Jumps and Repeated Values Fast Algorithms for the Graph Isomorphism Problem Small Subgraphs Strictly Balanced Graphs Arbitrary Subgraphs Poisson Approximation The Evolution of Random Graphs-Sparse Components Trees of Given Sizes As Components The Number of Vertices on Tree Components The Largest Tree Components Components Containing Cycles The Evolution of Random Graphs-the Giant Component A Gap in the Sequence of Components The Emergence of the Giant Component Small Components after Time nl2 Further Results Two Applications Connectivity and Matchings The Connectedness of Random Graphs The k-Connectedness of Random Graphs Matchings in Bipartite Graphs Matchings in Random Graphs Reliable Networks Random Regular Graphs Long Paths and Cycles Long Paths in Gcjn-First Approach Hamilton Cycles-First Approach Hamilton Cycles-Second Approach Long Paths in Gcfn-Second Approach Hamilton Cycles in Regular Graphs-First Approach Hamilton Cycles in Regular Graphs-Second Approach The Automorphism Group The Number of Unlabelled Graphs The Asymptotic Number of Unlabelled Regular Graphs Distinguishing Vertices by Their Distance Sequences Asymmetric Graphs Graphs with a Given Automorphism Group The Diameter Large Graphs of Small Diameter The Diameter of G p The Diameter of Random Regular Graphs Graph Processes Related Results Small Worlds Cliques, Independent Sets and Colouring Cliques in G p Poisson Approximation Greedy Colouring of Random Graphs The Chromatic Number of Random Graphs Sparse Graphs Ramsey Theory Bounds on R(s) Off-Diagonal Ramsey Numbers Triangle-Free Graphs Dense Subgraphs The Size-Ramsey Number of a Path Explicit Constructions Character Sums The Paley Graph Pq Dense Graphs Sparse Graphs Pseudorandom Graphs Sequences, Matrices and Permutations Random Subgraphs of the Cube Random Matrices Balancing Families of Sets Random Elements of Finite Groups Random Mappings Sorting Algorithms Finding Most Comparisons in One Round Sorting in Two Rounds Sorting with Width n/2 Bin Packing Random Graphs of Small Order Connectivity Independent Sets Colouring Regular Graphs References Index