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

About 11 years old · traced to

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

r=cnlog⁡log⁡n3.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 (nlog⁡log⁡n)−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.

References

Primary source

Tobias Müller and Reto Spöhel, “A geometric Achlioptas process”, arXiv:1510.07428 (2015).

Progress summary

Never refreshed

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.