Strict monotonicity conjecture for Maker–Breaker clique games

For positive integers m,bm,b and a positive integer NN, let fN(m,b)f_N(m,b) be the largest integer qq such that Maker can occupy a clique KqK_q in the (m:b)(m:b) Maker–Breaker game played on KNK_N, where Maker claims mm edges and Breaker claims bb edges per turn.

Strict monotonicity conjecture. For fixed b,mb,m, for all sufficiently large NN,

fN(m,b+1)<fN(m,b)<fN(m+1,b),f_N(m,b+1)<f_N(m,b)<f_N(m+1,b),

and both differences tend to infinity as NN\to\infty.

The source notes that the first inequality for m=1m=1 would follow from an unsolved conjecture of Bednarska and Łuczak. The general conjecture is therefore presented as open.

Sources & referencesView supporting material

Primary source

Stijn Cambie and Michiel Provoost, “On edge-colouring-games by Erdős, and Bensmail and Mc Inerney”, arXiv:2505.03497 (2025).

Additional references

5 papers in this index state this conjecture (2014–2025). The statement above is taken from the most recent of them; the others are arXiv:2409.09024, arXiv:2404.10870, arXiv:2109.09053, arXiv:1401.6335.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.