A geometric Achlioptas process

DOI10.1214/14-AAP1074zbMATH Open1326.05143arXiv1510.07428OpenAlexW3099038112MaRDI QIDQ894807FDOQ894807

Authors: Tobias Müller, Reto Spöhel 

Publication date: 24 November 2015

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: The random geometric graph is obtained by sampling $n$ points from the unit square (uniformly at random and independently), and connecting two points whenever their distance is at most $r$, for some given $r=r(n)$. We consider the following variation on the random geometric graph: in each of $n$ rounds in total, a player is offered two random points from the unit square, and has to select exactly one of these two points for inclusion in the evolving geometric graph. We study the problem of avoiding a linear-sized (or "giant") component in this setting. Specifically, we show that for any $rll(nloglogn{)}^{-1/3}$ there is a strategy that succeeds in keeping all component sizes sublinear, with probability tending to one as $noinfty$. We also show that this is tight in the following sense: for any $rgg(nloglogn{)}^{-1/3}$, the player will be forced to create a component of size $(1-o(1))n$, no matter how he plays, again with probability tending to one as $noinfty$. We also prove that the corresponding offline problem exhibits a similar threshold behaviour at $r(n)=Theta(n^{-1/3})$. These findings should be compared to the existing results for the (ordinary) random geometric graph: there a giant component arises with high probability once $r$ is of order $n^{-1/2}$. Thus, our results show, in particular, that in the geometric setting the power of choices can be exploited to a much larger extent than in the classical ErdH{o}s-R'{e}nyi random graph, where the appearance of a giant component can only be delayed by a constant factor.

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

Recommendations

• Memoryless rules for Achlioptas processes
• Avoiding small subgraphs in Achlioptas processes
• Creating a Giant Component
• A phase transition for avoiding a giant component
• Small subgraphs in random graphs and the power of multiple choices

zbMATH Keywords

random geometric graphAchlioptas process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cites Work

• Random Geometric Graphs
• Title not available (Why is that?)
• Two-point concentration in random geometric graphs
• Random Plane Networks
• Avoiding small subgraphs in Achlioptas processes
• Balanced Allocations
• Small subgraphs in random graphs and the power of multiple choices
• Title not available (Why is that?)
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Title not available (Why is that?)
• Hamilton cycles in random geometric graphs
• Explosive percolation in random networks
• The cover time of random geometric graphs
• Avoiding a giant component
• Achlioptas process phase transitions are continuous
• Creating a Giant Component
• Birth control for giants
• Hamiltonicity thresholds in Achlioptas processes
• On the chromatic number of random geometric graphs
• Embracing the giant component
• A phase transition for avoiding a giant component
• Balanced allocations (extended abstract)
• Creating small subgraphs in Achlioptas processes with growing parameter

Cited In (4)

• Geometric Pólya-Aeppli process
• The evolution of subcritical Achlioptas processes
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• Memoryless rules for Achlioptas processes

This page was built for publication: A geometric Achlioptas process

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