Arithmetic progressions in a random set on a budget

Abstract

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=\ddot{I}‰(n^{1-2/k})$, a budget of $b=\hat{I}˜((n/t{)}^{\frac{k-2}{2}})$ is both necessary and sufficient for Builder to successfully construct a $k$-term arithmetic progression with high probability.