Beck's bounded-move conjecture for strong Ramsey games

Let KnK_n be the complete graph on nn vertices, and let KtK_t be the complete graph on tt vertices. The function L(Kn,Kt)L(K_n,K_t) denotes the minimum number of moves required for player P1P_1 to establish a copy of KtK_t in the strong Ramsey game on KnK_n, regardless of P2P_2's play.

Beck's conjecture. For sufficiently large nn and every integer t3t\geq 3, there is a constant ctc_t, depending only on tt, such that

L(Kn,Kt)ct.L(K_n,K_t)\leq c_t.

This conjecture asks whether player P1P_1 can always win in a number of moves bounded independently of the board size. Beck identified it as a major open problem, even for t=5t=5.

Sources & referencesView supporting material

Primary source

Jiangdong Ai, Jun Gao, Zixiang Xu and Xin Yan, “Strong Ramsey game on two boards”, arXiv:2501.06830 (2025).

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.