Square-root upper-bound conjecture for the synchronous-to-asynchronous guaranteed spreading ratio

Let $G$ be an $n$-vertex graph, and let $\operatorname{gst}_{\mathsf s}(G)$ and $\operatorname{gst}_{\mathsf a}(G)$ denote its synchronous and asynchronous guaranteed spreading times. The ratio compares the performance of the two rumour-spreading protocols.

Synchronous-to-asynchronous ratio conjecture. For any $n$-vertex graph $G$,

$$\frac{\operatorname{gst}_{\mathsf s}(G)}{\operatorname{gst}_{\mathsf a}(G)} = O\left(\sqrt n\,(\log n)^{O(1)}\right),$$

and this bound is tight for infinitely many graphs.

The paper proves a lower and upper bound on this ratio and exhibits infinitely many graphs with a polynomially large ratio; the conjecture proposes the sharper square-root scale, up to a polylogarithmic factor, and asserts that this scale is attained infinitely often.