On edge-colouring-games by Erdős, and Bensmail and Mc Inerney Stijn Cambie, Michiel Provoost Abstract We study two games proposed by Erdős, and one game by Bensmail and Mc Inerney, all sharing a common setup: two players alternately colour edges of a complete graph, or in the biased version, they colour p p and q q edges respectively on their turns, aiming to maximise a graph parameter determined by their respective induced subgraphs. In the unbiased case, we give a first reduction towards confirming the conjecture of Bensmail and Mc Inerney, propose a conjecture for Erdős’ game on maximum degree, and extend the clique and maximum-degree versions to edge-transitive and regular graphs. In the biased case, the maximum-degree and vertex-capturing games are resolved, and we prove the clique game with ( p , q ) = ( 1 , 3 ) (p,q)=(1,3) . 1 Introduction We consider three games: two proposed by Erdős [ 1 ] (popularised last year at BCC by Cameron [ 9 ] and as a problem in the Erdős’ problem database, https://www.erdosproblems.com/778 ), and one by Bensmail and Mc Inerney [ 7 ] , all with a similar setup. We first describe the shared principles of these games. Consider a graph G of order n and size m. Alice and Bob play a game, taking turns to colour the edges of G red (Alice) and blue (Bob), where Alice is the starting player (player 1 ), and Bob is the second player (player 2 ). When all edges are coloured, a score, which depends on the set of red edges A and the set of blue edges B , is assigned. Here Alice has score a and Bob b , where a and b depend on the final colouring of G , i.e., on G[A] and G[B] (the graphs induced by the edges in their colour respectively). In the studied games, a and b will be bounded by the order of the graph, n . Both players play optimally, ensuring that their score is as high as possible relative to the other’s score. The score of the game, s(G) , equals the difference a-b . Alice tries to maximise s(G) , while Bob tries to minimise s(G) . To ensure a unique outcome (a,b) , we assume Alice tries to maximise a for the optimal value of s=a-b , and Bob tries to minimise it for the optimal value of s=a-b . Equivalently, considering the outcome-function f(G)=(C+1)a-Cb=C(a-b)+a for some C\geq n , Alice wants f(G) to be as large as possible and Bob wants f(G) to be as small as possible. By Zermelo’s theorem [ 13 ] , we know f(G) and s(G) are uniquely determined when both players play optimally. So, there is a unique optimal outcome (a,b). The three games we will discuss are called the Clique game, the Star game and the vertex-capturing game. When played on a graph G , the games are denoted by \Clique(G),\Star(G) or \VC(G) respectively, and when G=K_{n} , we write \Clique(n),\Star(n) or \VC(n). • In the Clique game, a=\omega(G[A]) and b=\omega(G[B]) . • In the Star game, a=\Delta(G[A]) and b=\Delta(G[B]) . • In the vertex-capturing game, at the end of the game; a is the number of vertices for which most incident edges are red, and b is the number of vertices for which most incident edges are blue ( a+bp and Bob wins if at the end b>a for the respective parameters of the game, or q=p and Bob wins if a=b. To specify the parameters p and q , we write \Clique_{(p,q)}(G) or \Clique_{(p,q)}(n) and use analogous notation for the other two games. Erdős conjectured that for \Clique(n) , the second player can always force a win as long as n\not=2, and asked the same question for \Star(n) . Conjecture 2 . [ [ 1 ] ] \Clique(n) is a player 2 win, s_{\omega}(n)=0 , for all n\in\mathbb{N}\setminus\{2\}. Question 3 ( [ 1 ] ) . For every n\in\mathbb{N}, which player wins the game \Star(n) (when is s_{\Delta}(n)=1 )? Bensmail and Mc Inerney [ 7 , Conj. 7.2] conjectured the exact outcome for the vertex-capturing game (on cliques), and confirmed it for n\leq 6 , in [ 7 , Prop. 7.6] . Conjecture 4 ( [ 7 ] ) . s_{\VC}(n)=\begin{cases}2\mbox{ if }n=2\\ 1\mbox{ if }n\equiv 3\pmod{4}\\ 0\mbox{ otherwise. }\\ \end{cases} We prove one implication between the validity of Conjecture 4 for two residue classes modulo 4 . 1 1 1 This proof by strategy stealing is similar to reductions in [ 11 ] and was obtained before their publication, as communicated with them. Proposition 5 . If Conjecture 4 is true for every n\equiv 3\pmod{4}, then it is true for every n\equiv 1\pmod{4} as well. This is done in Section 2 , where, for completeness, we also extend an observation by [ 11 ] using strategy stealing, confirming that \Clique(n) being a win for the first player implies that \Clique(n+3) is a win for the second player for every n . Finally, we give our intuition, formulated in conjectures for the Clique and Star game (stated in the framework of edge-transitive and regular graphs). In particular, we are the first to conjecture the answer for Question 3 . Conjecture 6 . With the exception of K_{2} , for every edge-transitive graph G , the Clique game is winning for the second player, i.e., s_{\omega}(G)=0. Conjecture 7 . With the exception of K_{2} and K_{3} , for every regular graph G , the Star game is winning for the second player, i.e., s_{\Delta}(G)=0. At the end of their conclusion, Malekshahian and Spiro [ 11 ] wondered whether studying \Star_{(p,q)}(n) would be interesting. In Section 3 , more precisely Theorem 11 , we notice that both \Star_{(p,q)}(n) and \VC_{(p,q)}(n) are (up to some small cases) player 2 wins whenever q>p. In [ 11 ] , the authors noted that \Clique_{(p,q)}(n) is a player 2 win for an exponential bound of q in p . In Section 3 , we improve this drastically to a (unconditional) quadratic bound and a (conditional) linear bound. Erdős [ 1 ] also asked if \Clique_{(1,2)}{(n)} is won by the second player whenever n\geq 4. We conjecture this is indeed the case. Our main result in this direction proves this when q=2 is replaced by q=3 . (Notice that in [ 11 ] , it is proved with q=15 ) Theorem 8 . For every n\geq 4 , \Clique_{(1,3)}(n) is won by player 2. Despite the interest of many mathematicians, little progress has been made on fully resolving Question 3 and conjectures 2 and 4 , or the unbiased p=q versions. At the end of our work, we highlight the underlying difficulties that may explain why this is so hard and remains unresolved. In Section 5 , we consider the three games for Colex graphs. A Colex graph \mathcal{C}(m) , where m=\binom{m_{1}}{2}+m_{2} with 0\leq m_{2}0 ). See Fig. 3 for examples where (m_{1},m_{2})\in\{(4,3),(5,2)\}. As a class of graphs that smoothly extend cliques, this serves as a showcase to challenge certain intuitive expectations by exhibiting particular behaviours. The results were found by computer code (which implements the idea of Zermelo’s theorem [ 13 ] ), explained in Section 6 . 2 Further results by strategy stealing In this section, we present the proof of Proposition 5 . Proof of Proposition 5 . Let n\equiv 1\pmod{4} where n\geq 5 . Alice colours one edge, which we call uv , red. Bob plays on the other vertices, which induce a K:=K_{n-2} , optimally (being the first player there). Whenever Alice colours an edge ux or vx , for x\in V(K), Bob colours the other of the two in his colour. If Alice colours an edge in K, so does Bob. Since s_{\VC}(K)=1, and for every x\in V(K), there are two edges outside K with different colours, Bob captures one vertex more among those n-2 (by the assumption that Conjecture 4 is true for n-2\equiv 3\pmod{4} ). By the pigeon hole principle, one vertex of \{u,v\} has at least \mathopen{}\left\lceil\frac{n-2}{2}\right\rceil\mathclose{}=\frac{n-1}{2} incident edges coloured by Bob. Hence Alice will have captured exactly one vertex among u and v. This implies that Bob does not lose. By a strategy stealing argument, Alice will not lose either ( [ 7 , Thm. 2.2] ), and this implies that s_{\VC}(K_{n})=0. ∎ As a corollary of Proposition 5 , together with the computer verification for n\leq 8 , we know that Conjecture 4 is true for n\leq 9. When 4\mid n, the truth of Conjecture 4 appears natural since we know that s_{\VC}(G)\in\{0,2\} , while the size and order are both even. Nevertheless, taking into account that \VC(\mathcal{C}(12))\not=0 (see Table 1 ) while \mathcal{C}(12) has even order and even size, a proof cannot be trivial. Also one might think about mirror strategies creating isomorphic coloured graphs on even size cliques K_{n}. Nevertheless, already for n\in\{4,5\} it can be checked that there is no winning strategy for the second player for the creation of isomorphic coloured graphs. In [ 11 ] , the authors proved that if Alice wins \Clique(n) (something that conjecturally is only the case when n=2 ), then Bob wins \Clique(n+3) for n\geq R(5,5). This was later included on https://www.erdosproblems.com/778 (at that time) without the condition that n has to be sufficiently large. Here we prove that it is indeed a valid statement for all n . This follows in essence from [ 11 , Rem. 8] with the additional observation that n\geq R(3,4)=9 instead of n\geq R(4,4)=18 also works, and the computer check for n\leq 8 (checked with independent implementation for n\leq 7 ). Proposition 9 . If Alice wins \Clique(n) for n\geq 8 , then Bob wins \Clique(n+3). Bob wins \Clique(n) for 3\leq n\leq 8. Proof. The fact that Bob wins \Clique(n) for 3\leq n\leq 8 was done by the implementation. Next, we observe that if Alice wins \Clique(n) for n\geq 8 , she has at least 4 points, \omega(G[A])\geq 4 . Observation 10 . Every graph with order n=8 and size 14 satisfies \omega(G)\geq 3 or \alpha(G)\geq 4 . Proof. Easily verified by exhaustive computer check. The three graphs of order 8 satisfying \omega(G)=2 and \alpha(G)=3 have size 10,11 and 12 (and R(2,4)\frac{n}{2}>\Delta_{A} . ∎ It can be observed that for (p,q)=(1,2), n\geq 3 is sufficient. Proposition 12 . The games \Delta_{(1,2)}(n) and \VC_{(1,2)}(n) are both player 2 wins provided that n\geq 3. Proof. Write n=3k+r , where k\geq 1 and 0\leq r\leq 2. Let the vertices be partitioned in U=\{u_{1},u_{2},\ldots,u_{k}\},V=\{v_{1},v_{2},\ldots,v_{k}\} and W=\{w_{1},\ldots,w_{k}\} , and also x if r=1 or x and y if r=2 . Bob colours the two other vertices for triples of the following form: \{u_{i}u_{j},v_{i}v_{j},w_{i}w_{j}\},\{u_{i}v_{i},u_{i}w_{i},v_{i}w_{i}\},\{u_{i}v_{j},v_{i}w_{j},w_{i}v_{j}\},\{xu_{i},xv_{i},xw_{i}\},\{yu_{i},yv_{i},yw_{i}\}, where 1\leq i,j\leq k. In this case the number of blue incident edges to (at least one) of u_{i},v_{i},w_{i} is double the number of red such edges. As such, \Delta_{A}<\Delta_{B} and Bob captured at least k vertices more than Alice did. ∎ Next, we consider regimes in which \Clique_{(p,q)}(n) is won by the second player. By applying [ 4 , Thm. 2] , we get a general improvement for the general biased clique game. We recall the latter statement for convenience, formulated slightly different (the way applied in [ 4 , Thm. 1] ). Theorem 13 ( [ 4 ] ) . Let G be a graph of order n and size bounded by \frac{\binom{n}{2}}{k} . Then \max\{\omega(G),\alpha(G)\}>c_{4}\frac{k}{\log k}\log n. Theorem 14 . There is a constant c such that if q>cp^{2} , then for every n sufficiently large, \Clique_{(p,q)}(n) is won by player 2. Proof. Let c=\frac{2}{c_{4}}, where c_{4} is as in Theorem 13 . Then for n sufficiently large, the ratio of edges coloured by the first player is bounded by p+\frac{p}{p+q}\binom{n}{2}<\frac{\binom{n}{2}}{k} for q+1\geq k\geq\frac{q}{p}>\frac{2}{c_{4}}p. By Theorem 13 , the graph of at least one of the two players contains a clique of order no less than c_{4}\frac{k}{\log k}\log n. By [ 2 , Thm. 20.1] on the other hand, the second player can force the largest clique induced by the colour of the first player to be bounded by \frac{2p}{\log(q+1)}\log n. Since c_{4}\frac{k}{\log k}>\frac{2p}{\log(q+1)}, we conclude the second player wins. ∎ For further (conditional) improvement, we consider Maker-Breaker games, in which Maker tries to obtain a clique K_{q} in its colour, and Breaker tries to prevent that. Let f_{N}(m,b) denote the largest q such that Maker can occupy a K_{q} in the (m:b) game (Maker has m edges and Breaker has b edges) played on K_{N} . The value of f_{N}(1,1)\sim 2\log_{2}N is known exactly by Beck [ 2 , Thm. 6.4] . Beck [ 2 , Thm. 30.2] also gave lower bounds for f_{N}(m,1) of the form 2(1+o(1))\log_{(m+1)/m}(N) and Gebauer [ 5 , Thm. 1.3] gave a lower bound on f_{N}(m,b) , (1+o(1))m\log_{b+1}(N) . Motivated by these lower bounds, we state the following conjecture. Conjecture 15 . For fixed b,m , for N sufficiently large f_{N}(m,b+1)\omega_{A} . ∎ By the results from Beck, this in particular implies that the second player wins \Clique_{(1,3)}(n) provided that n is sufficiently large. In Section 4 , we prove this for all n\geq 4 . It is also natural to conjecture the following sharp version for the game. Conjecture 17 . Provided that n is sufficiently large, the \Clique_{(p,p+1)}(n) is won by player 2. 4 The biased clique game \omega_{1,3} There are multiple elementary proofs possible when n is even. We provide the one solution we could modify for the odd case. Theorem 18 . For every n\geq 4 even, \Clique_{(1,3)}(n) is won by player 2. Proof. We will consider a turn as one move (colouring an edge) by Alice and (at most) 3 moves of Bob. Since Bob can also play some of the remaining edges randomly, the win for Bob will be kept, so we present the strategy for Bob in this simpler way. The n=2k vertices are initially unlabeled vertices. During the game, a vertex is labeled as soon as at least one of its incident edges is coloured, or when there are only two vertices without coloured incident edges, in which case both are labeled. Initial play Here we assume that at the beginning of the turn, at least 4 vertices are unlabeled. The 2m labeled vertices will have indices which appear in pairs (v_{i},v_{i+k}) , where 1\leq i\leq m . The edges v_{i}v_{i+k} , will be coloured by Bob. If an edge v_{i}v_{j} is coloured by Alice, the symmetric edge v_{i+k}v_{j+k} will have been coloured by Bob. Here indices can be considered modulo 2k throughout. Depending on the edge Alice chooses, Bob reacts as follows. • If Alice colours an edge between two unlabeled vertices, we will label them as v_{i},v_{j} (where i=m+1,j=m+2 ). Bob picks two unlabeled vertices, calls them v_{i+k},v_{j+k} , and colours the edges v_{i}v_{i+k},v_{i+k}v_{j+k},v_{j}v_{j+k} . • If Alice colours an edge whose endvertices contain a labeled one, v_{i} , and one unlabeled one, which we call v_{m+1}. Bob takes an other unlabeled vertex, v_{m+1+k}, and colours v_{i+k}v_{m+1+k} and v_{m+1}v_{m+1+k} . • If Alice colours an edge v_{i}v_{j} whose end vertices are already labeled, Bob colours v_{i}v_{j+k},v_{i+k}v_{j+k} and v_{j}v_{i+k} (some of these edges may have been coloured before by Bob if the vertices v_{i},v_{j} were labeled in the same turn). If two unlabeled vertices remain at the end of the turn, we label them by x and y , and we go to the final play. Finishing play • If Alice colours xy , Bob colours no edges. • If Alice colours xv_{i} , then Bob colours xv_{i+k},yv_{i} and yv_{i+k} . • If Alice colours yv_{i} , then Bob colours xv_{i},xv_{i+k} and yv_{i+k} . • If Alice colours an edge v_{i}v_{j} whose end vertices are already labeled, then Bob responds as during the initial play; that is, he colours v_{i}v_{j+k},v_{i+k}v_{j+k} and v_{j}v_{i+k} (some of these edges may have been coloured before by Bob if the vertices v_{i},v_{j} were labeled in the same turn). Having sketched a winning strategy for Bob, we prove that Bob wins. Consider a largest clique induced by all vertices different from x and y for which all edges are coloured by Alice. Up to shifting and relabeling opposite vertices, we denote it v_{1}v_{2}\ldots v_{r}. This clique has order r\geq 2. In that case, by the strategy of Bob, he coloured the clique v_{k+1}v_{k+2}\ldots v_{k+r} containing all symmetric edges. There are at most r-1 edges among G[v_{1},v_{2},\ldots,v_{r}] which have been coloured by Alice at a moment at least one of its endvertices was unlabeled. For each of these edges v_{i}v_{j} , the clique G[v_{i},v_{j},v_{i+k},v_{j+k}]\cong K_{4} contains two edges coloured by Alice. If v_{i}v_{j} was already labeled before Alice coloured that edge, it is the only edge within G[v_{i},v_{j},v_{i+k},v_{j+k}] which is coloured by her. This implies that the bipartite graph spanned by the partition classes V_{1}=\{v_{1},v_{2},\ldots,v_{r}\} and V_{2}=\{v_{k+1},v_{k+2},\ldots,v_{k+r}\} has at most r-1 blue edges. This implies that there is a vertex v_{i} in V_{1} such that G[v_{i},V_{2}] is fully coloured by Bob. That is, G[V_{2}\cup\{v_{i}\}] is a clique of order r+1 fully coloured by Bob. By Bob’s strategy, Alice has no triangle containing the edge xy that is fully coloured. If Alice has a large fully coloured clique containing x , then it must be of the form V_{1}\cup\{x\} ; analogously, if it contains y , it must be of the form V_{1}\cup\{y\} . But then the clique spanned by V_{2}\cup\{v_{i},y\} (resp. V_{2}\cup\{v_{i},x\} ) is fully coloured by Bob. ∎ Theorem 19 . For every n\geq 5 be odd, \Clique_{(1,3)}(n) is won by player 2. Proof. The setup and initial play proceed as in Theorem 18 , up to the point where either three unlabeled vertices remain and Alice colours an edge incident to at least one of them, or five unlabeled vertices remain and Alice begins colouring an edge between two of these. The labeled vertices (possibly after relabeling), can be L=\{v_{i}\mid 1\leq i\leq 2k\} where v_{i} and v_{i+k} form a pair of opposite vertices. Here n=2k+3 or n=2k+5 . When n=2k+3 , we call the the three remaining unlabeled vertices a,b,c. When n=2k+5 , we name the end vertices of the edge coloured by Alice x,y . We label the other three by a,b,c. We present the final play in each of the following three situations. Case 1: n=2k+3 and Alice colours av_{\ell} Bob colours the edges of abc . From now on; • If Alice colours an edge in \{a,b,c\}\times\{v_{\ell},v_{\ell+k}\} , then Bob can colour edges among \{a,b,c\}\times\{v_{\ell},v_{\ell+k}\} (but does not even have to). • If Alice colours an edge v_{i}v_{j}\in G[L] , Bob colours v_{i}v_{j+k},v_{i+k}v_{j+k} and v_{j}v_{i+k} (some of these edges may have been coloured before by Bob if the vertices v_{i},v_{j} were labeled in the same turn). • If Alice colours an edge in dv_{i} for some d\in\{a,b,c\} , then Bob colours av_{i+k},bv_{i+k} and cv_{i+k} . If those three were already coloured, Bob colours the uncoloured edge among av_{i},bv_{i} and cv_{i} . If a largest clique of Alice is contained in G[L], Bob has a larger clique within G[L], as shown before in the proof of Theorem 18 . If the largest clique contains one vertex from \{a,b,c\} and w.l.o.g. V_{1}=\{v_{1},v_{2},\ldots,v_{r}\} ( r vertices from L . Let V_{2}=\{v_{k+1},v_{k+2},\ldots,v_{k+r}\} . Bob has a clique spanned by the vertices V_{2}\setminus\{v_{\ell},v_{\ell+k}\}\cup\{a,b,c\} , so its clique number is at least r+2. Case 2: n=2k+3 and Alice colours ab Bob reacts by colouring the other two edges of abc . From now on; • If Alice colours an edge av_{i} , then Bob colours bv_{i},bv_{i+k} and cv_{i+k}. Symmetrically, if Alice colours an edge bv_{i} , then Bob colours av_{i},av_{i+k} and cv_{i+k}. • If Alice colours an edge in cv_{i} , then Bob colours av_{i+k},bv_{i+k} and cv_{i+k}. • If Alice colours an edge v_{i}v_{j}\in G[L] , Bob colours v_{i}v_{j+k},v_{i+k}v_{j+k} and v_{j}v_{i+k} (some of these edges may have been coloured before by Bob if the vertices v_{i},v_{j} were labeled in the same turn). If a largest clique of Alice is contained in G[L], Bob wins as before. If a largest clique of Alice is of the form \{a,v_{1},v_{2},\ldots,v_{r}\} , then Bob has a clique spanned by \{b,c,v_{k+1},v_{k+2},\ldots,v_{k+r}\} . Similarly, \{b,v_{1},v_{2},\ldots,v_{r}\} or \{c,v_{1},v_{2},\ldots,v_{r}\} would be a smaller clique than \{a,c,v_{k+1},v_{k+2},\ldots,v_{k+r}\} . Case 3: n=2k+5 and Alice colours xy Bob reacts by colouring the edges of abc . From now on; • If Alice colours an edge in av_{i},bv_{i} or cv_{i} , then Bob colours av_{i+k},bv_{i+k} and cv_{i+k}. • If Alice colours xv_{i} or yv_{i}, Bob colours the three remaining edges in \{x,y\}\times\{v_{i},v_{i+k}\}. • If Alice colours w.l.o.g. ax , Bob colours ay,by and cy. (the 6 edges are all equivalent) If later, Alice colours bx or cx , Bob colours the other edge among those two. • If Alice colours an edge v_{i}v_{j}\in G[L] , Bob colours v_{i}v_{j+k},v_{i+k}v_{j+k} and v_{j}v_{i+k} (some of these edges may have been coloured before by Bob if the vertices v_{i},v_{j} were labeled in the same turn). If a maximum clique from Alice contains at most one vertex from \{a,b,c,x,y\}, then Bob has a larger clique as before. The only clique of Alice containing xy is xy itself. If \{a,x,v_{1},v_{2},\ldots,v_{r}\} is a maximum clique from Alice, then \{b,c,y,v_{k+1},v_{k+2},\ldots,v_{k+r}\} is a monochromatic clique coloured by Bob. In all cases, the maximum clique coloured by Bob is strictly larger than the maximum clique coloured by Alice. ∎ 5 Particular behaviour for some variants and extensions 5.1 Smoothening cliques; the games on Colex graphs Playing the Clique game on K_{n+1} instead of K_{n} implies that there are many more edges to colour. To have a smoother behaviour, we can consider Colex graphs. Let n be the smallest integer for which \binom{n}{2}\geq m. The Colex graphs G=\mathcal{C}(m) of size m can be defined (up to isomorphism) by choosing V(G)=\{1,2,\ldots,n\} and letting E(G) consist of the first m pairs of vertices in colexicographic order (here (a,b)<(c,d) if b