Two-sided spectral expander — Definition 1.9

PDF p. 8: Definition 1.9

Let $G=(V,E)$ be a finite undirected graph with $n=\mathrm{\mid }V\mathrm{\mid }>0$, adjacency matrix $A$, degree matrix $D$, and Laplacian $L=D-A$, using the graph conventions of Adjacency, degrees, graph Laplacian, and spectral notation. Thus $D_{xx}={\sum }_y{A}_{xy}$, including a diagonal loop entry once. Let $I$ be the identity matrix and $J$ the all-ones matrix. For real parameters $d^{\ast }$, $\alpha$, $c^{-}$, and $c^{+}$, put ${\mathrm{\Delta }}_A=A-(d^{\ast }\mathrm{/}n)J$ and ${\mathrm{\Delta }}_L=L-d^{\ast }I+(d^{\ast }\mathrm{/}n)J$.

The graph is an $(n,d^{\ast },\alpha ,c^{-},c^{+})$-expander if it is an $(n,d^{\ast },\alpha )$-expander, meaning that $\mathrm{\parallel }{\mathrm{\Delta }}_A\mathrm{\parallel }\le \alpha d^{\ast }$, and also satisfies $c^{-}{d}^{\ast }I⪯{\mathrm{\Delta }}_L⪯c^{+}{d}^{\ast }I$. Here $\mathrm{\parallel }\cdot \mathrm{\parallel }$ is the operator norm induced by the standard norm on ${\mathbb{C}}^V$. For Hermitian matrices, $B⪯C$ means that $f^{\ast }(C-B)f\ge 0$ for every $f\in {\mathbb{C}}^V$. The definition does not require $G$ to be regular.

The graph convention supplies real symmetric matrices $A$, $D$, and $L$ of the same size (Adjacency, degrees, graph Laplacian, and spectral notation). Because $n>0$, the centered-matrix construction gives well-defined real symmetric matrices ${\mathrm{\Delta }}_A$ and ${\mathrm{\Delta }}_L$ (Centered graph matrices and reference degree). The operator norm and Loewner order are well defined for these matrices (Loewner order, Hermitian inner product, and operator norm). The first inequality is precisely the previously defined $(n,d^{\ast },\alpha )$-expander predicate (Adjacency spectral expander — Definition 1.3), while the two order inequalities are meaningful predicates on the same vertex space. Their conjunction therefore defines the stated class. No sign restrictions on the real parameters are needed to make this predicate meaningful; the inequalities themselves determine whether a given graph belongs to the class.

The formulation is attributed to Definition 1.9 of Expander graphs are globally synchronizing. The justification above uses the displayed definitions and does not treat the article as proof of its own definition.