This monograph provides and explains the mathematics behind geometric graph theory, which studies the properties of a graph that consists of nodes placed in Euclidean space so that edges can be added to connect points that are close to one another. For example, a collection of trees scattered in a forest and the disease that is passed between them, a set of nests of animals or birds on a region and the communication between them or communication between communications stations or nerve cells. Aimed at graduate students and researchers in probability, statistics, combinatorics and graph theory including computer scientists, it covers topics such as: technical tools, edge and component counts, vertex degrees, clique and chromatic number, and connectivity. Applications of this theory are used in the study of neural networks, spread of disease, astrophysics and spatial statistics.
Author(s): Mathew Penrose
Year: 2003
Language: English
Pages: 345
Tags: Математика;Дискретная математика;Теория графов;
0198506260......Page 1
Contents......Page 8
Notation......Page 12
1.1 Motivation and history......Page 16
1.2 Statistical background......Page 19
1.3 Computer science background......Page 22
1.4 Outline of results......Page 24
1.5 Some basic definitions......Page 26
1.6 Elements of probability......Page 29
1.7 Poissonization......Page 33
1.8 Notes and open problems......Page 36
2.1 Dependency graphs and Poisson approximation......Page 37
2.2 Multivariate Poisson approximation......Page 40
2.3 Normal approximation......Page 42
2.4 Martingale theory......Page 48
2.5 De-Poissonization......Page 52
2.6 Notes......Page 61
3 Subgraph and component counts......Page 62
3.1 Expectations......Page 63
3.2 Poisson approximation......Page 67
3.3 Second moments in a Poisson process......Page 70
3.4 Normal approximation for Poisson processes......Page 75
3.5 Normal approximation: de-Poissonization......Page 80
3.6 Strong laws of large numbers......Page 84
3.7 Notes......Page 88
4 Typical vertex degrees......Page 89
4.1 The setup......Page 90
4.2 Laws of large numbers......Page 91
4.3 Asymptotic covariances......Page 93
4.4 Moments for de-Poissonization......Page 97
4.5 Finite-dimensional central limit theorems......Page 102
4.6 Convergence in Skorohod space......Page 106
4.7 Notes and open problems......Page 108
5.1 Consequences of the Lebesgue density theorem......Page 110
5.2 Covering, packing, and slicing......Page 112
5.3 The Brunn–Minkowski inequality......Page 117
5.4 Expanding sets in the orthant......Page 119
6 Maximum degree, cliques, and colourings......Page 124
6.1 Focusing......Page 125
6.2 Subconnective laws of large numbers......Page 133
6.3 More laws of large numbers for maximum degree......Page 135
6.4 Laws of large numbers for clique number......Page 141
6.5 The chromatic number......Page 145
6.6 Notes and open problems......Page 149
7.1 Thresholds in smoothly bounded regions......Page 151
7.2 Strong laws for thresholds in the cube......Page 160
7.3 Strong laws for the minimum degree......Page 166
7.4 Notes......Page 169
8 Minimum degree: convergence in distribution......Page 170
8.1 Uniformly distributed points I......Page 171
8.2 Uniformly distributed points II......Page 175
8.3 Normally distributed points I......Page 182
8.4 Normally distributed points II......Page 188
8.5 Notes and open problems......Page 191
9.2 Connectivity and Peierls arguments......Page 192
9.3 Bernoulli percolation......Page 195
9.4 k-Dependent percolation......Page 201
9.5 Ergodic theory......Page 202
9.6 Continuum percolation: fundamentals......Page 203
10 Percolation and the largest component......Page 209
10.1 The subcritical regime......Page 210
10.2 Existence of a crossing component......Page 215
10.3 Uniqueness of the giant component......Page 220
10.4 Sub-exponential decay for supercritical percolation......Page 225
10.5 The second-largest component......Page 231
10.6 Large deviations in the supercritical regime......Page 235
10.7 Fluctuations of the giant component......Page 239
10.8 Notes and open problems......Page 245
11.1 The subcritical case......Page 246
11.2 The supercritical case on the cube......Page 249
11.3 Fractional consistency of single-linkage clustering......Page 255
11.4 Consistency of the RUNT test for unimodality......Page 262
11.5 Fluctuations of the giant component......Page 267
11.6 Notes and open problems......Page 272
12.1 Background on layout problems......Page 274
12.2 The subcritical case......Page 277
12.3 The supercritical case......Page 283
12.4 The superconnectivity regime......Page 290
12.5 Notes and open problems......Page 294
13 Connectivity and the number of components......Page 296
13.1 Multiple connectivity......Page 297
13.2 Strong laws for points in the cube or torus......Page 298
13.3 SLLN in smoothly bounded regions......Page 304
13.4 Convergence in distribution......Page 310
13.5 Further results on points in the cube......Page 317
13.6 Normally distributed points......Page 321
13.7 The component count in the thermodynamic limit......Page 324
13.8 Notes and open problems......Page 331
References......Page 333
H......Page 343
S......Page 344
W......Page 345
