Logo
Tags Prizes
More
FAQ Problem Lists Definitions Links How to help
All Random Solved Random Open
OPEN
Alice and Bob play a game on the edges of $K_n$, alternating colouring edges by red (Alice) and blue (Bob). Alice wins if at the end the largest red clique is larger than any of the blue cliques.

Does Bob have a winning strategy for $n\geq 3$? (Erdős believed the answer is yes.)

If we change the game so that Bob colours two edges after each edge that Alice colours, but now require Bob's largest clique to be strictly larger than Alice's, then does Bob have a winning strategy for $n>3$?

Finally, consider the game when Alice wins if the maximum degree of the red subgraph is larger than the maximum degree of the blue subgraph. Who wins?

Malekshahian and Spiro [MaSp24] have proved that, for the first game, the set of $n$ for which Bob wins has density at least $3/4$ - in fact they prove that if Alice wins at $n$ then Bob wins at $n+1,n+2,n+3$.

Similarly, for the third game they prove that the set of $n$ for which Bob wins has density at least $2/3$, and prove the stronger statement that if Alice wins at $n$ then Bob wins at $n+1,n+2$.