The intrinsic geometry of several probabilistic structures constructed on different underlying discrete systems are believed to be universal. But mathematical results making this rigorous have been proven only very recently. We discuss two such recent results.
(a) The minimal spanning tree (MST) constructed by assigning exchangeable weights to the edges of a random -regular graph: We prove scaling of distance which supports a prediction for the strong disorder regime. We further show that its scaling limit exists and has the same law as the scaling limit of the MST of the complete graph up to a scaling factor of , and in particular, is compact and has Minkowski dimension almost surely.
(b) The vacant set left by a random walk run on a random -regular graph when : We show that around the point of phase transition, the components of the vacant set asymptotically behave like components of the complete graph under critical percolation, i.e., the critical Erdos-Renyi random graph. This answers a question posed by Cerny and Teixeira.
Our approach forms the main technical bedrock for the broader program of developing general universality theorems for such structures. We also discuss related open problems. Based on joint work with Louigi Addario-Berry and Shankar Bhamidi.