random regular and random geometric graphs

These two models sit at opposite ends of the random-graph spectrum and complement Erdos-Renyi. A random d-regular graph is a uniformly random graph in which every vertex has exactly degree d — the most homogeneous possible degree sequence, and a model with no degree fluctuation at all. A random geometric graph (RGG) is the opposite: vertices are points scattered at random in space (say n uniform points in the unit square or n Poisson points in a region) and two are joined whenever they lie within a fixed distance r — a model with built-in geometry and strong local clustering. The question they answer is: what happens to random-graph phenomena when we remove degree randomness (regular) or when we add real geometry (geometric)?

The random d-regular graph for fixed d >= 3 is best generated and analyzed by the configuration model conditioned to be simple (the pairing model with all degrees equal to d), which is uniform and simple with probability bounded away from 0. For d >= 3 it is whp connected and even d-connected, it is an excellent expander (its second-largest adjacency eigenvalue is close to the Ramanujan bound 2 sqrt(d-1), by Friedman's theorem), it has diameter of order (log n)/(log(d-1)), and its local limit is the infinite d-regular tree — so it is essentially a finite, connected, expanding piece of a regular tree. It has no giant-component transition (it is connected for every fixed d >= 3) and few short cycles. The random geometric graph is governed by its dimension and radius: in dimension D with n points and connection radius r, the average degree is about n times the volume of a ball of radius r, and the connectivity threshold (Penrose) again coincides with the disappearance of isolated points, at r such that n r^D times the ball-volume constant is about log n. Crucially the RGG is highly clustered — two neighbours of a vertex are themselves close and hence likely joined — so unlike Erdos-Renyi it has many triangles and is NOT locally tree-like.

Random regular graphs matter as the canonical sparse expanders — central to coding theory, derandomization, and the theory of rapid mixing of Markov chains — and as the cleanest test of contiguity (different constructions of d-regular graphs are 'contiguous', meaning whp-events coincide). Random geometric graphs matter wherever space is real: wireless ad-hoc and sensor networks, spatial epidemics, and clustering. The honesty to keep: these two models behave very differently from Erdos-Renyi precisely where it matters. The RGG's high clustering and dimension-dependent behaviour mean its connectivity, percolation and spectral properties are governed by geometry, not by the mean-field branching heuristic; and its percolation transition is the continuum percolation problem, with non-explicit, dimension-dependent critical density. The random regular graph, by contrast, has no degree heterogeneity at all, so it is a poor model of real networks even though it is a superb mathematical object.