You are here

Random Graphs, Geometry and Asymptotic Structure

Michael Krivelevich, Konstatntinos Panagiotou, Matthew Penrose, and Colin McDiarmid
Cambridge University Press
Publication Date: 
Number of Pages: 
London Mathematical Society Student Texts 84
[Reviewed by
Miklós Bóna
, on

The area of random graphs is huge, and because of that, sometimes intimidating for newcomers. This short volume intends to change that via four chapters that provide an in-depth introduction to four aspects of random graphs that are not usually presented in introductory courses.

Three of the four chapters study aspects of the structure of random graphs: Krivelevich discusses long paths and Hamiltonicity, Panagiotou focuses on random trees and random block-stable graphs, while McDiarmid covers classes of random graphs that are closed under taking minors. The remaining chapter, by Penrose, is devoted to random geometric graphs, that is, graphs whose spatial realization matters.

The chapter on geometric graphs has plenty of exercises, while the other chapters do not have any at all, which is not ideal in a book in a Student Text Series. Still, the book will help many novices make their first steps in the field of random graphs.

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

Editors' introduction

Part I. Long Paths and Hamiltonicity in Random Graphs:
1. Introduction
2. Tools
3. Long paths in random graphs
4. The appearance of Hamilton cycles in random graphs
References for Part I

Part II. Random Graphs from Restricted Classes:
1. Introduction
2. Random trees
3. Random graphs from block-stable classes
References for Part II

Part III. Lectures on Random Geometric Graphs:
1. Introduction
2. Edge counts
3. Edge counts: normal approximation
4. The maximum degree
5. A sufficient condition for connectivity
6. Connectivity and Hamiltonicity
7. Solutions to exercises
References for Part III

Part IV. On Random Graphs from a Minor-closed Class:
1. Introduction
2. Properties of graph classes
3. Bridge-addability, being connected and the fragment
4 Growth constants
5. Unlabelled graphs
6. Smoothness
7. Concluding remarks
References for Part IV