A geometric Achlioptas process

DOI10.1214/14-AAP1074MaRDI QIDQ894807zbMATHOpenAlexFDO

Authors Tobias Müller, Reto Spöhel

Publication date 24 November 2015

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

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

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)

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.

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

Cites work

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

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)