The giant component size conjecture in the Waiter–Client game
The giant component size conjecture in the Waiter–Client game
Let be the complete graph on vertices, and let denote the largest component size that Waiter can force in Client's graph when playing a Waiter–Client game on . Giant component size conjecture. For any constant and sufficiently large , if , then
This conjecture concerns the sharp value of the largest component in the supercritical regime. The paper proves a lower bound of for the largest component when , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.