Didin 2026 asymptotic solution 1 2 biased erdos

../

---

M. A. Didin, Mark Pimenov, An Asymptotic Solution to the (1:2)-Biased Erdős Clique-Building Game. Zenodo preprint (2026). doi:10.5281/zenodo.21813052. The file prints no license line; the Zenodo record (https://zenodo.org/records/21813052, read 2026-10-02), whose DOI the citation above carries, names the Creative Commons Attribution 4.0 International license in its license field.

In the (1:2)-biased clique-building game on K_n, Bella moves first and takes one unclaimed edge per turn, Chingiz takes two, and Chingiz wins when the clique number of his final graph exceeds that of Bella's. Theorem 1 proves he has a winning strategy for every sufficiently large n, which answers yes, asymptotically, to the 1:2 question that Guy's 1983 problem list attributes to Erdős, matching earlier asymptotic results for bias 1:4 (Malekshahian-Spiro) and 1:3 (Cambie-Provoost). The method is a single greedy rule with two elementary weight functions: Q_A = 3^{-f_A} on a-vertex sets, zeroed by any Chingiz edge, penalizes Bella cliques, while P_U on l-vertex sets forces Chingiz edge density 3/5 inside every large set; Chingiz repeatedly takes a free edge of maximum danger d(e), and Lemma 1 shows the potential Phi = sum Q_A + sum P_U never increases in a round, and Phi < 1 initially. Lemma 2 then extracts a Chingiz clique of size 1 + floor(log_{5/3}((m + 3/2)/(l + 3/2))) from any m >= l vertices, giving omega(G_C) >= log n / log(5/3) - O(log log n) against omega(G_B) <= 2 log n / log 3 + O(1), and the comparison of leading constants reduces to 27 > 25. For problem 778 this settles only the second question asymptotically: there is no explicit threshold n_0, so the claim for every n >= 4 is untouched, as are the unbiased game and the maximum-degree variant. The paper states that the proof was generated by GPT-5.6 Pro under Didin's direction and independently checked by Pimenov.

Source: https://zenodo.org/records/21813052.

Bears on. #778

Results to transcribe.

• Theorem 1: For every sufficiently large n, Chingiz (the two-edge player) has a strategy with omega(G_C) > omega(G_B) in the (1:2)-biased clique-building game on K_n.
• Lemma 1: After Bella's opening move the potential Phi = sum_A Q_A + sum_U P_U does not increase during any round under the maximum-danger greedy rule; the estimate after the lemma gives Phi < 1 initially for all sufficiently large n.
• Lemma 2: Any m >= l vertices span a clique of Chingiz edges on at least R(m) = 1 + floor(log_{5/3}((m + 3/2)/(l + 3/2))) vertices, by iterated passage to the neighborhood of a vertex of at least average degree.
• Clique-number bounds: omega(G_C) >= log n / log(5/3) - O(log log n) and omega(G_B) <= a - 1 = 2 log n / log 3 + O(1); the gap is positive because 1/log(5/3) > 2/log 3, i.e. 27 > 25.