Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees

Shankar Bhamidi, Sanchayan Sen

Published 2016-08-25Version 1

We provide an explicit algorithm for sampling a connected uniform random graph with given degree sequence by first sampling a plane tree with a modified degree sequence according to an appropriately defined measure on the space of plane trees with this modified degree sequence. A careful analysis of this algorithm allows us to derive continuum scaling limits for uniform simple connected graphs with given degree sequence under some regularity conditions. By products of this central result include: (a) asymptotics for the number of connected simple graphs with prescribed degree sequence and fixed complexity; (b) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under optimal assumptions on the degree sequence. As a substantive application we consider the fractal properties of maximal components in the vacant set left by random walks (VSRW), a question that has witnessed substantial interest in the probability community; see, e.g., [21-23, 27, 52, 53]. We answer a question raised by Cerny and Teixeira [21] by obtaining the metric space scaling limit of maximal components in the VSRW on random regular graphs. Assuming one is able to: (a) establish the existence of the critical point for emergence of a giant component for VSRW on random graphs with general prescribed degree sequence, and (b) establish regularity conditions of the degree sequence of the VSRW in the critical regime analogous to those established in [21] for random regular graphs, the results in this paper would imply universality for the metric space structure of maximal components in VSRW on random graphs with a general given degree sequence under appropriate moment conditions on the degree sequence.