Scaling limits and generic bounds for exploration processes

DOI10.1007/S10955-017-1902-ZzbMATH Open1387.82008arXiv1612.09347OpenAlexW2568364429MaRDI QIDQ683323FDOQ683323

Authors: Paola Bermolen, Matthieu Jonckheere, Jaron Sanders 

Publication date: 6 February 2018

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: We consider exploration algorithms of the random sequential adsorption type both for homogeneous random graphs and random geometric graphs based on spatial Poisson processes. At each step, a vertex of the graph becomes active and its neighboring nodes become explored. Given an initial number of vertices $N$ growing to infinity, we study statistical properties of the proportion of explored nodes in time using scaling limits. We obtain exact limits for homogeneous graphs and prove an explicit central limit theorem for the final proportion of active nodes, known as the emph{jamming constant}, through a diffusion approximation for the exploration process. We then focus on bounding the trajectories of such exploration processes on random geometric graphs, i.e. random sequential adsorption. As opposed to homogeneous random graphs, these do not allow for a reduction in dimensionality. Instead we build on a fundamental relationship between the number of explored nodes and the discovered volume in the spatial process, and obtain generic bounds: bounds that are independent of the dimension of space and the detailed shape of the volume associated to the discovered node. Lastly, we give two trajectorial interpretations of our bounds by constructing two coupled processes that have the same fluid limits.

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

Recommendations

• The jamming constant of uniform random graphs
• Random Sequential Adsorption on Graphs
• Generalized random sequential adsorption on Erdős-Rényi random graphs
• Random parking, sequential adsorption, and the jamming limit
• Exact and approximate results for deposition and annihilation processes on graphs

zbMATH Keywords

random graphsscaling limitsrandom sequential adsorption

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• Probability and random processes.
• Random Geometric Graphs
• Komlós-Major-Tusnády approximation under dependence
• Title not available (Why is that?)
• An approximation of partial sums of independent RV's, and the sample DF. II
• An approximation of partial sums of independent RV'-s, and the sample DF. I
• Title not available (Why is that?)
• Title not available (Why is that?)
• Connected components in random graphs with given expected degree sequences
• The Average Distance in a Random Graph with Given Expected Degrees
• Random parking, sequential adsorption, and the jamming limit
• Differential equation approximations for Markov chains
• Strong approximation theorems for density dependent Markov chains
• Title not available (Why is that?)
• A Random Graph Model for Power Law Graphs
• Limit theory for random sequential packing and deposition
• The jamming constant of uniform random graphs
• Generalized random sequential adsorption on Erdős-Rényi random graphs
• Scaling limits and generic bounds for exploration processes

Cited In (6)

• The jamming constant of uniform random graphs
• Corrected mean-field model for random sequential adsorption on random geometric graphs
• Large deviations of the greedy independent set algorithm on sparse random graphs
• Scaling limits and generic bounds for exploration processes
• Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
• Generalized random sequential adsorption on Erdős-Rényi random graphs

This page was built for publication: Scaling limits and generic bounds for exploration processes

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