Erdős Problem #778

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

Each move colours one previously uncoloured edge, and the game ends when all edges are coloured. Bob wins ties as well as a larger blue clique, since Alice's winning condition is a strict inequality. Strategies may depend on the complete history. [S1] [S2]

Statement recorded in the supplied source.

Alice and Bob play a game on the edges of $K_n$, alternating colouring edges by red (Alice) and blue (Bob). Alice goes first, and 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.) [S1]

Residual task reported by the archive.

The embedded review (2026-08-17) records: Eliminate all possible Alice-winning n>=3 in the first clique game, or exhibit an exception. [S1]

Short English statement

Can the second player always prevent the first player's largest final clique from being strictly larger than every clique of the second player's colour?

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 2300 (EP-778), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 T. F. Bloom, Erdős Problems, Problem 778, https://www.erdosproblems.com/778. Reference from the supplied record; the live problem page was not independently checked for this compilation.

• S3 Alexandru Malekshahian and Sam Spiro, On a Clique-Building Game of Erdős, Journal of Graph Theory (2026), article jgt.70061. https://doi.org/10.1002/jgt.70061. Bibliographic information from the supplied record.

• S4 Oxford University Research Archive record for Malekshahian--Spiro (published 2026-05-14). https://ora.ox.ac.uk/objects/uuid%3A9860b403-00c0-47a1-9a2e-609494faec80. Bibliographic information from the supplied record.

• S5 Malekshahian, A. and Spiro, S., On a clique-building game of Erdős. arXiv:2410.18304 (2024). Bibliographic information from the supplied record.