You are here

Introduction to Random Graphs

Alan Frieze and Michał Karoński
Cambridge University Press
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Miklós Bóna
, on

This is a well-planned book that is true to its title in that it is indeed accessible for anyone with just an undergraduate student’s knowledge of Enumerative Combinatorics and Probability.

The book has four parts, the longest of which is the first one. Just that part has sufficient material in it for a one-semester graduate course. Its topic is the basic models of the area. There are several ways one can select a random graph on \(n\) vertices. One is by fixing the number \(m\) of edges in advance, and then select each graph with \(n\) vertices and \(m\) edges with the same probability, or one can decide one by one, for each pair of vertices, whether an edge will connect them or not. The authors describe the connections between these two models, and they analyze the natural parameters (like diameter, vertex degree, connectivity, and spanning subgraphs) in them.

Part two is about the extensions of the basic models, and their generalizations to directed graphs and hypergraphs. Part three focuses on other models, such as trees, permutations, mappings and weighted graphs. There is one chapter with brief remarks about numerous topics that are not covered in the book. Finally, and this is again a good idea, the last part is a collection of methods that are used in the field. This will be a frequently consulted reference for researchers and students working on random graphs.

Almost all chapters end with a few exercises, and a helpful Notes section that discusses recent research of the covered topic. I wish there were more exercises, and that some of them had their solutions included. Still, this is a very useful and very needed book. The authors, commendably, typically did not try to present the strongest result of a given subfield, but they presented the one that illustrated a given proof technique the best.

To summarize, various parts of the book can be used as a textbook, as a book for researchers to learn new methods, and as a reference material. This reviewer may well use the book in all of those ways.

Miklós Bóna is Professor of Mathematics at the University of Florida.


Part I. Basic Models:
1. Random graphs
2. Evolution
3. Vertex degrees
4. Connectivity
5. Small subgraphs
6. Spanning subgraphs
7. Extreme characteristics
8. Extremal properties

Part II. Basic Model Extensions:
9. Inhomogeneous graphs
10. Fixed degree sequence
11. Intersection graphs
12. Digraphs
13. Hypergraphs

Part III. Other Models:
14. Trees
15. Mappings
16. k-out
17. Real-world networks
18. Weighted graphs
19. Brief notes on uncovered topics

Part IV. Tools and Methods:
20. Moments
21. Inequalities
22. Differential equations method
23. Branching processes
24. Entropy

Author index
Main index.