Dependencies

If every degree is positive, \(|x_t(u)-\sum _v\pi (v)x_0(v)|\le \lambda ^t\sum _v\sqrt{\deg (v)/\deg (u)}\, |x_0(v)|\).

\(x_{t+1}(v)=\frac1{\deg v}\sum _{u\sim v}x_t(u)\), and \(\bar x=\sum _v\deg (v)\, x_0(v)/\sum _v\deg (v)\).

\(G\) is \(d\)-regular on two clusters \(V_1,V_2\) of \(n\) nodes, each node having \(b\) neighbours in the other cluster; \(\chi =\mathbb 1_{V_1}-\mathbb 1_{V_2}\), \(P=A/d\) with eigenvalues \(\lambda _1\ge \lambda _2\ge \dots \), \(\lambda =\max _{i\ge 3}|\lambda _i|\). Node \(v\) is blue at round \(t\) if \(x_t(v)\ge x_{t-1}(v)\); a coloring is a strong reconstruction if no color appears in both clusters. \(T(n,\delta )=\lceil \log (4n^3)/\log (1+\delta )\rceil +1\).

A step on the edge \((i,j)\) multiplies the state by \(W_{ij}=I-\frac12(e_i-e_j)(e_i-e_j)^\top \); a run applies the steps of a list of oriented edges in order. For a stochastic matrix \(P\) (given as a kernel), \(\bar W_P=I-\bar D/2n+(P+P^\top )/2n\) with \(\bar D_{ii}=\sum _j(P_{ij}+P_{ji})\), and \(\bar W=I-L/2m\) with \(L\) the Laplacian.

\(P=D^{-1}A\) is the transition matrix of the random walk, \(N=D^{-1/2}AD^{-1/2}\) its symmetric version with eigenvalues \(\lambda _1\ge \lambda _2\ge \dots \ge \lambda _n\), \(\lambda =\max \{ |\lambda _2|,|\lambda _n|\} \) (\(0\) if \(n{\lt}2\)), and \(\pi (v)=\deg (v)/2m\) with \(m\) the number of edges.

For uniform \(x\in \{ \pm 1\} ^{2n}\), \(P(\langle x,\chi \rangle =0)=\binom {2n}{n}/4^n\le 1/\sqrt{\pi n}\).

\(\sum _v\deg (v)\, x_{t}(v)\) does not depend on \(t\); without isolated nodes, a round never leaves an interval containing all current values.

If \(\lambda {\lt}1-2b/d\) and \(x\in \{ \pm 1\} ^{2n}\), then \(|x_t(v)-\alpha _1-\alpha _2(1-2b/d)^t\chi (v)|\le \lambda ^t\sqrt{2n}\) with \(\alpha _1=\langle x,\mathbb 1\rangle /2n\), \(\alpha _2=\langle x,\chi \rangle /2n\).

\(W_{ij}x\) replaces \(x_i\) and \(x_j\) by their average and keeps the other values; \(W_{ij}\) is doubly stochastic and a symmetric projection, \(W_{ij}^\top W_{ij}=W_{ij}\).

On a connected graph with an odd closed walk, \(\lambda {\lt}1\).

\(P^t(u,v)=W_t(u,v)\) is the probability that the walk from \(u\) is at \(v\) after \(t\) steps, and \(x_t=P^tx_0\). If every degree is positive, \(P\) and \(N\) have the same characteristic polynomial, so \(\lambda \) is computed from the spectrum of \(P\).

\(x_t(v)=\sum _u W_t(v,u)\, x_0(u)\) with \(W_t\) stochastic and \(W_t(v,u){\gt}0\) when a walk of length \(t\) joins \(v\) and \(u\). On a connected graph with an odd closed walk, some length \(L\) joins every pair.

On a connected bipartite graph with at least two nodes, the values \(\pm 1\) of a proper 2-colouring change sign at every round, so they converge nowhere.

On a connected graph with an odd closed walk, \(x_t(v)\to \bar x\) for every \(v\).

On a connected clustered graph with \(1-2b/d{\gt}(1+\delta )\lambda \), if \(x\in \{ \pm 1\} ^{2n}\) and \(\langle x,\chi \rangle \ne 0\), then for \(t\ge T(n,\delta )=O(\log n/\delta )\), \(\operatorname {sgn}(x_{t-1}(u)-x_t(u))=\operatorname {sgn}(\langle x,\chi \rangle \chi (u))\).

If every degree is positive, \(|P^t(u,v)-\pi (v)|\le \sqrt{\deg (v)/\deg (u)}\, \lambda ^t\) for all nodes \(u,v\) and all \(t\).

If a uniformly random node \(i\) contacts \(j\) with probability \(P_{ij}\), then \(\mathbb E[W_{ij}]=\bar W_P\); if a uniformly random oriented edge is selected, then \(\mathbb E[W_{ij}]=\bar W\). On a \(d\)-regular graph with \(d{\gt}0\) and \(P=D^{-1}A\) both equal \((1-1/n)I+P/n\).

For a uniformly random oriented edge, \(\mathbb E[W^\top W]=\bar W\) and \(\mathbb E\| Wx\| ^2=x^\top \bar Wx\); after \(t\) independent uniformly random oriented edges, \(\mathbb E[x_t]=\bar W^tx_0\).

With probability at least \(1-1/\sqrt{\pi n}\), the coloring is a strong reconstruction at every round \(t\ge T(n,\delta )\).