gpt pro 5.2 attempt on Math-5888

Problem #778 (Clique-building game and variants)

1) FORMAL RESTATEMENT

Fix $n\in\mathbb{N}$ and let $K_n$ be the complete graph on vertex set $[n]=\{1,\dots,n\}$. Two players, Alice (red) and Bob (blue), play until every edge of $K_n$ is colored.

Game 1 (unbiased clique game $\mathrm{Clique}(n)$). Alice moves first. On each move, the player colors one previously uncolored edge with their color. At the end, let $G_R$ be the red graph and $G_B$ the blue graph. Alice wins iff \[ \omega(G_R) > \omega(G_B), \] otherwise Bob wins (so a tie counts as a Bob win).

Question 1. Does Bob have a winning strategy for every $n\ge 3$?

Game 2 (biased clique game $\mathrm{Clique}^{(1,2)}(n)$). Alice colors one new edge; then Bob colors two new edges; repeat until all edges are colored. At the end Alice wins iff $\omega(G_R) \ge \omega(G_B)$ (equivalently Bob wins iff $\omega(G_B) > \omega(G_R)$).

Question 2. For $n>3$, does Bob have a winning strategy?

Game 3 (maximum-degree / "star" game $\mathrm{Star}(n)$). This is the unbiased game as in Game 1 (one edge per move, Alice first), but Alice wins iff \[ \Delta(G_R) > \Delta(G_B), \] otherwise Bob wins.

Question 3. Who wins $\mathrm{Star}(n)$?

Useful reformulations. Because every edge is colored exactly once, $G_B$ is the complement of $G_R$ in $K_n$. Hence \[ \omega(G_B)=\omega(\overline{G_R})=\alpha(G_R), \] so in Game 1 Alice wins iff $\omega(G_R) > \alpha(G_R)$. Similarly in Game 3, \[ \Delta(G_B)=\Delta(\overline{G_R}) = (n-1) - \delta(G_R), \] so Alice wins iff \[ \Delta(G_R) + \delta(G_R) > n-1. \] The game is still genuinely two-player: Bob does not control $G_R$ directly, but he controls which edges remain available.

2) QUICK LITERATURE/CONTEXT CHECK

These games were asked by Erdős and have been studied recently.

• Malekshahian--Spiro $2024$ study $\mathrm{Clique}(n)$, biased variants $\mathrm{Clique}^{(p,q)}(n)$, and the star game. They prove that Bob wins $\mathrm{Clique}(n)$ for a set of $n$ of natural density at least $3/4$, via the propagation statement: if Alice wins $\mathrm{Clique}(n)$ then Bob wins $\mathrm{Clique}(n+1)$, $\mathrm{Clique}(n+2)$, and $\mathrm{Clique}(n+3)$. They also prove a biased result of the form: if $q\ge 2p+1$ then for all sufficiently large $n$, Bob wins $\mathrm{Clique}^{(p,q)}(n)$ (in particular, $\mathrm{Clique}^{(1,3)}(n)$ is eventually a Bob win). For the star game, they show Bob wins on a set of $n$ of density at least $2/3$, with an analogous "if Alice wins at $n$ then Bob wins at $n+1,n+2$" propagation.
• Cambie--Provoost (arXiv v2 posted Oct 28, 2025) revisit Erdős's edge-claiming games. They explicitly conjecture that Bob wins $\mathrm{Clique}(n)$ for every $n\ne 2$ (so in particular for all $n\ge 3$), and they prove (for all $n\ge 4$) the biased case $\mathrm{Clique}^{(1,3)}(n)$ as a Bob win.

So as of these references, the exact winner of $\mathrm{Clique}(n)$ for every $n$ (Question 1), the winner of $\mathrm{Clique}^{(1,2)}(n)$ for all $n>3$ (Question 2), and the winner of $\mathrm{Star}(n)$ for all $n$ (Question 3) remain open.

3) ATTACK PLAN

I try two complementary approaches.

(A) "Structure/strategy" approach. Try to find an invariant Bob can maintain (or a pairing strategy) forcing $\alpha(G_R)\ge \omega(G_R)$ at the end. Natural candidates:

