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

DOI10.1002/RSA.20880zbMATH Open1445.05096arXiv1608.07153OpenAlexW2963590975MaRDI QIDQ5113952FDOQ5113952

Sanchayan Sen, Shankar Bhamidi

Publication date: 19 June 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (i) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (ii) 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 finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by Cerny and Teixeira by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs.

Full work available at URL: https://arxiv.org/abs/1608.07153

zbMATH Keywords

critical random graphsGromov-Hausdorff distanceconfiguration modelmultiplicative coalescentvacant setsBrownian excursionsgraph enumerationGromov-weak topologycontinuum random treesgraphs with prescribed degree sequenceWright's constants

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability measures on topological spaces (60B05) Random walks on graphs (05C81) Processes in random environments (60K37)

Cited In (13)

• Universality for critical heavy-tailed network models: metric structure of maximal components
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• Convergence of blanket times for sequences of random walks on critical random graphs
• A probabilistic approach to the leader problem in random graphs
• Multisource invasion percolation on the complete graph
• Geometry of the minimal spanning tree of a random 3-regular graph
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• On breadth‐first constructions of scaling limits of random graphs and random unicellular maps
• Epidemics on critical random graphs with heavy-tailed degree distribution
• Stable graphs: distributions and line-breaking construction
• Title not available (Why is that?)
• Universal height and width bounds for random trees
• Scaling Limits of Random Trees and Random Graphs

This page was built for publication: Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113952)