Linear upper-bound conjecture for random-walk speed-up

Let $G$ be a graph, let $k\geq 1$ be the number of random walks, and write $S^k(G)$ for their speed-up in covering the graph. Linear speed-up conjecture. For any graph $G$ and any $k\geq 1$,

$$S^k(G)\leq O(k).$$

Questions about the minimal and maximal speed-up as functions of $k$ remain open; the paper presents this as the conjectured universal upper bound, despite examples with exponential speed-up under additional starting-point assumptions.