Sold Out
Book Categories |
Preface | ||
Notation | ||
1 | Probability Theoretic Preliminaries | 1 |
1.1 | Notation and Basic Facts | 1 |
1.2 | Some Basic Distributions | 5 |
1.3 | Normal Approximation | 9 |
1.4 | Inequalities | 15 |
1.5 | Convergence in Distribution | 25 |
2 | Models of Random Graphs | 34 |
2.1 | The Basic Models | 34 |
2.2 | Properties of Almost all Graphs | 43 |
2.3 | Large Subsets of Vertices | 46 |
2.4 | Random Regular Graphs | 50 |
3 | The Degree Sequence | 60 |
3.1 | The Distribution of an Element of the Degree Sequence | 60 |
3.2 | Almost Determined Degrees | 65 |
3.3 | The Shape of the Degree Sequence | 69 |
3.4 | Jumps and Repeated Values | 72 |
3.5 | Fast Algorithms for the Graph Isomorphism Problem | 74 |
4 | Small Subgraphs | 78 |
4.1 | Strictly Balanced Graphs | 79 |
4.2 | Arbitrary Subgraphs | 85 |
4.3 | Poisson Approximation | 91 |
5 | The Evolution of Random Graphs - Sparse Components | 96 |
5.1 | Trees of Given Sizes As Components | 96 |
5.2 | The Number of Vertices on Tree Components | 102 |
5.3 | The Largest Tree Components | 110 |
5.4 | Components Containing Cycles | 117 |
6 | The Evolution of Random Graphs - the Giant Component | 130 |
6.1 | A Gap in the Sequence of Components | 130 |
6.2 | The Emergence of the Giant Component | 138 |
6.3 | Small Components after Time n/2 | 143 |
6.4 | Further Results | 148 |
6.5 | Two Applications | 153 |
7 | Connectivity and Matchings | 160 |
7.1 | The Connectedness of Random Graphs | 161 |
7.2 | The k-Connectedness of Random Graphs | 166 |
7.3 | Matchings in Bipartite Graphs | 171 |
7.4 | Matchings in Random Graphs | 178 |
7.5 | Reliable Networks | 189 |
7.6 | Random Regular Graphs | 195 |
8 | Long Paths and Cycles | 201 |
8.1 | Long Paths in G[subscript c/n] - First Approach | 202 |
8.2 | Hamilton Cycles- First Approach | 206 |
8.3 | Hamilton Cycles- Second Approach | 212 |
8.4 | Long Paths in G[subscript c/n]-Second Approach | 219 |
8.5 | Hamilton Cycles in Regular Graphs - First Approach | 221 |
8.6 | Hamilton Cycles in Regular Graphs - Second Approach | 224 |
9 | The Automorphism Group | 229 |
9.1 | The Number of Unlabelled Graphs | 229 |
9.2 | The Asymptotic Number of Unlabelled Regular Graphs | 241 |
9.3 | Distinguishing Vertices by Their Distance Sequences | 243 |
9.4 | Asymmetric Graphs | 245 |
9.5 | Graphs with a Given Automorphism Group | 248 |
10 | The Diameter | 251 |
10.1 | Large Graphs of Small Diameter | 251 |
10.2 | The Diameter of G[subscript p] | 254 |
10.3 | The Diameter of Random Regular Graphs | 264 |
10.4 | Graph Processes | 267 |
10.5 | Related Results | 271 |
10.6 | Small Worlds | 276 |
11 | Cliques, Independent Sets and Colouring | 282 |
11.1 | Cliques in G[subscript p] | 282 |
11.2 | Poisson Approximation | 290 |
11.3 | Greedy Colouring of Random Graphs | 294 |
11.4 | The Chromatic Number of Random Graphs | 298 |
11.5 | Sparse Graphs | 303 |
12 | Ramsey Theory | 319 |
12.1 | Bounds on R(s) | 320 |
12.2 | Off-Diagonal Ramsey Numbers | 324 |
12.3 | Triangle-Free Graphs | 332 |
12.4 | Dense Subgraphs | 339 |
12.5 | The Size-Ramsey Number of a Path | 341 |
13 | Explicit Constructions | 348 |
13.1 | Character Sums | 348 |
13.2 | The Paley Graph P[subscript q] | 357 |
13.3 | Dense Graphs | 365 |
13.4 | Sparse Graphs | 373 |
13.5 | Pseudorandom Graphs | 376 |
14 | Sequences, Matrices and Permutations | 383 |
14.1 | Random Subgraphs of the Cube | 384 |
14.2 | Random Matrices | 394 |
14.3 | Balancing Families of Sets | 399 |
14.4 | Random Elements of Finite Groups | 408 |
14.5 | Random Mappings | 412 |
15 | Sorting Algorithms | 425 |
15.1 | Finding Most Comparisons in One Round | 426 |
15.2 | Sorting in Two Rounds | 431 |
15.3 | Sorting with Width n/2 | 435 |
15.4 | Bin Packing | 442 |
16 | Random Graphs of Small Order | 447 |
16.1 | Connectivity | 447 |
16.2 | Independent Sets | 448 |
16.3 | Colouring | 451 |
16.4 | Regular Graphs | 455 |
References | 457 | |
Index | 496 |
Login|Complaints|Blog|Games|Digital Media|Souls|Obituary|Contact Us|FAQ
CAN'T FIND WHAT YOU'RE LOOKING FOR? CLICK HERE!!! X
You must be logged in to add to WishlistX
This item is in your Wish ListX
This item is in your CollectionRandom Graphs
X
This Item is in Your InventoryRandom Graphs
X
You must be logged in to review the productsX
X
X
Add Random Graphs, 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, Random Graphs to the inventory that you are selling on WonderClubX
X
Add Random Graphs, 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, Random Graphs to your collection on WonderClub |