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.
References
Primary source
Tobias Müller and Reto Spöhel, “A geometric Achlioptas process”, arXiv:1510.07428 (2015).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.