Arithmetic progressions in a random set on a budget

A restricted-budget version of the random graph process, introduced by Frieze, Krivelevich, and Michaeli in 2025, studies the construction of structures by an online player who can purchase only a limited number of random edges.

In this paper, we transfer this framework from random graphs to random subsets of integers, focusing on the construction of $k$-term arithmetic progressions.

A player, Builder, is presented with a sequence of $t$ integers drawn uniformly at random from $[n]$.

As the elements are revealed one by one, Builder must immediately and irrevocably decide whether to select the current integer, subject to a maximum budget of $b$ selected elements in total.

We establish the optimal thresholds for this process, proving that for $t = \omega(n^{1-2/k})$, a budget of $b = \Theta((n/t)^{\frac{k-2}{2}})$ is both necessary and sufficient for Builder to successfully construct a $k$-term arithmetic progression with high probability.