Scaling Limits and Generic Bounds for Exploration Processes

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 verti...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bermolen, P., Jonckheere, M., Sanders, J.
Formato:	JOUR
Materias:	Random graphs Random sequential adsorption Scaling limits
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_00224715_v169_n5_p989_Bermolen
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_00224715_v169_n5_p989_Bermolen
record_format	dspace
spelling	todo:paper_00224715_v169_n5_p989_Bermolen2023-10-03T14:32:58Z Scaling Limits and Generic Bounds for Exploration Processes Bermolen, P. Jonckheere, M. Sanders, J. Random graphs Random sequential adsorption Scaling limits 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. © 2017, Springer Science+Business Media, LLC. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_00224715_v169_n5_p989_Bermolen
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Random graphs Random sequential adsorption Scaling limits
spellingShingle	Random graphs Random sequential adsorption Scaling limits Bermolen, P. Jonckheere, M. Sanders, J. Scaling Limits and Generic Bounds for Exploration Processes
topic_facet	Random graphs Random sequential adsorption Scaling limits
description	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. © 2017, Springer Science+Business Media, LLC.
format	JOUR
author	Bermolen, P. Jonckheere, M. Sanders, J.
author_facet	Bermolen, P. Jonckheere, M. Sanders, J.
author_sort	Bermolen, P.
title	Scaling Limits and Generic Bounds for Exploration Processes
title_short	Scaling Limits and Generic Bounds for Exploration Processes
title_full	Scaling Limits and Generic Bounds for Exploration Processes
title_fullStr	Scaling Limits and Generic Bounds for Exploration Processes
title_full_unstemmed	Scaling Limits and Generic Bounds for Exploration Processes
title_sort	scaling limits and generic bounds for exploration processes
url	http://hdl.handle.net/20.500.12110/paper_00224715_v169_n5_p989_Bermolen
work_keys_str_mv	AT bermolenp scalinglimitsandgenericboundsforexplorationprocesses AT jonckheerem scalinglimitsandgenericboundsforexplorationprocesses AT sandersj scalinglimitsandgenericboundsforexplorationprocesses
_version_	1782030277092048896

Scaling Limits and Generic Bounds for Exploration Processes

Ejemplares similares