Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Scaling Limits and Generic Bounds for Exploration Processes
KTH, School of Electrical Engineering (EES), Automatic Control.
2017 (English)In: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 169, no 5, p. 989-1018Article in journal (Refereed) Published
Abstract [en]

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 blocked. Given an initial number of vertices N growing to infinity, we study statistical properties of the proportion of explored (active or blocked) 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 jamming constant, through a diffusion approximation for the exploration process which can be described as a unidimensional process. We then focus on bounding the trajectories of such exploration processes on random geometric graphs, i.e., random sequential adsorption. As opposed to exploration processes on homogeneous random graphs, these do not allow for such a dimensional reduction. Instead we derive a fundamental relationship between the number of explored nodes and the discovered volume in the spatial process, and we obtain generic bounds for the fluid limit and jamming constant: bounds that are independent of the dimension of space and the detailed shape of the volume associated to the discovered node. Lastly, using coupling techinques, we give trajectorial interpretations of the generic bounds.

Place, publisher, year, edition, pages
SPRINGER , 2017. Vol. 169, no 5, p. 989-1018
Keywords [en]
Random sequential adsorption, Scaling limits, Random graphs
Identifiers
URN: urn:nbn:se:kth:diva-217927DOI: 10.1007/s10955-017-1902-zISI: 000414378000007Scopus ID: 2-s2.0-85032492754OAI: oai:DiVA.org:kth-217927DiVA, id: diva2:1158882
Note

QC 20171121

Available from: 2017-11-21 Created: 2017-11-21 Last updated: 2017-11-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Sanders, Jaron
By organisation
Automatic Control
In the same journal
Journal of statistical physics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 6 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf