Angle and mass sequences in the amplification argument

PDF p. 22: Section 4 opening; Figure 2

Assume countable choice. Let $G=(V,E)$ be a finite connected undirected graph, possibly with self-loops, with nonempty vertex set and $n=\mathrm{\mid }V\mathrm{\mid }$. Connected means that every two vertices are joined by a finite edge path. Let $\theta$ be a stable state, meaning a local minimum on the phase torus $T_V={\mathbb{R}}^V\mathrm{/}(2\pi \mathbb{Z}{)}^V$ of the graph energy ${\mathcal{E}}_G(\theta )=\frac{1}{2}{\sum }_{x,y\in V}{A}_{x,y}(1-\cos ({\theta }_x-{\theta }_y))$, where $A$ is the binary adjacency matrix. Suppose the state is not fully synchronized, meaning that its coordinates are not all equal modulo $2\pi$, and that its first order parameter ${\rho }_1=n^{-1}{\sum }_{x\in V}{e}^{i{\theta }_x}$ is real and nonnegative. Use the unique representatives ${\theta }_x\in (-\pi ,\pi ]$.

For $0\le \psi \le \pi$, write ${\mathcal{C}}_{\psi }=\{x\in V:\mathrm{\mid }{\theta }_x\mathrm{\mid }\ge \psi \}$ for the phase tail set. Set ${\beta }_0=\pi \mathrm{/}2$ and $c_0=\mathrm{\mid }{\mathcal{C}}_{\pi \mathrm{/}2}\mathrm{\mid }$. An amplification sequence of length $M$, where $M$ is a nonnegative integer, consists of real angles ${\beta }_0,\dots ,{\beta }_M$ and real mass lower bounds $c_0,\dots ,c_M$ satisfying $\pi \mathrm{/}2={\beta }_0>{\beta }_1>\cdots >{\beta }_M\ge 0$, $c_0<c_1<\cdots <c_M$, and $\mathrm{\mid }{\mathcal{C}}_{{\beta }_s}\mathrm{\mid }\ge c_s$ for every $0\le s\le M$. When $M=0$, the strict chains impose no additional comparisons. Set ${\beta }_{-1}=\pi$, $c_{-1}=0$, ${\beta }_{M+1}=0$, and $c_{M+1}=n$ as endpoint conventions.

Given: The graph and normalized nonsynchronized stable state in the definition.

Goal: Justify the starting mass, endpoint bounds and the sequence terminology.

1.1 Since $V$ is finite and nonempty, [F4] with $k=1$ gives $\mathrm{\mid }{\rho }_1\mathrm{\mid }\le 1$. The assumed real nonnegativity therefore gives ${\rho }_1=\mathrm{\mid }{\rho }_1\mathrm{\mid }\in [0,1]$. If ${\mathcal{C}}_{\pi \mathrm{/}2}$ were empty, [F1] would put every representative in $(-\pi \mathrm{/}2,\pi \mathrm{/}2)$. All hypotheses of [F2] would then hold, so the half-circle lemma would make every representative zero, contradicting nonsynchronization. Thus $c_0=\mathrm{\mid }{\mathcal{C}}_{\pi \mathrm{/}2}\mathrm{\mid }\ge 1$. [F1, F2, F3, F4, given]

2.1 The endpoint bounds hold: $\mathrm{\mid }{\mathcal{C}}_{\pi }\mathrm{\mid }\ge 0=c_{-1}$, while [F1] gives ${\mathcal{C}}_0=V$, so $\mathrm{\mid }{\mathcal{C}}_0\mathrm{\mid }=n=c_{M+1}$. In particular, the one-term choice $M=0$ is an amplification sequence; longer sequences are specified by the displayed conditions and are not asserted to exist here. The endpoint angles are weakly ordered with the internal angles, and endpoint mass bounds need not be strictly larger than their neighbors. [F1, step 1.1, algebra] ∎

The sequence and endpoint conventions are attributed to Expander graphs are globally synchronizing, PDF page 22, Section 4 and Figure 2. The justification uses the declared mathematical suppliers.

The sequence and endpoint conventions are attributed to Expander graphs are globally synchronizing, PDF page 22, Section 4 and Figure 2. The justification uses the declared mathematical suppliers.