Consensus time for asynchronous ${\ell }^p$ relaxation: graph dependence

Abstract

We study the asynchronous ${\ell }^p$ relaxation introduced by Amir, Nazarov, and Peres: at each step, a uniformly chosen vertex minimizes its incident ${\ell }^p$ energy. For the profile $f_t$ after $t$ updates, let $${\mathsf{T}}_p(G,1/2):=\underset{\Vert f_0{\Vert }_{\infty }\le 1}{\sup }\mathbb{E}[\min \{t\ge 0:\mathrm{osc}(f_t)\le 1/2\}].$$ For $1<p<\infty$, we obtain graph-dependent estimates for boxes, trees, and conductance expanders. On the nearest-neighbor box $[L{]}^d$, for $d,L\ge 2$ and $n=L^d$, the answer is, up to logarithmic factors, $n{d}^{1/(p-1)}{L}^{p/(p-1)}$ for $1<p<2$ and $nd{L}^2$ for $p\ge 2$. On bounded-degree trees, an explicit rerooting-invariant parameter $T_G$ determines the answer up to logarithmic factors; for arbitrary trees it gives upper and lower bounds that differ additionally by the maximum degree. If the volume conductance $h(G)\ge h_0>0$, then ${\mathsf{T}}_p(G,1/2)={\Theta }_{p,h_0}(n\log n)$ without a degree assumption. At $p=\infty$, every connected graph satisfies ${\mathsf{T}}_{\infty }(G,1/2)\ge cn{D}^2/\Delta$, where $D$ and $\Delta$ are its diameter and maximum degree.

35 pages