Convergence rate of ${\ell }^p$-energy minimization on graphs: sharp polynomial bounds and a phase transition at $p=3$

Gideon Amir, Fedor Nazarov, Yuval Peres

We consider the following dynamics on a connected graph $(V,E)$ with $n$ vertices. Given $p>1$ and an initial opinion profile $f_0:V\to [0,1]$, at each integer step $t\ge 1$ a un…