The online power-of-choices geometric graph giant-component conjecture
The online power-of-choices geometric graph giant-component conjecture
Consider the online power-of-choices geometric graph process on vertices, with radius
Here , is a function from to , and w.h.p. means with high probability. Online giant-component conjecture. There is a function such that, assuming optimal play, the largest component has size
with high probability. This conjecture proposes a limiting giant-component fraction for the online process at the critical scale where the radius is of order ; the paper establishes delay of the giant to this scale but does not determine the limiting fraction.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Tobias Müller and Reto Spöhel, “A geometric Achlioptas process”, arXiv:1510.07428 (2015).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.