2-EXPSPACE-completeness conjecture for Ramsey-number avoidance games

Let KnK_n be the complete graph on nn vertices, let Ramsey(n,n)\mathrm{Ramsey}(n,n) be the symmetric binary Ramsey number, and let KRamsey(n,n)K_{\mathrm{Ramsey}(n,n)} be the complete graph on that many vertices. Explicit-Ramsey-number avoidance conjecture. The graph Ramsey avoidance games played on (KRamsey(n,n),Kn,{},{})(K_{\mathrm{Ramsey}(n,n)},K_n,\{\},\{\}) are 22-EXPSPACE{\bf EXPSPACE}-complete. This conjecture is presented as a consequence of the preceding conjectures: computing explicit Ramsey numbers and manipulating graphs of their size suggests doubly exponential space requirements under succinct input representations.

Sources & referencesView supporting material

Primary source

Wolfgang Slany, “Graph Ramsey games”, arXiv:cs/9911004 (1999).

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.