The giant component size conjecture in the Waiter–Client game

Let KnK_n be the complete graph on nn vertices, and let L(n,q)\mathcal L(n,q) denote the largest component size that Waiter can force in Client's graph when playing a (q:1)(q:1) Waiter–Client game on E(Kn)E(K_n). Giant component size conjecture. For any constant ε>0\varepsilon>0 and sufficiently large nn, if q=(1ε)nq=(1-\varepsilon)n, then

L(n,q)=min{n,2(nq1)}.\mathcal L(n,q)=\min\{n,2(n-q-1)\}.

This conjecture concerns the sharp value of the largest component in the supercritical regime. The paper proves a lower bound of 2εn22\varepsilon n-2 for the largest component when q(1ε)nq\leq(1-\varepsilon)n, and the authors believe that the bound in the corresponding theorem is sharp.

Sources & referencesView supporting material

Primary source

Mał gorzata Bednarska-Bzdȩga, Dan Hefetz, Michael Krivelevich and Tomasz Łuczak, “Manipulative waiters with probabilistic intuition”, arXiv:1407.8391 (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.