Generalized random sequential adsorption on Erdős-Rényi random graphs

DOI10.1007/S10955-016-1583-ZMaRDI QIDQ504210zbMATH OpenOpenAlexWikidataFDO

Authors Souvik Dhara, Johan S. H. van Leeuwaarden, Debankur Mukherjee

Publication date 25 January 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

random graphsfrequency assignmentparking problemgreedy independent setjamming limitrandom sequential adsoption

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Interacting particle systems in time-dependent statistical mechanics (82C22)

Abstract: We investigate Random Sequential Adsorption (RSA) on a random graph via the following greedy algorithm: Order the $n$ vertices at random, and sequentially declare each vertex either active or frozen, depending on some local rule in terms of the state of the neighboring vertices. The classical RSA rule declares a vertex active if none of its neighbors is, in which case the set of active nodes forms an independent set of the graph. We generalize this nearest-neighbor blocking rule in three ways and apply it to the ErdH{o}s-R'enyi random graph. We consider these generalizations in the large-graph limit $noinfty$ and characterize the jamming constant, the limiting proportion of active vertices in the maximal greedy set.

Recommendations

• Random Sequential Adsorption on Graphs
• Degree-dependent threshold-based random sequential adsorption on random trees
• Scaling limits and generic bounds for exploration processes
• The greedy independent set in a random graph with given degrees
• The expected duration of random sequential adsorption

Cites work

• scientific article; zbMATH DE number 3171475 (Why is no real title available?)
• scientific article; zbMATH DE number 4101221 (Why is no real title available?)
• A second-row parking paradox
• Multilayer parking with screening on a random tree
• On the independence number of random graphs
• On the scalability and message count of trickle-based broadcasting schemes
• On-Line Coloring of Sparse Random Graphs and Random Trees
• Parking on a random tree
• Random parking, sequential adsorption, and the jamming limit
• Random sequential adsorption on random trees
• Scaling limits and generic bounds for exploration processes
• The greedy independent set in a random graph with given degrees
• The jamming constant of uniform random graphs

Cited in

(5)

• Corrected mean-field model for random sequential adsorption on random geometric graphs
• Random Sequential Adsorption on Graphs
• Scaling limits and generic bounds for exploration processes
• Greedy maximal independent sets via local limits
• Degree-dependent threshold-based random sequential adsorption on random trees

This page was built for publication: Generalized random sequential adsorption on Erdős-Rényi random graphs

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