Expansion and the distribution of phases in stable states

PDF p. 4: Section 1, explanation following Theorem 1.2; PDF p. 5: Section 1.1, proof overview; PDF p. 19: Section 3, introduction to mixing lemmas

Assume countable choice. Let $G=(V,E)$ be a finite undirected graph with $n=\mathrm{\mid }V\mathrm{\mid }>0$, symmetric binary adjacency matrix $A$ and possible self-loops. Let $d^{\ast }>0$ and $\alpha \ge 0$, and suppose $G$ is an $(n,d^{\ast },\alpha )$-expander: $\mathrm{\parallel }A-(d^{\ast }\mathrm{/}n)J\mathrm{\parallel }\le \alpha d^{\ast }$, where $J$ is the all-ones matrix and the norm is the Euclidean operator norm. For subsets $X,Y\subseteq V$, write $e(X,Y)={\sum }_{x\in X,y\in Y}{A}_{xy}$; this counts ordered adjacency entries and includes diagonal entries. Then $\mathrm{\mid }e(X,Y)-(d^{\ast }\mathrm{/}n)\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }\mathrm{\mid }\le \alpha d^{\ast }\sqrt{\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }}$. For nonempty $X,Y$, its relative error compared with $(d^{\ast }\mathrm{/}n)\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }$ is at most $\alpha n\mathrm{/}\sqrt{\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }}$.

A phase state assigns an angle modulo $2\pi$ to each vertex. A stable state is a local minimum on the phase torus of ${\mathcal{E}}_G(\theta )=\frac{1}{2}{\sum }_{x,y}{A}_{xy}(1-\cos ({\theta }_x-{\theta }_y))$; it is spurious if its phases are not all equal. At a stable state, ${\sum }_{x,y}{A}_{xy}\cos ({\theta }_x-{\theta }_y)(1-\cos ({\theta }_x-{\theta }_y))\ge 0$. Thus the negative contributions from pairs whose cosine is negative must be offset by positive contributions from other pairs. If $G$ is connected, representatives satisfy ${\theta }_x\in (-\pi \mathrm{/}2,\pi \mathrm{/}2)$, and ${\rho }_1=n^{-1}{\sum }_x{e}^{i{\theta }_x}$ is real and nonnegative, the half-circle lemma gives ${\theta }_x=0$ for every vertex.

These estimates illustrate the article's qualitative explanation: spurious stable states require, in a suitable sense, more connections between similar phases than between disparate phases, while mixing constrains such imbalances for sufficiently large vertex sets. Together with stability conditions, expansion can rule out suitably well-spread states; the half-circle lemma handles a concentrated extreme. The article uses an amplification argument to bridge intermediate distributions. The phrases “sufficiently large”, “suitably well-spread” and “more connections” here describe the method, not separate quantitative hypotheses or an additional theorem.

Adjacency, degrees, graph Laplacian, and spectral notation

Finite phase tori, local lifts and the flat metric

Phasors, trigonometric identities and periodic derivatives

Equilibria, stable states, synchronized states, and spurious minima

Adjacency spectral expander — Definition 1.3

A bilinear centered-adjacency estimate without regularity

Second-order necessary conditions for stable states

Half-circle lemma — Lemma 2.9

The Axiom of Countable Choice (AC_ω)

The qualitative explanation and amplification overview are attributed to Expander graphs are globally synchronizing, PDF pages 4–5 and 19. The exact consequences proved here use the linked mathematical suppliers; the overview itself is not presented as a proof of a quantitative synchronization theorem.