Bollobás–Przykucki–Riordan–Sahasrabudhe conjecture for the $K_5$ running time

Bollobás, Przykucki, Riordan, and Sahasrabudhe conjectured that the maximum running time for the $K_5$ process satisfies $M_{K_5}(n)=o(n^2)$. The central question is whether the running time can actually be quadratic.

Known results

• Balogh, Kronenberg, Pokrovskiy, and Szabó constructed examples with $M_{K_5}(n)\ge n^{2-o(1)}$, using Behrend-type progression-free sets.
• Their analogous conjecture fails for $K_r$ when $r\ge 6$, but their construction does not settle $K_5$.
• For every integer $t\ge 3$, the known upper bound is $M_{K_t}(n)\le\left(\frac{t-3}{t-2}+o(1)\right)\binom{n}{2}$; this is not subquadratic for $t=5$.

2026 upper-bound advance

Liu, Nie, Piga, and Schülke report the first nontrivial general upper bound, giving $M_{K_5}(n)\le\left(\frac{2}{3}+o(1)\right)\binom{n}{2}$. Their paper explicitly says that it remains unknown whether the $K_5$ running time is quadratic, so this advances the bounds without proving or disproving the conjecture.

Current status (as of September 2026): The conjecture remains open; near-quadratic lower bounds and a quadratic-order upper bound are known, but neither $M_{K_5}(n)=o(n^2)$ nor a quadratic lower bound has been established.