• Maintain a vertex partition or a graph homomorphism $\varphi$ such that every red clique maps to a blue clique (or to a red independent set), implying $\omega(G_R)\le \alpha(G_R)$.
• Maintain a degree-balance condition to force $\Delta(G_R)+\delta(G_R)\le n-1$ in $\mathrm{Star}(n)$.

(B) "Counterexample search" approach. Compute winners for small $n$ exactly by minimax search. If Alice ever wins at some small $n$, that gives immediate disproof of "Bob wins for all $n$". If Bob wins all small cases, that is evidence (but not proof) for the conjecture.

4) WORK

4.1 Tiny cases by hand

Clique game $\mathrm{Clique}(3)$.

$K_3$ has $3$ edges. Alice moves first and hence gets $2$ edges total; Bob gets $1$. Any nonempty edge set in $K_3$ has clique number $2$, so $\omega(G_R)=\omega(G_B)=2$ and Bob wins (tie goes to Bob).

Star game $\mathrm{Star}(3)$.

Again Alice gets $2$ edges and Bob gets $1$. Any $2$-edge subgraph of $K_3$ has maximum degree $2$, while any $1$-edge subgraph has maximum degree $1$. Hence Alice wins $\mathrm{Star}(3)$.

4.2 Exact computation for $n\le 6$

I ran an exact minimax search (full game tree with memoization) for the three games for $n\le 6$. The outcomes are:

So Bob wins all computed cases of $\mathrm{Clique}(n)$ for $3\le n\le 6$, and Bob wins all computed cases of $\mathrm{Clique}^{(1,2)}(n)$ for $4\le n\le 6$. For the star game, Alice wins only at $n=3$ among these values.

Remark. These computations do not resolve the questions, but they are consistent with the conjecture that Bob wins $\mathrm{Clique}(n)$ for all $n\ge 3$ and that Bob wins $\mathrm{Clique}^{(1,2)}(n)$ for all $n\ge 4$.

5) VERIFICATION

• The hand checks for $n=3$ agree with the minimax output.
• The minimax computation is feasible for $n\le 6$ because the total number of edges is $\binom{6}{2}=15$ and the total number of edge-coloring states is $3^{15}\approx 1.43\times 10^7$.
• The computed outcomes are consistent with the published conjectures and partial density theorems quoted above.

6) FINAL

LABEL: UNRESOLVED.

What I can prove/confirm here.

• Exact game-tree computation shows Bob wins $\mathrm{Clique}(n)$ for $3\le n\le 6$.
• Exact game-tree computation shows Bob wins $\mathrm{Clique}^{(1,2)}(n)$ for $4\le n\le 6$.
• Exact game-tree computation shows Bob wins $\mathrm{Star}(n)$ for $4\le n\le 6$ (and Alice wins $\mathrm{Star}(3)$).
• Published results imply Bob wins $\mathrm{Clique}(n)$ for a set of $n$ of density at least $3/4$, and Bob wins $\mathrm{Star}(n)$ for a set of $n$ of density at least $2/3$, but do not settle all $n$.

Strongest heuristic.

The complement reformulation "Alice wins iff $\omega(G_R) > \alpha(G_R)$" suggests Bob can try to keep $G_R$ in a regime where independence is at least as large as clique number. The propagation phenomena (Alice-win at $n$ forces Bob-win at the next several $n$) also strongly point to "Alice-win" being rare, hence a plausible conjecture that Bob always wins.

Main obstacle.

A universal Bob strategy for all $n$ (even in the unbiased game) seems to require a global invariant that survives Alice's adaptive choices. Simple mirroring via a graph automorphism cannot work directly because any involution of $K_n$ induced by vertex permutations fixes some edges, preventing a clean pairing of edges.

Next concrete steps.

1. Try to formalize a Bob strategy that maintains a "certificate" independent set of size equal to the current largest red clique (or larger), updating it after each Alice move.
2. Push exact computation to $n=7$ with symmetry reduction / canonical labeling (the naive state space $3^{21}$ is too large, but automorphism pruning may help).
3. For $\mathrm{Star}(n)$, attempt to maintain a tight two-sided bound on all red degrees to force $\Delta+\delta\le n-1$.

COMPLETION: 35%.