Bollobas B. Random Graphs

Second Edition. — Cambridge University Press, 2001. — ISBN: 0521797225, 978-0521797221.
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
Notation
Probability Theoretic Preliminaries
Notation and Basic Facts
Some Basic Distributions
Normal Approximation
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 n/2
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 Gc/n-First Approach
Hamilton Cycles-First Approach
Hamilton Cycles-Second Approach
Long Paths in Gc/n-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 Gp
The Diameter of Random Regular Graphs
Graph Processes
Related Results
Small Worlds
Cliques, Independent Sets and Colouring
Cliques in Gp
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Добавлен OCR-слой