Loose cycles in the budget-constrained random hypergraph process

Abstract

We consider a model of a controlled random graph process introduced by Frieze, Krivelevich and Michaeli. In this model, the edges of the complete graph $K_n$ are ordered randomly and then revealed, one by one, to a player called Builder. She must decide, immediately and irrevocably, whether to purchase an edge. The observation time is bounded by the parameter $t$, and the total budget of purchased edges is bounded by the parameter $b$. Frieze, Krivelevich and Michaeli prove that Builder has a strategy to create a copy of a cycle of length $\ell$ with high probability if $b \gg \max\{n^{k+2/\ell}t^{-1+1/\ell}, n/\sqrt{t}\}$, and this is optimal. We deconstruct their proof and use it as a blueprint for proving an analogous result for loose cycles in uniform hypergraphs. We also show that when $t \gg n^2$, Builder can construct a loose cycle of length $\ell$ with high probability purchasing exactly $\ell$ edges.