Adjacency spectral expander — Definition 1.3

PDF p. 6: Definition 1.3; PDF p. 7: Definition 1.3 and continuation

Let $G=(V,E)$ be a finite undirected graph with $n=\mathrm{\mid }V\mathrm{\mid }>0$ vertices and adjacency matrix $A$. Its entries $A_{xy}$ record adjacency, including any diagonal loop entries under the graph convention. Let $J$ be the $V\times V$ all-ones matrix, and let $d^{\ast }$ and $\alpha$ be real parameters. The centered adjacency matrix is ${\mathrm{\Delta }}_A=A-(d^{\ast }\mathrm{/}n)J$. Its operator norm is $\mathrm{\parallel }{\mathrm{\Delta }}_A\mathrm{\parallel }={\sup }_{f\mathrm{\ne }0}\mathrm{\parallel }{\mathrm{\Delta }}_{A}f{\mathrm{\parallel }}_2\mathrm{/}\mathrm{\parallel }f{\mathrm{\parallel }}_2$, where $f\in {\mathbb{C}}^V$ and $\mathrm{\parallel }f{\mathrm{\parallel }}_2=({\sum }_{x\in V}\mathrm{\mid }f(x){\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$.

The graph $G$ is an $(n,d^{\ast },\alpha )$-expander if $\mathrm{\parallel }{\mathrm{\Delta }}_A\mathrm{\parallel }\le \alpha d^{\ast }$, equivalently, if $\mathrm{\parallel }A-(d^{\ast }\mathrm{/}n)J\mathrm{\parallel }\le \alpha d^{\ast }$. The reference parameter $d^{\ast }$ need not be the degree of every vertex; this definition does not require regularity.

Adjacency, degrees, graph Laplacian, and spectral notation

Centered graph matrices and reference degree

Loewner order, Hermitian inner product, and operator norm

The graph notation supplies the finite vertex set and adjacency matrix, with the stated diagonal convention (Adjacency, degrees, graph Laplacian, and spectral notation). Since $n>0$, the centered-matrix definition supplies the uniquely defined matrix ${\mathrm{\Delta }}_A=A-(d^{\ast }\mathrm{/}n)J$ for each real $d^{\ast }$ (Centered graph matrices and reference degree). The operator norm is finite and well defined on this finite-dimensional vertex space (Loewner order, Hermitian inner product, and operator norm). Consequently the displayed inequality is a well-defined predicate, and its two forms agree by substitution. The inequality itself imposes any restrictions needed on the product $\alpha d^{\ast }$; no positivity assumption is needed merely to define the predicate.

The definition is attributed to Expander graphs are globally synchronizing, Definition 1.3. The article's subsequent regular-graph spectral characterization is stated separately.