Hamilton-cycle time-and-budget trade-off conjecture

Let a $(t,b)$-strategy $B$ of Builder be a strategy that observes at most $t$ arriving edges and purchases at most $b$ of them. A graph is Hamiltonian if it contains a Hamilton cycle. Hamilton-cycle time-and-budget trade-off conjecture. There exists $\varepsilon>0$ such that, if

$$t\le(1+\varepsilon)n\log n/2\quad\text{and}\quad b\le(1+\varepsilon)n,$$

then for any $(t,b)$-strategy $B$ of Builder,

$$\lim_{n\to\infty} \mathbb{P}(B_t\text{ is Hamiltonian})=0.$$

The conjecture says that simultaneously near-optimal observation time and near-optimal budget do not suffice to construct a Hamilton cycle with high probability. It complements the paper's results showing success when either time or budget is inflated by a constant factor.