The online power-of-choices geometric graph giant-component conjecture

From papers

Consider the online power-of-choices geometric graph process on nn vertices, with radius

r=cnloglogn3.r = \sqrt[3]{\frac{c}{n\log\log n}}.

Here c>0c>0, ff is a function from (0,)(0,\infty) to (0,1)(0,1), and w.h.p. means with high probability. Online giant-component conjecture. There is a function f ⁣:(0,)(0,1)f\colon (0,\infty)\to(0,1) such that, assuming optimal play, the largest component has size

(1+o(1))f(c)n(1+o(1))\,f(c)\,n

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 (nloglogn)1/3(n\log\log n)^{-1/3}; 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

No solutions have been posted yet.