随机图(第2版) 内容简介

The period since the publication of the first edition of this book has seen the theory of random graphs go from strength to strength. Indeed, its appearance happened to coincide with a watershed in the subject; the emergence in the subsequent few years of singnificant new ideas and tools, perhaps most noteably concentration methods, has had a major impact. It could be argued that the subject is now qualitatively different, insofar as results which would previously have been inaccessible are now regarded as routine. Several long standing issues have been resolved, including the value of the chromatic number of a random graph $G-{n,p}$, the existence of Hamilton cycles in random cubic graphs, and precise bounds on certain Ramsey numbers. It remains the case, though, that most of the material in the first edition of the book is vital for gaining an insight into the theory of random graphs.

随机图(第2版) 本书特色

The period since the publication of the first edition of this book has seen the theory of random graphs go from strength to strength. Indeed, its appearance happened to coincide with a watershed in the subject; the emergence in the subsequent few years of singnificant new ideas and tools, perhaps most noteably concentration methods, has had a major impact. It could be argued that the subject is now qualitatively different, insofar as results which would previously have been inaccessible are now regarded as routine. Several long standing issues have been resolved, including the value of the chromatic number of a random graph $G-{n,p}$, the existence of Hamilton cycles in random cubic graphs, and precise bounds on certain Ramsey numbers. It remains the case, though, that most of the material in the first edition of the book is vital for gaining an insight into the theory of random graphs.

随机图(第2版) 目录

Preface Notation 1 Probability Theoretic Preliminaries 1.1 Notation and Basic Facts 1.2 Some Basic Distributions 1.3 Normal Approximation 1.4 Inequalities 1.5 Convergence in Distribution 2 Models of Random Graphs 2.1 The Basic Models 2.2 Properties of Almost All Graphs 2.3 Large Subsets of Vertices 2.4 Random Regular Graphs 3 The Degree Sequence 3.1 The Distribution of an Element of the Degree Sequence 3.2 Almost Determined Degrees 3.3 The Shape of the Degree Sequence 3.4 Jumps and Repeated Values 3.5 Fast Algorithms for the Graph Isomorphism Problem 4 Small Subgraphs 4.1 Strictly Balanced Graphs4.2 Arbitrary Subgraphs4.3 Poisson Approximation5 The Evolution of Random Graphs-Spare Components5.1 Trees of Given Sizes As Components5.2 The Number of Vertices on Tree Components5.3 The Largest Tree Components5.4 Components Containing Cycles6 The Evolution of Random Graphs-the Giant Component6.1 A Gap in the Sequence of Components6.2 The Emergence of the Giant Component6.3 Small Components after Time6.4 Further Results6.5 Two Applications7 Connectivity and Matchings7.1 The Connectedness of Random Graphs7.2 The k-Gonnectedness of Random Graphs7.3 Matchings in Bipartite Graphs7.4 Matchings in Random Craphs7.5 Reliable Networks7.6 Random Regular Graphs8 Long Paths and Cycles9 The Automorphism Group10 The Diameter11 Cliques,Independent Sets and Colouring12 Ramsey Theory13 Explicit Constructions14 Sequences,Matrices and Permutations15 Sorting Algorithms 16 Random Graphs of Small OrderReferencesIndex