Strong Ramsey game on two boards Jiangdong Ai, Jun Gao, Zixiang Xu, Xin Yan Abstract The strong Ramsey game R ⁡ ( ℬ , H ) R(\mathcal{B},H) is a two-player game played on a graph ℬ \mathcal{B} , referred to as the board, with a target graph H H . In this game, two players, P 1 P_{1} and P 2 P_{2} , alternately claim unclaimed edges of ℬ \mathcal{B} , starting with P 1 P_{1} . The goal is to claim a subgraph isomorphic to H H , with the first player achieving this declared the winner. A fundamental open question, persisting for over three decades, asks whether there exists a graph H H such that in the game R ⁡ ( K n , H ) R(K_{n},H) , P 1 P_{1} does not have a winning strategy in a bounded number of moves as n → ∞ n\to\infty . In this paper, we shift the focus to the variant R ⁡ ( K n ⊔ K n , H ) R(K_{n}\sqcup K_{n},H) , introduced by David, Hartarsky, and Tiba, where the board K n ⊔ K n K_{n}\sqcup K_{n} consists of two disjoint copies of K n K_{n} . We prove that there exist infinitely many graphs H H such that P 1 P_{1} cannot win in R ⁡ ( K n ⊔ K n , H ) R(K_{n}\sqcup K_{n},H) within a bounded number of moves through a concise proof. This perhaps provides evidence for the existence of examples of the longstanding open problem mentioned above. 1 Introduction The study of positional games began with the pioneering work of Hales and Jewett [ 13 ] , followed by notable contributions from Erdős and Selfridge [ 10 ] . Beck’s prolific research [ 1 , 2 , 3 , 4 , 5 ] , starting in the early 1980s, significantly defined and expanded this topic. Among the many variants [ 7 , 8 , 11 , 12 , 14 , 17 ] , strong positional games stand out as the most intuitive and natural. The strong Ramsey game R(\mathcal{B},H) is played on a finite or infinite graph \mathcal{B} , called the board, with target graph H . Two players P_{1} and P_{2} , take turns selecting unclaimed edges of \mathcal{B} , with P_{1} making the initial move. The first player to successfully establish an isomorphic copy of H wins and if neither player achieves this within a finite time, the game is declared a draw. In the context of fixed graphs, a general strategy-stealing argument establishes that P_{2} cannot have a winning strategy. Moreover, the classical Ramsey theorem [ 18 ] states that for any given graph H , there exists a natural number n_{0}(H) such that for any integer n\geq n_{0}(H) , any edge-colored clique K_{n} with two colors contains a monochromatic copy of H . Consequently, P_{1} is guaranteed to have a winning strategy for sufficiently large n . However, the strategy derived from this argument is non-explicit, and very few explicit strategies are known. While it is known that as n becomes sufficiently large, P_{1} is assured of having a winning strategy, a pertinent query arises: Can P_{1} ensure victory within a fixed number of moves, denoted by c_{H} , which solely relies on the target graph H ? To formally address this, we introduce the extremal function L(\mathcal{B},H) , which represents the minimum number of moves required for P_{1} to secure victory, regardless of P_{2} ’s level of intelligence. Question 1.1 . For given graph H and \mathcal{B} , determine the extremal function L(\mathcal{B},H) as n\rightarrow\infty . By the definition of the Turán number of graph H , it follows that for any given graph H , we have L(K_{n},H)\leq\textup{ex}(n,H) , where \textup{ex}(n,H) is the maximum number of edges in an n -vertex H -free graph. A major conjecture in this area, proposed by Beck [ 4 ] , is stated as follows. Remarkably, Beck includes this problem among his “7 most humiliating open problems” and deems even the case t=5 to be seemingly intractable. Conjecture 1.2 . Let n be a sufficiently large number, for any t\geq 3 , L(K_{n},K_{t})\leq c_{t}, (1) where c_{t} is a constant which depends only on t . It was proven in [ 4 ] that the above conjecture holds for t=3,4 . 1 1 1 For t=4 , Bowler and Gut showed that the proof was inaccurate and fixed it [ 6 ] . However, surprisingly when t\geq 5 , the best known upper bound is (1-\frac{1}{t-1}+o(1))\binom{n}{2} , which is trivial by the so-called Turán Theorem [ 19 ] . Hefetz, Kusch, Narins, Pokrovskiy, Requilě, and Sarid [ 15 ] explored a natural generalization from graphs to hypergraphs, completely altering the intuition about this phenomenon. Specifically, they proved the existence of a 5 -uniform hypergraph \mathcal{H} such that, in the game R(K_{n}^{(5)},\mathcal{H}) , P_{1} cannot secure a win within a bounded number of moves. Subsequently, in [ 9 ] , David, Hartarsky, and Tiba investigated another intriguing generalization where the board consists of two vertex-disjoint copies of K_{n} . They demonstrated that when H=K_{6}\setminus K_{4} , P_{1} cannot win the game R(K_{n}\sqcup K_{n},H) within a bounded number of moves. For given graphs H and \mathcal{B} , to prove that C is an upper bound for L(\mathcal{B},H) , we must show that, regardless of how strategically P_{2} plays, P_{1} can always secure a win within C moves. Conversely, to establish that D is a lower bound for L(\mathcal{B},H) , we need to demonstrate that, no matter what strategy P_{1} adopts, P_{2} can always ensure the game lasts at least D moves by avoiding defeat within the first D-1 moves. Moreover, one can see for any fixed graph H , if P_{1} can win the game R(K_{n}\sqcup K_{n},H) within a bounded number of moves, then P_{1} can also win the game R(K_{n},H) . The main result of this paper is to provide infinitely many examples H such that P_{1} cannot win the game R(K_{n}\sqcup K_{n},H) within a bounded number of moves. More precisely, for integers t\geq 2 and s\geq 0 , let K_{2,t}(s) be the complete bipartite graph plus s edge which is incident to some vertex in the smaller part, that is, V(K_{2,t}(s)):=\{a_{1},a_{2},b_{1},b_{2},\ldots,b_{t},c_{1},\dots,c_{s}\} , a_{i}b_{j}\in E(K_{2,t}(s)) for any i\in\{1,2\} and j\in\{1,2,\ldots,t\} , and a_{1}c_{i}\in E(K_{2,t}(s)) for any i\in[s] . Theorem 1.3 . For any t\geq 3 and constant C , there exists some constant n_{0} such that for any n\geq n_{0} , we have L(K_{n}\sqcup K_{n},K_{2,t+1}(t-2))>C. In particular, the condition t\geq 3 is optimal. By definition, when t=2 , K_{2,t+1}(t-2) is exactly the complete bipartite graph K_{2,3} . We can show that P_{1} can easily win the game R(K_{n}\sqcup K_{n},H) when H is K_{2,3} . Moreover, we can also show that P_{1} can win the game R(K_{n},C_{\ell}) , where C_{\ell} is the cycle of length \ell\geq 3 . Theorem 1.4 . Let n be a large enough number, then P_{1} can win the following games using a constant number of moves. 1. R(K_{n}\sqcup K_{n},K_{2,3}) ; 2. R(K_{n},C_{\ell}) for any \ell\geq 3 . The main advantage is, our proofs are concise and straightforward, without relying on computer-assisted exhaustive searches. For convenience, we will use K_{\infty} to denote the complete graph K_{n} when n is sufficiently large. 2 P_{1} cannot win in R(K_{\infty}\sqcup K_{\infty},K_{2,t+1}(t-2)) Let \mathcal{B}_{1}\cong K_{\infty} , and \mathcal{B}_{2}\cong K_{\infty} be two disjoint boards. Without loss of generality, we can assume P_{1} claims the first edge in \mathcal{B}_{1} . For a given positive integer i , let G_{i}^{(1)} and G_{i}^{(2)} be the graphs in \mathcal{B}_{1} and \mathcal{B}_{2} that P_{1} claimed after round i , respectively, and let F_{i}^{(1)} and F_{i}^{(2)} be the graphs in \mathcal{B}_{1} and \mathcal{B}_{2} that P_{2} claimed after round i , respectively. In order to show the lower bound on L(K_{\infty}\sqcup K_{\infty},K_{2,t+1}(t-2)) , we next propose a strategy for P_{2} and show that, if P_{2} strictly obeys this strategy, then P_{2} can successfully prevent P_{1} from winning the game within C moves for any constant C . Note that e(K_{2,t+1}(t-2))=3t . Let \mathcal{F} be the family consisting of all graphs obtained from K_{2,t+1}(t-2) by removing t-1 edges. x y z_{1} z_{2} z_{3} z_{4} (a) H_{1} x y z_{1} z_{2} z_{3} z_{4} z_{5} (b) H_{2} x y z_{1} z_{2} z_{3} z_{4} z_{5} (c) H_{3} Figure 2.1 : For t=3 , all possible graphs obtained from K_{2,4}(1) by removing 2 edges (under isomorphism) . Given a graph G , we say a vertex u is a core of G if d_{G}(u)\geq 3 . We say a vertex is unused if, at that moment, there is no edge already being claimed on the board that is incident to this vertex. The term check refers to a situation where a player will win in the next move if the opponent gives up the next move. We say the player P is in check where the opponent will win the game if P gives up the next move. u v x_{1} x_{2} x_{3} x_{4} x_{5} Figure 2.2 : The graph K_{2,3}(2) : key of P_{2} for t=3 Strategy 1 (Strategy for P_{2} ) . Suppose that the game is not finished after P_{1} ’s i -th move, P_{2} ’s i -th move should obey the following rules. Also note that these strategies have different priorities, and P_{2} will only execute the next strategy if the previous one does not occur. Case 1. If P_{2} has a chance to win the game after the i -th move, then P_{2} claims that edge and wins the game. Case 2. If Case 1 does not occur, and G^{(1)}_{2t+1}\cong F for some F\in\mathcal{F} . Recall that F can be obtained from K_{2,t+1}(t-2) by removing t-1 edges. Let x,y be the core of the original K_{2,t+1}(t-2) , A be the common neighbor of x,y in F , and let B be the set of the vertices that are adjacent to exactly one of x,y in F . Clearly, we have e(F)=2|A|+|B|=2t+1 , which implies that |B| is odd. Let |A|=a,|B|=2b-1 , where b\geq 1 . Since 2t-1\geq|A|+|B|=2t+1-|A| , we have a\geq 2 . 1. In round 2t+1 , P_{2} picks an arbitrary vertex w\in B and claims the unused edge xw or yw . Then we set B=B\setminus\{w\} . 2. Suppose that in some following rounds, P_{1} claims the edge xw or yw for some unused vertex w , then P_{2} claims yw or xw , respectively. 3. Suppose that in some following rounds, P_{1} claims the edge xw or yw for some vertex w\in B , then P_{2} picks another vertex w^{\prime}\in B and claims the unused edge xw or yw . Then we set B=B\setminus\{w,w^{\prime}\} . Case 3. If neither Case 1 nor Case 2 occurs, then P_{2} should try to build a copy of K_{2,t}(t-1) , which is shown in Figure 2.2 for t=3 , in \mathcal{B}_{2} . More precisely, to build the graph K_{2,t}(t-1) , P_{2} should obey the following order if, during this process, none of the preceding cases occur. 1. P_{2} first claims an arbitrary edge ux_{1} , where u and x_{1} are not incident to any claimed edge. Then P_{2} can repeatedly pick 2t-2 more unused vertices, say x_{2},x_{3},\dots,x_{2t-1} and claim ux_{2},ux_{3},\dots,ux_{2t-1} in this order. 2. P_{2} next picks an unused vertex, say v , and then claims t of the 2t-1 edges vx_{1} , vx_{2} , \ldots,vx_{2t-1} with a preference for edges vx_{j} according to the following rules: if at that moment P_{1} claims a star then we give priority to vertex x_{j} with degree one in the graph claimed by P_{1} in \mathcal{B}_{2} , otherwise we prioritize vertex x_{j} with the highest degree in the graph claimed by P_{1} in \mathcal{B}_{2} . Case 4. If P_{2} has claimed a copy of K_{2,t}(t-1) in \mathcal{B}_{2} with vertex set \{u,v,x_{1},x_{2},\dots,x_{2t-1}\} , and none of the events in Case 1 and Case 2 occurs, then P_{2} picks an unused vertex w . If P_{1} does not have a K_{2,t} with u as a core, then P_{2} claims the edge vw , otherwise P_{2} claims uw . Next, we would like to show that, if P_{2} strictly obeys the above strategy, then P_{2} can guarantee that P_{1} cannot win the game within a finite number of moves. We need a series of claims as follows. Claim 2.1 . If P_{2} wants to claim a copy of graph K_{2,t}(t-1) in \mathcal{B}_{2} , P_{2} can always achieve it after 3t-1 moves, provided that during the process none of Case 1 and Case 2 occur. Proof of claim. By the embedding rules listed in Case 3 above, P_{2} can always find a copy of K_{1,2t-1} with edges ux_{1},ux_{2},\dots,ux_{2t-1} , and as v is an unused vertex, by the pigeonhole principle, P_{2} can guarantee to claim t of edges vx_{1},vx_{2},\dots,vx_{2t-1} . ∎ Let \Delta(i)=e(G_{i}^{(1)})-e(F_{i}^{(1)}) . Note that if P_{1} wins in round i , then \Delta(i) does not exist. Claim 2.2 . If P_{1} finally claims a copy of K_{2,t+1}(t-2) in \mathcal{B}_{1} , then there must be some i such that \Delta(i)=3t . Proof of claim. If G^{(1)}_{2t+1}\cong F for some F\in\mathcal{F} , then P_{2} should start to defend in round 2t+1 , which implies \Delta(2t+1)=2t . Recalling the definition of the graph F , we know that a+b=t+1 . So if P_{2} obeys the strategy, then P_{1} cannot claim a copy of K_{2,t+1}(t-2) with core vertices x,y within a finite number of moves. That means, if P_{1} finally claims a copy of K_{2,t+1}(t-2) in \mathcal{B}_{1} , then P_{1} should find another pair of core vertices x^{\prime},y^{\prime} , where |\{x,y\}\cap\{x^{\prime},y^{\prime}\}|\leq 1 . If |\{x,y\}\cap\{x^{\prime},y^{\prime}\}|=1 , consider the codegree of the core vertices x^{\prime},y^{\prime} , P_{1} needs to claim at least t+1 more edges in \mathcal{B}_{1} which are not equal to xw or yw for some w\notin\{x,y\} . If |\{x,y\}\cap\{x^{\prime},y^{\prime}\}|=0 , consider the degree of the core vertices x^{\prime},y^{\prime} , P_{1} needs to claim at least 3t-4 more edges in \mathcal{B}_{1} which are not equal to xw or yw for some w\notin\{x,y\} . Since t\geq 3 , we have 3t-4\geq t+1 . Based on P_{2} ’s strategy, there must be some integer i such that \Delta(i)\geq 2t+t=3t . If G^{(1)}_{2t+1}\ncong F for any F\in\mathcal{F} , we have G^{(1)}_{3t} does not contain K_{2,t+1}(t-2) . Note that P_{2} does not claim any edges in \mathcal{B}_{1} , thus \Delta(3t)=3t . ∎ Claim 2.3 . P_{1} can not claim a copy of K_{2,t+1}(t-2) in \mathcal{B}_{1} . Proof of claim. Suppose on the contrary that P_{1} finally claims a copy of K_{2,t+1}(t-2) in \mathcal{B}_{1} . By Claim 2.2 , there exists some i such that e(F_{i}^{(2)})=3t-1 . By P_{2} ’s strategy, F_{i}^{(2)}\cong K_{2,t}(t-1) , without loss of generality, we further assume that E(F_{i}^{(2)})=\{ux_{s},vx_{k},s\in[2t-1],k\in[t]\} . Note that e(G^{(2)}_{i})\leq e(F_{i}^{(2)})-1=3t-2 , and \Delta(j)\leq 3t-1 for all j\leq i . By Claim 2.2 , P_{1} can not win in round i+1 . This means that G^{(2)}_{i+1} must contain vx_{j} for all j\in[2t-1]\setminus[t] , otherwise P_{2} will win in round i+1 . This implies that \Delta(i+1)\leq(3t-1)-(t-1)+1=2t+1. By Claim 2.2 , there exists some m such that \Delta(m)=3t . This means there exists a rounds m^{\prime} after round i such that P_{2} claims an edge in \mathcal{B}_{2} and P_{1} claims an edge in \mathcal{B}_{1} in round m^{\prime}+1 such that the game is not over, which implies that P_{2} claimed a copy of K_{2,t+1}(t-2) in round m^{\prime}+1 , a contradiction. ∎ Claim 2.4 . P_{1} can not claim a copy of K_{2,t+1}(t-2) in \mathcal{B}_{2} . Proof of claim. Suppose on the contrary that P_{1} finally claims a copy of K_{2,t+1}(t-2) in \mathcal{B}_{2} . According to the P_{2} ’s strategy, we have e(G_{i}^{(2)})\leq e(F_{i}^{(2)})-1 , which implies that e(G_{i+1}^{(2)})\leq e(F_{i}^{(2)}) . Therefore, there exists some i such that e(F_{i}^{(2)})=3t-1 and F_{i}^{(2)}\cong K_{2,t}(t-1) . Similarly, we assume that E(F_{i}^{(2)})=\{ux_{s},vx_{k},s\in[2t-1],k\in[t]\} and G^{(2)}_{i+1} must contain vx_{s} for all s\in[2t-1]\setminus[t] . Since e(K_{2,t+1}(t-2))=3t , there also exists some j such that e(F_{j}^{(2)})=3t . We claim that P_{2} can not be in check in round j . Suppose that P_{2} is in check in round j , then G^{(2)}_{j} is isomorphic to the graph obtained by deleting an edge from K_{2,t+1}(t-2) . Note that, e(G_{j}^{(2)})=3t-1 and v has degree t-1 or t in G_{j}^{(2)} . If v is a core of G^{(2)}_{j} , then G^{(2)}_{j}\cong K_{2,t}(t-1) as d(v)\leq t . Let u^{\prime} be another core of G^{(2)}_{j} . Since the vertex v remains unused until P_{2} picks it, we conclude that the first 2t-1 moves of P_{1} on \mathcal{B}_{2} form a star centered at u^{\prime} . Since P_{2} claims t of the 2t-1 edges vx_{1},vx_{2},\dots,vx_{2t-1} with a preference for edges vx_{j} , where x_{j} has degree one in the graph claimed by P_{1} in \mathcal{B}_{2} , t-1 of the edges u^{\prime}x_{1},u^{\prime}x_{2},\dots u^{\prime}x_{t} will belong to G_{j+1}^{(2)} . Since the edges vx_{1},vx_{2},\dots vx_{t} have been claimed by P_{2} , we derive that P_{2} is not in check in round j . If v is not a core of G^{(2)}_{j} , then the degree of v in G^{(2)}_{j} is 2 and t=3 , which implies that x_{4} and x_{5} are the two cores of G^{(2)}_{j} . Since at the moment P_{2} picks v , P_{1} does not claim a star in \mathcal{B}_{2} , by the strategy of P_{2} for claiming the 3 edges from vx_{1},vx_{2},\dots,vx_{5} , one of vx_{4} and vx_{5} will be claimed by P_{2} , which leads to a contradiction. Since e(G^{(2)}_{j})\leq 3t-1 and u,v do not belong to the same K_{2,t} in G^{(2)}_{j} , we deduce that at least one of the vertices u or v does not belong to any K_{2,t} in G^{(2)}_{j} . Without loss of generality, assume that v does not belong to any K_{2,t} in G^{(2)}_{j} . in round j+1 , P_{2} claims the edge uw for some unused vertex w . Since P_{2} is not in check and P_{1} is in check, P_{1} must respond by claiming vw in the next round. In each subsequent round, P_{2} will continue to claim an edge uw^{\prime} for some unused vertex w^{\prime} , forcing P_{1} to claim vw^{\prime} in response. This process ensures that P_{1} cannot claim a copy of K_{2,t+1}(t-2) , leading to a contradiction. ∎ By Claim 2.3 and Claim 2.4 , we can see that P_{1} cannot win within a finite number of moves. This finishes the proof. 3 P_{1} always wins for various games: Proof of Theorem 1.4 In this section, we prove the results in Theorem 1.4 separately. 3.1 The game R(K_{n},C_{\ell}) We first demonstrate that P_{1} can claim a path of length \ell-2 in such a way that P_{2} is unable to form a path of length \ell-2 with the same endpoints after \ell-2 moves. To see this, after \ell-3 moves, P_{1} can claim a path of length \ell-3 , denoted by v_{0}v_{1}\cdots v_{\ell-3} . If P_{2} does not claim a path of length \ell-3 after \ell-3 moves, then P_{1} can pick a new vertex v , which is not adjacent to any edge claimed by P_{2} . Regardless of P_{2} ’s moves on the (\ell-2) -th round, P_{1} can claim a path v_{0}v_{1}\cdots v_{\ell-3}v , but P_{2} cannot claim a path of length \ell-2 with endpoints v_{0} and v . Otherwise, suppose that P_{2} claims a path of length \ell-3 with endpoints \{x,y\} after \ell-3 moves, if \{x,y\}\neq\{v_{0},v_{\ell-3}\} , we can assume v_{0}\notin\{x,y\} , then P_{1} can pick a new vertex v which does not appear in any claimed edges and then claim v_{\ell-3}v , otherwise suppose that \{x,y\}=\{v_{0},v_{\ell-3}\} , then P_{1} can do the same operation. Observe that in both of the above cases, P_{2} has no way to obtain a path of length \ell-2 with the same endpoints \{v_{0},v\} . Therefore, P_{1} can first claim a path of length \ell-2 , denoted by v_{0}v_{1}\cdots v_{\ell-2} after \ell-2 moves, so that P_{2} cannot claim a path of length \ell-2 with the same endpoints \{v_{0},v_{\ell-2}\} . Without loss of generality, we can assume that P_{2} does not claim any path of length \ell-2 with v_{\ell-2} being one endpoint. P_{1} can pick a new vertex x which does not appear in any claimed edges and then claim v_{0}x in his (\ell-1) -th round, and P_{2} has to claim v_{\ell-2}x . Furthermore, P_{1} can pick another new vertex y which does not appear in any claimed edges and then claim v_{0}y in his \ell -th round, and P_{2} has to claim v_{\ell-2}y . As P_{2} does not claim a path of length \ell-2 with v_{\ell-2} being one endpoint after \ell-2 moves, we can see P_{2} does not claim any path of length \ell-1 after claiming v_{\ell-2}x and v_{\ell-2}y . Finally, P_{1} can pick a new vertex z which does not appear in any claimed edges and then claim v_{\ell-3}z in his (\ell+1) -th round, and P_{2} has to claim both of xz and yz , which is impossible. That means P_{1} can win the game using \ell+2 moves. 3.2 The game R(K_{n}\sqcup K_{n},K_{2,3} ) For a given positive integer i , let e_{i}^{(1)} (resp. e_{i}^{(2)} ) denote the edge claimed by P_{1} (resp. P_{2} ) on the i -th move. Player P_{1} ’s initial objective is to claim a 4-cycle with favorable properties. As demonstrated in the following propositions, if P_{1} succeeds in achieving this, they can secure a swift victory. This strategy serves as the foundation for P_{1} ’s overall approach to the game. Claim 3.1 . Assume we are now in the i -th step where i\in\mathbb{N} , P_{1} can win the game using at most 6 more moves if the following holds. P_{1} has claimed a copy of C_{4}:=abcd such that (1) There is some edge xy\in\{ab,bc,cd,ad\} such that P_{2} has not claimed a path of length 2 between x and y . (2) Furthermore, neither x nor y is contained in any copy of C_{4} claimed by P_{2} . (3) P_{1} is not in check. Proof of claim. Without loss of generality, we assume that xy=ab . From rounds i+1 to i+3 , P_{1} could claim cy_{i} for i=[3] consecutively, for three unused vertices y_{i} . By property (3), P_{2} must claim ay_{i} for i=[3] to prevent P_{1} from claiming a K_{2,3} . From rounds i+4 to i+5 , P_{1} claims dy_{i} for i=[2] consecutively. In response, P_{2} must claim by_{i} for i=[2] to prevent P_{1} from claiming a copy of K_{2,3} . However, in round i+6 , P_{1} can claim a copy of K_{2,3} , namely \{cy_{1},cy_{2},cy_{3},dy_{1},dy_{2},dy_{3}\} . Note that in this process, all of the vertices y_{i} are new, which yields that after the (i+4) -th move, e^{(2)}{(j)} cannot be contained in any copy of K_{2,2}(1) claimed by P_{2} for i+1\leq j\leq i+4 . As a result, to claim a copy of K_{2,3} , P_{2} needs to claim at least 2 more edges. Therefore, P_{2} can not prevent P_{i} ’s victory in round i+6 . ∎ Claim 3.2 . Assume we are now in the i -th step where i\in\mathbb{N} , P_{1} can win the game using at most 5 more moves if the following holds: P_{1} has claimed a copy of K_{2,2}(1) which consists of a C_{4}:=axby, and an edge ac such that (1) Neither x nor y is contained in any copy of C_{4} claimed by P_{2} . (2) P_{1} is not in check. Moreover, if P_{2} is C_{4} -free, then conditions (1) and (2) naturally hold. Proof. Without loss of generality, we assume that x is not contained in any copy of C_{4} claimed by P_{2} . Form rounds i+1 to i+3 , P_{1} could claim yz_{i} for i\in[3] consecutively, for three unused vertices z_{i} . Since P_{1} is not in check and x is not contained in any copy of C_{4} , we know that P_{2} must claim xz_{i} for \in[3] . In round i+4 P_{1} claims cz_{1} . Clearly, P_{1} is still not in check, so P_{1} will get a K_{2,3} with c,y as the core in the next round by claiming one of cz_{2},cz_{3} . ∎ a b c d y_{1} y_{2} y_{3} (a) The graph for Claim 3.1 a b x y c z_{1} z_{2} z_{3} (b) The graph for Claim 3.2 Based on Claim 3.1 and Claim 3.2 , we then describe the early strategy of P_{1} as following picture. P_{1} first picks an arbitrary edge, then P_{1} checks whether e^{(2)}(1) and e^{(1)}(1) share a common vertex. Note that in some cases, certain choices are isomorphic. We list only one representative in such cases. For example, in the second round of choices for P_{2} in the first case, if cx_{1} is selected, choosing cx_{2} , y_{1}x_{1} or y_{1}x_{2} would result in isomorphic graphs. ax_{1} ax_{2} ax_{2} x_{2}y_{1} x_{1}y_{1} ax_{3} :(1) bx_{1} ax_{3} :(2) bx_{2} x_{1}y_{1} :(3) x_{1}c x_{2}y_{1} :(4) cx_{1} ax_{3} :(5) bx_{2} :(6) bd bx_{1} :(7) cd cx_{2} :(8) ad cx_{2} :(9) dy_{1} :(10) ad :(11) ad :(12) dy_{1} :(13) cd :(14) bd :(15) cy_{1} ay_{1} cx_{1} x_{1}x_{2} o.w. y_{1}x_{1} o.w. x_{1}y_{1} o.w. x_{2}y_{1} o.w. bx_{2} by_{1} o.w. bx_{1} o.w. cx_{2} o.w. cx_{2} o.w. ad o.w. dy_{1} o.w. bd o.w. Figure 3.2 : The early strategy of P_{1} In the following proof, we will frequently invoke Claim 3.1 or Claim 3.2 to demonstrate that P_{1} can win the game within a finite number of moves. For convenience, we group some similar cases together for explanation. a x_{1} x_{2} x_{3} c y_{1} b (a) Graph:(1) a x_{1} x_{2} x_{3} y_{1} b (b) Graph:(2) a b x_{1} x_{2} x_{3} y_{1} (c) Graph:(5) Figure 3.3 : The graphs (1) (2) and (5) Case 1. Proofs of (1), (2) and (5). Proof. For graphs (1) and (2), P_{1} claims bx_{j} for some j\in[3] in round 4 , where x_{j} has the highest degree in the graph claimed by P_{2} and b is an unused vertex. Then P_{1} claims bx_{j} for some j\in[3] which has not been claimed in round 5 . Without loss of generality, assume that e^{(1)}(4)=bx_{1} and e^{(1)}(5)=bx_{2} . For graph (5), P_{1} claims bx_{2} or bx_{3} which has not been claimed in round 5 . We claim that no matter how P_{2} claims before round 5, we can apply Claim 3.2 ( x_{1} or x_{2} ). Let H be the graph obtained by P_{2} after the round 5 . It is sufficient to show that: P_{1} is not in check before round 6 and neither x_{1} nor x_{2} is contained in C_{4} in graph H . First, suppose that both x_{1} and x_{2} are vertices belonging to some C_{4} in H . Since e(H)=5 , we know that x_{1},x_{2} must belong to the same 4 -cycle, say C . • For graph (1), since bx_{1},bx_{2}\notin E(H) , C does not contain b , which implies that V(C)=\{x_{1},x_{2},c,y_{1}\} . We derive that P_{2} claims one of \{x_{1}x_{2},x_{1}c,x_{1}y_{1},x_{2}c,x_{2}y_{2}\} in round 2 , a contradiction. • For graph (2), C does not contain a and b as ax_{1},ax_{2},bx_{1}bx_{2} have been claimed by P_{1} . Then e(H)\geq|E(C)\cup\{ay_{1},bx_{3}\}|\geq 6 , a contradiction. • For graph (5), clearly, there is no C_{4} containing both x_{1} and x_{2} . Thus, one of x_{1},x_{2} does not belong to the C_{4} in H . Now, suppose that P_{1} is in check, which implies that H is isomorphic to K_{2,2}(1) . • For graphs (1) and (2) , note that x_{3} is unused before round 3 and b is unused before round 4. P_{2} must claim an edge containing either x_{3} or b from round 3 to 5 , since the sum of the degree of x_{3},b in H is at least 4 . If H does not contain x_{1} and x_{2} , then the degree of x_{1},x_{2} is zero in H , which contradicts the choice of bx_{3} . Without loss of generality, we assume that H contains x_{2} , which implies that P_{2} claims x_{2}y_{1} (it could also be x_{2}c for graph (1)) in round 2 , a contradiction. • For graph (5) , since x_{3}a has been claimed by P_{1} , P_{1} can not be in check. ∎ a x_{1} x_{2} c y_{1} (a) Graph:(3) a x_{1} x_{2} c y_{1} (b) Graph:(4) a x_{1} x_{2} b y_{1} (c) Graph:(6) Figure 3.4 : The graphs (3) (4) and (6) Case 2. Proofs of (3), (4) and (6). Proof. For graphs (3), (4) and (6), P_{2} can claim two more edges. Clearly, no matter how P_{2} claims these two edges, P_{2} cannot obtain a C_{4} containing x_{2} . For graphs (3) and (4), unless P_{2} claims ca and cx_{2} , we can apply Claim 3.1 ( x_{2}a or x_{2}y_{1} ) to show that P_{1} can win within 6 rounds. Now we suppose that P_{2} claims ca and cx_{2} . • For graph ( 3 ), P_{1} will claim ab for some unused vertex b in the next round. Then no matter how P_{2} claims the edge in the next round, P_{2} is C_{4} -free. By Claim 3.2 , we derive P_{1} can win within 5 rounds. • For graph ( 4 ), we can apply Claim 3.1 to show that P_{1} can win within 5 rounds. • For graph (6), since (3) and (6) are isomorphic, P_{1} can also win within 6 rounds. ∎ a x_{1} x_{2} c b y_{1} (a) Graph:(7) a x_{1} x_{2} y_{1} c (b) Graph:(8) a x_{1} x_{2} b c y_{1} (c) Graph:(9) Figure 3.5 : The graphs (7) (8) and (9) Case 3. Proofs of (7), (8) and (9). Proof. For graphs (7), (8) and (9), P_{2} can claim two more edges. Clearly, no matter how P_{2} claims those two edges, P_{2} cannot obtain a K_{2,2}(1) , which implies that P_{1} is not in check. • For graphs (7) (8), no matter how P_{2} claims those two edges, P_{2} cannot obtain a C_{4} containing vertex a . By Claim 3.2 , P_{1} can win within 6 rounds. • For graph (9), no matter how P_{2} claims those two edges, P_{2} cannot obtain a C_{4} containing c . By Claim 3.2 , P_{1} can win within 6 rounds. ∎ a x_{1} x_{2} c b y_{1} d (a) Graph:(10) a x_{1} x_{2} y_{1} c d (b) Graph:(12) a x_{1} x_{2} b c y_{1} d (c) Graph:(14) Figure 3.6 : The graphs (10) (12) and (14) Case 4. Proofs of (10), (12) and (14). Proof. For graphs (10), (12) and (14), P_{2} can claim one more edge. If P_{2} is C_{4} -free, then by claim 3.2 , P_{1} can win within 5 rounds. Suppose that P_{2} contains a C_{4} . • For graph (10), P_{2} must claim by_{1} or bc . Similar to the proof of Claim 3.2 , P_{1} could claim x_{2}z_{i} for i\in[3] consecutively, for three unused vertices z_{i} , then P_{2} must claim dz_{i} for i\in[3] . Thus, P_{1} can obtain a K_{2,3} by claiming two of the edges form x_{1}y_{i} for i\in[3] . • For graph (12), P_{2} must claim dx_{1} or dx_{2} . By Claim 3.2 , respectively, P_{1} can win within 5 rounds. • For graph (14), it is impossible for P_{2} to obtain a C_{4} by adding just one more edge. ∎ a x_{1} x_{2} c b y_{1} d (a) Graph:(11) a x_{1} x_{2} y_{1} c d (b) Graph:(13) a x_{1} x_{2} b c y_{1} d (c) Graph:(15) Figure 3.7 : The graphs (11) (13) and (15) Case 5. Proofs of (11), (13) and (15). Proof. For graphs (11), (13) and (15), P_{2} can claim two more edges. Clearly, no matter how P_{2} claims those two edges, P_{2} cannot obtain a K_{2,3} . So P_{2} must claim the dashed lines in the graphs. • For graphs (13) and (15), it is impossible for P_{2} to obtain a C_{4} by adding just one more edge. By Claim 3.2 , P_{1} can win within 5 rounds. • For graph (11), it is impossible for P_{2} to obtain a C_{4} containing x_{2} by adding just one more edge. By Claim 3.2 , P_{1} can win within 5 rounds. ∎ 4 Concluding remarks The main contribution of this paper is the discovery of a new family of graphs K_{2,t+1}(t-2) and our demonstration that P_{1} cannot win the game R(K_{n}\sqcup K_{n},K_{2,t+1}(t-2)) for t\geq 3 . Moreover, the condition t\geq 3 is optimal, since P_{1} can win the game when t=2 . We suspect that these graphs could be promising candidates for answering Beck’s major conjecture: there exists some graph H such that player 1 cannot win the game R(K_{n},H) within a bounded number of moves. On the other hand, we are interested in identifying which graphs H allow P_{1} to win the game R(K_{n},H) . While we have already proven this for cycles, it would be interesting to explore additional graphs. As mentioned earlier, the problem of significantly improving the upper bound L(K_{n},K_{5})\leq\left(\frac{3}{4}+o(1)\right)\binom{n}{2} remains open. More broadly, while it is conjectured that for any graph H , L(K_{n},H)\leq C_{H} for some constant C_{H} , examples that substantially improve upon the trivial upper bound provided by the Turán number are quite rare. Hence, we believe the following problem is of independent interest. Problem 4.1 . Find more graphs H for which L(K_{n},H) is sufficiently smaller than \textup{ex}(n,H) . For example, we say a graph H is 2 -color-critical if there is some edge e\in E(H) such that H is not bipartite, but H-e is bipartite. Next, we can establish an upper bound that is better than (\frac{1}{4}+o(1))n^{2} . Proposition 4.2 . For any given 2 -color-critical graph H , we have L(K_{n},H)\leq O(n^{2-\frac{1}{|H|}}). Proof of Proposition 4.2 . Suppose that the game is not finished after C_{H}n^{2-\frac{1}{|H|}} moves, where C_{H}>0 is a sufficiently large constant. By the famous Kővári–Sós–Turán theorem [ 16 ] , P_{1} must have claimed a copy of K_{|H|,|H|}=L\cup R . Since the game has not ended, there must be some unclaimed edges in both parts L and R . At this point, P_{1} can claim an arbitrary unclaimed edge, say e . Note that H is a subgraph of K_{|H|,|H|}+e , ensuring that P_{1} wins. ∎