Scaling limits and generic bounds for exploration processes

DOI10.1007/S10955-017-1902-ZMaRDI QIDQ683323zbMATH OpenOpenAlexFDO

Authors Paola Bermolen, Matthieu Jonckheere, Jaron Sanders

Publication date 6 February 2018

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

Full work available at URL https://arxiv.org/abs/1612.09347, http://hdl.handle.net/11336/55573

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)

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.

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

Cites work

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

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)