Dependencies

\(\hat A\) is the transition matrix of the random walk; it is symmetric and doubly stochastic; its eigenvalues are \(\hat\lambda _i=\lambda _i/d\), so \(\hat\lambda _1=1\) and \(\max (|\hat\lambda _2|,|\hat\lambda _n|)\le \alpha \); \(\hat A^t\) is the \(t\)-step transition matrix; and \(\hat A\mathbf u=\mathbf u\).

Every Cayley graph is vertex transitive.

Every clique of \(H\) lies in some \(S^t\) with \(S\) a maximal clique of \(G\); in particular \(\omega (H)=\omega (G)^t\).

A \((k_{\max },\epsilon )\)-lossless conductor, read as a bipartite graph with \(N=2^n\), \(M=2^m\), \(D=2^d\), is a \((2^{k_{\max }},\epsilon )\)-lossless expander.

\(c_2(Q_r)=\sqrt r\).

If \(\omega (G)\ge \delta _1n\) then \(\omega (H')\ge (\delta _1-2\alpha )^tm\).

If \(\omega (G)\le \delta _2n\) then \(\omega (H')\le (\delta _2+2\alpha )^tm\).

\(E:\{ 0,1\} ^n\times \{ 0,1\} ^{2a}\to \{ 0,1\} ^{n-3a}\) is an \((n-30a,2a,4\epsilon )\)-lossless conductor.

Neighbour queries to \(G_k\) are answerable in logspace.

\(G_k\) is an \((nd^{16k},d^{16},3/4)\)-graph.

\(\lambda _1\ge d\), where \(d=2|E|/n\) is the average degree.

If each element of \(\tilde S\) is a product of \(\le m\) elements of \(S\), then \(K(H,S)\ge K(H,\tilde S)/m\).

The lossless expanders of the conductor chapter give explicit constant-rate codes with \(L(G,d){\gt}0.99k\) for \(d=\Omega (n)\), hence efficient asymptotically good codes.

Decoding to the nearest codeword corrects up to \(\lfloor (\mathrm{dist}(C)-1)/2\rfloor \) bit flips.

\(Z\) is PSD iff \(\sum _{ij}q_{ij}z_{ij}\ge 0\) for every PSD \(Q\).

The \(4\)-point metric with one centre at distance \(1\) and the others at distance \(2\) has no isometric Euclidean embedding.

The largest eigenvalue \(\mu \) of the height-\(k\) tree \(\mathbf{T}_d^{(k)}\) has a unique, nonnegative, spherically symmetric eigenfunction \(g\), with \(g_i\) on level \(i\) satisfying \(\mu g_0=dg_1\), \(\mu g_i=g_{i-1}+(d-1)g_{i+1}\), \(g_{k+1}=0\).

The probability of \(\ge 2\) coincidences is \(O(k^4/n^2)\).

Every \((n,d)\)-graph has \(\lambda \ge \sqrt d\, (1-o_n(1))\).

For almost all high lifts of any \(G\), all new eigenvalues are bounded by \(\rho (\hat G)+o(1)\).

Every \(d\)-regular (Ramanujan) graph has a \(2\)-lift all of whose new eigenvalues lie in \([-2\sqrt{d-1},2\sqrt{d-1}]\).

Whether every negative-type metric embeds into \(\ell _1\) with bounded distortion (refuted by Khot–Vishnoi with an \((\log \log n)^c\) lower bound).

For every \(d\ge 3\) there are arbitrarily large \(d\)-regular Ramanujan graphs.

Given \(y\notin C\), flip any bit \(i\) for which \(|A(y+e_i)|{\lt}|Ay|\) (more violated than satisfied constraints), repeating until a codeword is reached.

Fix a \((d^4,d,1/4)\)-graph \(H\) (it exists by a probabilistic argument and, \(d\) being constant, is found by brute force).

For a bipartite \(G\) (\(n\) left variables, \(m\) right constraints), \(C(G)=\{ x: Ax=0\} \) where \(A\) is the bipartite adjacency matrix (each constraint = mod-2 sum of incident variables).

Replace random \(t\)-tuples by all length-\((t-1)\) walks of an \((n,d,\alpha )\)-graph \(\mathcal G\) on \(V(G)\); then \(m=nd^{t-1}\).

Given \(n\)-vertex \(G\) and \(t=\log n\), \(H\) has vertex set \(V^t\); two tuples are adjacent iff the union of their coordinates induces a clique in \(G\).

For distinct primes \(p,q\equiv 1\ (4)\), \(X^{p,q}\) is a \((p+1)\)-regular Cayley graph of \(\mathrm{PGL}(2,q)\) with generators the \(p+1\) Jacobi solutions of \(a_0^2+a_1^2+a_2^2+a_3^2=p\).

\(G_m\) has vertices \(\mathbb {Z}_m\times \mathbb {Z}_m\); \((x,y)\) joins \((x\pm y,y)\), \((x\pm (y+1),y)\), \((x,y\pm x)\), \((x,y\pm (x+1))\) (mod \(m\)); \(8\)-regular and very explicit.

On \(V=\mathbb {Z}_n\times \mathbb {Z}_n\), with \(T_1=\left(\begin{smallmatrix} 1 & 2 \\ 0 & 1 \end{smallmatrix}\right)\), \(T_2=\left(\begin{smallmatrix} 1 & 0 \\ 2 & 1 \end{smallmatrix}\right)\), \(e_1,e_2\) the standard basis, join \(v\) to \(T_1v,T_2v,T_1v+e_1,T_2v+e_2\) and the four inverses; an \(8\)-regular graph.

On \(I\times I\) (\(I=[0,1)\)), \(T(x,y)=(x+y,y)\) and \(S(x,y)=(x,x+y)\) (mod \(1\)); neighbours of \((x,y)\) are \(T^{\pm 1},S^{\pm 1}\) of it, a \(4\)-regular structure.

For input \(D=d^{16}\)-regular connected \(G\) (so an \((n,D,\alpha )\)-graph with \(\alpha {\lt}1-\Omega (1/n^2)\)) and a \((d^{16},d,1/2)\)-graph \(H\), set \(G_1=G\), \(G_{i+1}=(G_i\textcircled {z}H)^8\), run for \(k=O(\log n)\) steps.

With \(a=1000\log (1/\epsilon )\), \(d=2a\): \(\langle E_1,C_1\rangle \) an \((n-30a,6a,\epsilon )\)-permutation conductor, \(\langle E_2,C_2\rangle \) a \((14a,0,\epsilon )\)-buffer conductor, \(E_3\) a \((15a,a,\epsilon )\)-lossless conductor.

Symmetrizing a convex planar set about the \(x\)-axis (replacing each vertical slice \([y_1(x),y_2(x)]\) by the centred slice of equal length) preserves area and does not increase the perimeter.

From a permutation conductor \(\langle E_1,C_1\rangle \), a buffer conductor \(\langle E_2,C_2\rangle \), and a lossless conductor \(E_3\), build \(E\) by: \((y_2,z_2)=\langle E_2,C_2\rangle (x_2,r_2)\); \((y_1,z_1)=\langle E_1,C_1\rangle (x_1,y_2)\); \(y_3=E_3(z_1z_2,r_3)\); output \(y_1y_3\).

\(G_1=H^2\), \(G_{n+1}=(G_n)^2\textcircled {z}H\).

For prime \(p\), \(V_p=\mathbb {Z}_p\), \(x\) joins \(x\pm 1\) and \(x^{-1}\) (\(0^{-1}:=0\)); \(3\)-regular, expansion by Selberg’s \(3/16\) theorem, mildly explicit.

Every \((n,d)\)-graph has \(\lambda _2\ge 2\sqrt{d-1}(1-O(1/\log ^2n))\).

An \((n,d,\alpha )\)-graph has \(\chi (G)\ge 1/\alpha \).

Theorem 148 with \(\lambda _1=2d\), \(\rho =2\sqrt{d-1}\) recovers \(O(d^{3/4})\).

For \(\delta \le 1/2\) there are codes of normalized distance \(\delta \) and rate \(\ge 1-H(\delta )\).

An independent set in an \((n,d,\alpha )\)-graph has \(\le \alpha n\) vertices.

\(\lambda _2(G)\ge \mu \), the top eigenvalue of \(\mathbf{T}_d^{(k)}\).

For large \(d\), the groups \(H_1=A_d\), \(H_{i+1}=H_i^d\rtimes A_d\) admit generating sets \(U_i\) with \(\lambda (H_i,U_i)\le 1/2\) and \(|U_i|\) independent of \(i\).

A code of relative distance \(\delta \) has rate \(\le 1-H(\delta /2)\).

\(A_\rho =\tfrac 1{|S|}\sum _{s\in S}\rho (s)\).

The adjacency matrix \(A=A(G)\) has \((u,v)\) entry the number of edges between \(u,v\). It is real symmetric with eigenvalues \(\lambda _1\ge \dots \ge \lambda _n\) (the spectrum) and orthonormal eigenbasis \(v_1,\dots ,v_n\).

\(v(n,r)=\sum _{i=0}^r\binom ni\).

\(H(\delta )=-\delta \log \delta -(1-\delta )\log (1-\delta )\); \(\tfrac 1n\log \binom n{\delta n}\to H(\delta )\).

\(\mathcal L\in \mathbf{BPP}\) if a randomized polynomial-time \(A\) using \(k\) bits errs (on every \(x\)) with probability \(\le \beta \le \tfrac 1{10}\).

\(c_2(X,d)\) is the least distortion of an embedding of \((X,d)\) into Euclidean space (achievable with \(n\le |X|\)).

\(c_2(G)=c_2(V(G),d_G)\) for the shortest-path metric.

\(C_k=\binom {2k}k/(k+1)\), counting balanced bracket sequences; \(C_k=\Theta (4^k k^{-3/2})\).

For a group \(H\) and symmetric \(S\subseteq H\), \(C(H,S)\) has vertex set \(H\) and edge \((g,gs)\) for \(s\in S\); it is \(|S|\)-regular and connected iff \(S\) generates \(H\).

A character of \(H\) is a homomorphism \(\chi :H\to \mathbb {C}^*\). For \(H=\mathbb {Z}_n^2\), \(\chi _b(a)=\omega ^{a_1b_1+a_2b_2}\) with \(\omega =e^{2\pi i/n}\).

\(h(M)=\inf _A\mu _{n-1}(\partial A)/\min (\mu _n(A),\mu _n(M\setminus A))\).

A clique is a set of pairwise-adjacent vertices; \(\omega (G)\) is the maximum clique size.

For a code \(C\subseteq \{ 0,1\} ^n\), the rate and (normalized) distance are \(R=\frac{\log _2|C|}{n}\) and \(\delta =\frac{\min _{c_1\neq c_2\in C}d_H(c_1,c_2)}{n}\).

Exposing a good word’s walk step by step, a step is free if the image was undetermined; a coincidence is a free step landing on a previously visited vertex. Each \(\Pr [C_i\mid \text{history}]\le 2k/(n-2k)\).

\(E:\{ 0,1\} ^n\times \{ 0,1\} ^d\to \{ 0,1\} ^m\) is a \((k_{\max },a,\epsilon )\)-conductor if for every \(k\le k_{\max }\) and every \(k\)-source \(X\), \(E(X,U_d)\) is a \((k+a,\epsilon )\)-source.

\(E\) is \((a,\epsilon )\)-extracting if it is an \((m-a,a,\epsilon )\)-conductor; \((k_{\max },\epsilon )\)-lossless if a \((k_{\max },d,\epsilon )\)-conductor; \(\langle E,C\rangle \) is a buffer conductor if \(E\) is extracting and \(\langle E,C\rangle \) is lossless; a permutation conductor if moreover \(\langle E,C\rangle \) is a permutation.

\(f:V(H)\to V(G)\) is a covering map if it maps each \(\Gamma _H(v)\) bijectively onto \(\Gamma _G(f(v))\); then \(H\) is a lift of \(G\).

The cut cone is the convex cone of \(\ell _1\) metrics; its extreme rays are the cut metrics \(d_S(x,y)=\mathbf1[|\{ x,y\} \cap S|=1]\).

Unless stated otherwise \(G=(V,E)\) is undirected, \(d\)-regular, with \(n=|V|\) (self-loops/multi-edges allowed). For \(S,T\subseteq V\), \(E(S,T)=\{ (u,v):u\in S,v\in T,(u,v)\in E\} \) is a set of directed edges; \(\Gamma (S)\) is the neighbourhood of \(S\).

\(\mathbf{T}_d\) is the unique infinite connected acyclic graph with every vertex of degree \(d\) (the universal cover of every \(d\)-regular graph).

\(Q_d\) is the graph on \(\{ 0,1\} ^d\) with edges between vectors of Hamming distance \(1\).

For \(f:X\to (\mathbb {R}^n,\ell _2)\), \(\mathrm{distortion}(f)= \mathrm{expansion}(f)\cdot \mathrm{contraction}(f)\), the product of the largest ratios \(\| f(x)-f(y)\| /d(x,y)\) and \(d(x,y)/\| f(x)-f(y)\| \).

A code is \(C\subseteq \{ 0,1\} ^n\); its distance is \(\mathrm{dist}(C)=\min _{x\neq y\in C}d_H(x,y)\) and its rate is \(\log |C|/n\).

For a cut \(E(T,V\setminus T)\) of \(C(H,S)\), \(\epsilon _{s,T}\) counts cut edges using generator \(s^{\pm 1}\).

The edge boundary is \(\partial S=E(S,\overline S)\); the expansion ratio is \(h(G)=\min _{|S|\le n/2}\frac{|\partial S|}{|S|}\).

\(\Phi _E(G,k)=\min _{|S|=k}|E(S,\overline S)|\).

For a distribution \(\mathbf p\) on \([n]\): Shannon entropy \(H(\mathbf p)=-\sum _ip_i\log p_i\); Rényi \(2\)-entropy \(H_2(\mathbf p)=-2\log \| \mathbf p\| _2\); min-entropy \(H_\infty (\mathbf p)=-\log \| \mathbf p\| _\infty \).

A sequence \(\{ G_i\} \) of \(d\)-regular graphs of increasing size is a family of expanders if \(h(G_i)\ge \epsilon \) for some \(\epsilon {\gt}0\), all \(i\).

\(\{ G_i\} \) (on \(n_i\) vertices, \(n_{i+1}\le n_i^2\)) is mildly explicit if \(G_j\) is computable in time \(\mathrm{poly}(j)\), and very explicit if the \(k\)-th neighbour of \(v\) in \(G_i\) is computable in time \(\mathrm{poly}(|(i,v,k)|)\).

For connected \(G\), all vertex/edge fibers \(f^{-1}(\cdot )\) have a common size \(n\); such \(H\) is an \(n\)-lift.

\(\hat f(x)=\sum _b\overline{f(b)}\, \omega ^{b_1x_1+b_2x_2}\).

A family \(C_n\) is asymptotically good if \(\mathrm{dist}(C){\gt}\delta n\) and rate \({\gt}r\) for fixed \(\delta ,r{\gt}0\), and efficient if encoding/decoding (up to \(\delta n/2\) errors) is polynomial-time.

For \(f:V\to \mathbb {R}\), the gradient is \(fK\) (indexed by \(E\)), with \((fK)_e=f_u-f_v\) for \(e=(u,v)\). For \(g:E\to \mathbb {R}\), the divergence is \(Kg\).

\(G^k\) has an edge for every length-\(k\) walk of \(G\); if \(G\) is an \((n,d,\alpha )\)-graph then \(G^k\) is an \((n,d^k,\alpha ^k)\)-graph.

\(F_p[H]\) is the group ring of \(H\) over \(F_p\); the construction sets \(H_{i+1}=F_{p_i}[H_i]\rtimes H_i\).

For words \(u,v\in \Sigma ^n\) over an alphabet \(\Sigma \), the Hamming distance \(d_H(u,v)\) is the number of coordinates \(i\) with \(u_i\neq v_i\).

A hypergraph \(H=(V,E)\) has \(E\) a family of subsets of \(V\); it is \(r\)-uniform if every edge has size \(r\) (graphs are \(2\)-uniform).

Fix an orientation of \(E\). The \(V\times E\) matrix \(K\) has \(K_{u,e}=+1\) if \(e\) leaves \(u\), \(-1\) if \(e\) enters \(u\), else \(0\).

A representation with no nontrivial invariant subspace.

\(G\) is Ramanujan if \(\lambda (G)\le \rho (\hat G)\) (coincides with the regular definition when \(\hat G=\mathbf{T}_d\)).

A \(k\)-source is a distribution with min-entropy \(\ge k\); a \((k,\epsilon )\)-source is \(\epsilon \)-close in \(\ell _1\) to a \(k\)-source.

\(K(H,S)=\min _{v\perp \mathbf1}\max _{h\in S}\tfrac {\| r(h)v-v\| ^2}{\| v\| ^2}\), equivalently the minimum over nontrivial irreducibles.

\(\lambda (H,S)=\lambda (C(H,S))\) and \(g(H,S)=1-\lambda _2(H,S)\).

Set \(\lambda (G)=\max (|\lambda _2|,|\lambda _n|)\). An \(n\)-vertex \(d\)-regular graph is an \((n,d)\)-graph; it is an \((n,d,\alpha )\)-graph if \(\lambda (G)\le \alpha d\). The spectral gap is \(d-\lambda _2\).

\(L=L_G=KK^\top \), with \(L_{u,u}=\deg (u)\) and \(L_{u,v}=-1\) for \((u,v)\in E\).

For a \(k\)-left-regular bipartite \(G\), \(L(G,d)=\min _{0{\lt}|S|\le d}|\Gamma (S)|/|S|\).

A linear code is a subspace \(C\subseteq \mathbb {F}_2^n\).

\(L_n\) is a \(K_n\) glued to a path \(P_{n+1}\) at a vertex; it has average degree \(\Theta (n)\) but \(\lambda (L_n)\le 2\) (showing Alon–Boppana fails for irregular graphs).

A left-\(D\)-regular bipartite \(G=(V_L,V_R;E)\), \(|V_L|=N\), \(|V_R|=M\), is a \((K_{\max },\epsilon )\)-lossless expander if every \(K\le K_{\max }\) left vertices have \(\ge (1-\epsilon )DK\) neighbours.

An \(\ell _2\) (\(\ell _1\)) metric is one isometric to a finite subset of \((\mathbb {R}^n,\ell _2)\) (resp. \(\ell _1\)).

A bipartite graph \(G=(L,R,E)\) with \(|L|=n\), \(|R|=m\), every left vertex of degree \(d\), and neighbourhood map \(\Gamma \), is an \((n,m;d)\)-magical graph if: (1) \(|\Gamma (S)|\ge \tfrac {5d}8|S|\) for \(|S|\le \tfrac n{10d}\); and (2) \(|\Gamma (S)|\ge |S|\) for \(\tfrac n{10d}{\lt}|S|\le \tfrac n2\).

A set \(X\) with \(d:X\times X\to \mathbb {R}^+\) symmetric, vanishing only on the diagonal, and satisfying the triangle inequality.

Ship \(\delta \) units between every pair under unit edge capacities; \(\delta _{\max } (G)\) is the maximum feasible \(\delta \) (a linear program).

\(\mathcal L_n(G)\): \(V(H)=V(G)\times [n]\), and each edge \(e\in E(G)\) carries a permutation \(\pi _e\in S_n\), with fiber edges \(((u,i),(v,\pi _e(i)))\).

\((X,d)\) is of negative type if \(\sqrt d\) is an \(\ell _2\) metric; every \(\ell _1\) metric is of negative type.

For \(d\)-regular \(G\), \(\hat A=\tfrac 1d A\). The uniform vector is \(\mathbf u=(1,\dots ,1)/n\).

If \(h\) is an eigenfunction of \(G\) with eigenvalue \(\lambda \) then \(h\circ f\) is one of \(H\) (an old eigenvalue); the remaining eigenvalues of \(H\) are new.

Choose \(d\) independent uniform permutations \(\pi _1,\dots ,\pi _d\in S_n\) and add edges \((v,\pi _i(v))\); this is contiguous with the uniform \((n,2d)\)-model.

For \(B\subseteq V\), \(P=P_B\) is the diagonal \(0/1\) matrix with \(P_{ii}=1\) iff \(i\in B\).

A \(d\)-regular \(G\) is Ramanujan if \(\lambda (G)\le 2\sqrt{d-1}\).

\(G(n,p)\) is the Erdős–Rényi model (each edge independently with probability \(p\)). The random \((n,d)\)-graph model samples \(d\)-regular graphs (via the configuration/permutation model).

A random walk on \(G\) is the Markov chain \((X_0,X_1,\dots )\) with \(X_0\) drawn from an initial distribution and \(X_{i+1}\) uniform among the neighbours of \(X_i\); this induces distributions \(\pi _i\) on \(V\).

On \(V=\mathbb {C}^H\), \([r(h)f](x)=f(xh)\).

For an \((n,m,\alpha )\)-graph \(G\) and an \((m,d,\beta )\)-graph \(H\), \(G\, \textcircled rH\) has vertex set \(V(G)\times [m]\) (each \(G\)-vertex a cloud of \(m\) vertices), with the \(G\)-edges between clouds and \(n\) copies of \(H\) within clouds.

A representation of \(H\) is a homomorphism \(\rho :H\to U(V)\) to the unitary group of a Hermitian space \(V\).

\(\mathcal L\subseteq \{ 0,1\} ^*\) is in \(\mathbf{RP}\) if a randomized polynomial-time \(A\) satisfies: \(x\in \mathcal L\Rightarrow A(x,r)=1\) for all \(r\); \(x\notin \mathcal L\Rightarrow \Pr _r[A(x,r)=1]{\lt}1\) (fixed below \(1/16\)), with \(r\) uniform of length \(k=\mathrm{poly}(|x|)\).

An action of \(H\) on \(X\) is a homomorphism \(\pi :H\to \mathrm{Sym}(X)\); \(\mathrm{Sch}(H,X,S)\) has vertex set \(X\) and edges \((x,\pi (s)x)\). Cayley graphs are the special case \(X=H\).

An action of \(B\) on \(A\) is a homomorphism \(B\to \mathrm{Aut}(A)\); the semidirect product \(A\rtimes B\) has multiplication \((a_1,b_1)(a_2,b_2)=(a_1\phi _{b_1}(a_2),b_1b_2)\).

A signing \(\tilde A\) of \(A_G\) replaces some \(1\)-entries by \(-1\) (symmetrically); signings correspond bijectively to \(2\)-lifts.

\(\Psi _E(G,k)=\min _{|S|\le k}\frac{|E(S,\overline S)|}{|S|}\), \(\Psi _V(G,k)=\min _{|S|\le k}\frac{|\Gamma (S)\setminus S|}{|S|}\), \(\Psi '_V(G,k)=\min _{|S|\le k}\frac{|\Gamma (S)|}{|S|}\).

\(\rho (H)=\sup \{ |\lambda |:\lambda \in \mathrm{spec}(H)\} \).

\(\rho (\mathbf{T}_d)=2\sqrt{d-1}\).

Let \(G=(V,E)\) and let \(I,O\subseteq V\) each have \(n\) vertices (inputs and outputs). \(G\) is a super concentrator if for every \(k\) and every \(S\subseteq I\), \(T\subseteq O\) with \(|S|=|T|=k\) there are \(k\) vertex-disjoint paths from \(S\) to \(T\).

A matrix \(A\) is super regular if every square submatrix of \(A\) has full rank.

Estimate \(\operatorname {tr}(A^{2k})=\sum _i\lambda _i^{2k}\), the number of closed length-\(2k\) walks; subtracting \(\lambda _1^{2k}\) and taking \(2k\)-th roots bounds the second eigenvalue.

\(t_{2k}\) is the number of closed walks of length \(2k\) from a fixed vertex of \(\mathbf{T}_d\) (the analogous count in any \(d\)-regular graph is \(\ge t_{2k}\)).

\(A_T\) acts on \(\ell _2(V(\mathbf{T}_d))\); \(\lambda \in \mathrm{spec}(A_T)\) iff \(A_T-\lambda I\) is not invertible.

\(\hat G\) is the infinite tree of non-backtracking walks from a fixed vertex; every connected lift of \(G\) is a quotient of \(\hat G\).

\(\Phi _V(G,k)=\min _{|S|=k}|\Gamma (S)\setminus S|\).

A graph is vertex transitive if its automorphism group acts transitively on vertices.

A word reduces by deleting adjacent \(\pi _j\pi _j^{-1}\) pairs. A reduced word is bad if it has the form \(\omega _a\omega _b^j\omega _a^{-1}\) (\(j\ge 2\), or empty), else good.

\(H\wr S_d=H^d\rtimes S_d\) with \(S_d\) permuting coordinates; the construction sets \(H_1=A_d\), \(H_{i+1}=H_i^d\rtimes A_d\).

For bipartite \(H\) (\(d\)-regular, \(s\) per side) and bipartite \(G\) (\(s\)-regular, \(n\) per side), \(G\textcircled {z}H\) is the \(d^2\)-regular bipartite graph on \(sn\) per side defined by dashed–wiggly–dashed steps.

\(G\textcircled {z}H=(V(G)\times [m],E')\) where \(((v,i),(u,j))\in E'\) iff there are \(k,l\) with \((i,k),(l,j)\in E(H)\) and \(e_v^k=e_u^l\) (dashed–wiggly–dashed walks in \(G\, \textcircled rH\)).

\(fLf^\top =\| fK\| ^2=\sum _{(u,v)\in E}(f(u)-f(v))^2\).

A uniform length-\(2k\) word reduces to a bad word with probability \(O(k^2(2/d)^k)\).

For \(d\)-regular \(G\): (i) \(\lambda _1=d\) with eigenvector \(\mathbf1/\sqrt n\); (ii) \(G\) is connected iff \(\lambda _1{\gt}\lambda _2\); (iii) \(G\) is bipartite iff \(\lambda _1=-\lambda _n\).

Order \(f_1\ge \dots \ge f_n\) with \(V^+=\mathrm{supp}(f)\), \(|V^+|\le n/2\). Then \(B_f\ge h(G)\, \| f\| ^2\).

For \(B_f=\sum _{(x,y)\in E}|f_x^2-f_y^2|\) on a \(d\)-regular graph, \(B_f\le \sqrt{2d}\, \| fK\| \, \| f\| \).

Every \(d\)-regular adjacency matrix has a signing \(\tilde A\) with \(x\tilde Ax\le O(\sqrt d\log d\, \| x\| ^2)\) for all \(x\in \{ -1,0,1\} ^V\).

For integers \(1\le k\le n\), \(\binom nk\le (en/k)^k\).

For real vectors, \(|\langle x,y\rangle |\le \| x\| _2\, \| y\| _2\).

If \(Z\sim \mathrm{Binomial}(N,p)\) then for \(0{\lt}\Delta {\lt}1\), \(\Pr [|Z-\mathbb {E}Z|\ge \Delta \mathbb {E}Z]{\lt}2\exp (-Np\Delta ^2/3)\).

If a polynomial-time \(A\) satisfies \(n^{-\epsilon }\le A(G)/\omega (G)\le n^{\epsilon }\) on every graph, then \(\mathbf{NP}\subseteq \mathbf{RP}\).

For any \((X_1,X_2)\), \(\epsilon \), \(a\), there is \((Y_1,Y_2)\) \(\epsilon \)-close to \((X_1,X_2)\) that is a convex combination of two distributions of min-entropy \(\ge H_\infty (X_1,X_2)-\log (1/\epsilon )\), one with \(H_\infty (\hat Y_2\mid \hat Y_1=x)\ge a\) throughout, the other with it \({\lt}a\) throughout.

\(g(H,S)=\min _{v\perp \mathbf1}\tfrac 1{2|S|}\sum _{h\in S}\tfrac {\| r(h)v-v\| ^2}{\| v\| ^2}\).

The distance of a linear code equals the minimum weight of a nonzero codeword.

The normalized adjacency matrix of \(C(H,S)\) is \(A_r\); its eigenvalues are the union, over irreducibles \(\rho \), of the eigenvalues of \(A_\rho \), and conversely.

For a \(d\)-regular graph on \(n\) vertices with \(\lambda =\lambda (G)\) and all \(S,T\subseteq V\), \(\bigl|\, |E(S,T)|-\frac{d|S||T|}n\bigr|\le \lambda \sqrt{|S||T|}\).

For \(k\)-regular \(G\) of even order \(n\), the graph \(H\) joining vertices at \(G\)-distance \(\ge \lfloor \log _kn\rfloor \) has a perfect matching.

For a concave \(\varphi \) and a random variable \(X\), \(\mathbb {E}[\varphi (X)]\le \varphi (\mathbb {E}X)\).

For a probability vector \(\mathbf p\) in an \((n,d,\alpha )\)-graph, \(\| \hat A\mathbf p-\mathbf u\| _2\le \alpha \| \mathbf p-\mathbf u\| _2\le \alpha \).

For \(d\)-regular \(G\), \(L=dI-A\); \(\mathrm{spec}(L)\subseteq [0,2d]\), with smallest eigenvalue \(0\) and smallest positive eigenvalue \(d-\lambda _2\), the spectral gap.

There is \(n_0\) so that for every \(d\ge 32\), \(n\ge n_0\), \(m\ge 3n/4\), an \((n,m;d)\)-magical graph exists.

In an \((n,3n/4;d)\)-magical graph, \(|\Gamma (S)|\ge |S|\) for every \(S\subseteq L\) with \(|S|\le \tfrac n2\), so by Hall’s theorem there is a matching saturating any such \(S\).

For a nonnegative random variable \(X\) and \(a{\gt}0\), \(\Pr [X\ge a]\le \mathbb {E}X/a\).

If \(\bigl|\, |E(S,T)|-\tfrac {d|S||T|}n\bigr|\le \rho \sqrt{|S||T|}\) for all disjoint \(S,T\), then \(\lambda \le O(\rho (1+\log (d/\rho )))\), and this is tight.

For a good word of length \(s\le 2k\), the probability of exactly one coincidence and ending at vertex \(1\) is \(\le 1/(n-2k)\).

An irreducible nonnegative matrix has a positive real eigenvalue equal to its spectral radius, with a positive eigenvector of multiplicity one.

\(\| P\hat A P\mathbf v\| _2\le (\beta +\alpha )\| \mathbf v\| _2\) for all \(\mathbf v\), where \(\beta =|B|/n\).

For a symmetric \(A\) with eigenvalues \(\lambda _1\ge \dots \ge \lambda _n\) and top eigenvector \(v_1\), \(\lambda _1=\max _x\frac{x^\top Ax}{\| x\| ^2}\) and \(\lambda _2=\max _{x\perp v_1}\frac{x^\top Ax}{\| x\| ^2}\).

A real symmetric matrix has real eigenvalues and an orthonormal eigenbasis.

For \(f\) built from a nonincreasing \(g\) supported on the two distance-balls around far vertices \(s,t\): \((Af)_v\ge \mu f_v\) on the \(s\)-side and \((Af)_v\le \mu f_v\) on the \(t\)-side.

For the walk transition matrix \(P\) with \(\rho =\max (|\mu _2|,|\mu _n|)\), \(\mathbb {E}[\rho ]\le (\mathbb {E}[\operatorname {tr}(P^{2k})]-1)^{1/2k}\) and \(\mathbb {E}[\operatorname {tr}(P^{2k})]=n\Pr [\omega (1)=1]\), where \(\omega \) is a uniform word of length \(2k\) over \(\{ \pi _i^{\pm 1}\} \).

\(t_{2k}\ge C_k(d-1)^k=\Theta ((2\sqrt{d-1})^{2k}k^{-3/2})\).

\(t_{2s+1}=0\) and \(t_{2s}=\sum _{j=1}^s\binom {2s-j}s\frac j{2s-j}d^j(d-1)^{s-j}\).

For finite events \(A_1,\dots ,A_m\), \(\Pr [\bigcup _i A_i]\le \sum _i\Pr [A_i]\).

In an \((n,3n/4;d)\)-magical graph, every nonempty \(S\subseteq L\) with \(|S|\le \tfrac n{10d}\) has a vertex \(u\in R\) with \(|\Gamma (u)\cap S|=1\).

Let \((B,t)\) be the event that a uniformly-started length-\(t\) walk stays in \(B\). Then \(\Pr [(B,t)]=\| (P\hat A)^tP\mathbf u\| _1\).

\(\varphi (\alpha ,\beta )\le \alpha +\beta +\beta ^2\) for \(G\textcircled {z}H\).

For \(\delta {\gt}0\) and large \(d\), explicitly construct \((n,d)\)-graphs with \(\Psi _V(G,\epsilon n)\ge d-2-\delta \).

Of all simple closed plane curves of a given length, which encloses the greatest area? (Answer: the circle.)

Computing \(h(G)\) is co-\(\mathbf{NP}\)-hard; up to a constant it reduces to the sparsest cut \(\min _S|E(S,\overline S)|/(|S|(n-|S|))\).

Let \(A\) be an \(n\times n\) matrix over a field \(\mathcal F\). What is the least number of gates in an arithmetic circuit computing \(x\mapsto Ax\), where each gate has two inputs \(x,y\), two field coefficients \(a,b\), and output \(ax+by\)?

Alice sends a \(k\)-bit message to Bob over a channel that may flip a fraction \(p\) of bits. What is the smallest \(n\) so that Bob can always recover the message?

Do there exist arbitrarily large codes \(\{ C_k\} \), \(|C_k|=2^k\), with \(R(C_k)\ge R_0\) and \(\delta (C_k)\ge \delta _0\) for absolute constants \(R_0,\delta _0{\gt}0\), that are explicit and efficiently encodable/decodable?

Given a one-sided-error randomized membership algorithm for \(\mathcal L\), how many random bits suffice to reduce the error to \(\le \epsilon \) on every input?

The new eigenvalues of the \(2\)-lift encoded by \(\tilde A\) are exactly the eigenvalues of \(\tilde A\).

If \(H\) is abelian and \(\lambda (H,S)\le 1/2\) then \(|S|\ge \tfrac 13\log |H|\).

For abelian \(H\), \((\chi (h))_{h}\) is an eigenvector of the normalized adjacency matrix of \(C(H,S)\) with eigenvalue \(\tfrac 1{|S|}\sum _{s\in S}\chi (s)\).

A finite abelian \(H\) has \(|H|\) characters forming an orthonormal basis; every \(f\) has a unique Fourier expansion \(f=\sum _x\hat f(x)\chi _x\).

\(H_\infty (\mathbf p)\le H_2(\mathbf p)\le 2H_\infty (\mathbf p)\).

(a) \(\sum _af(a)=0\iff \hat f(0)=0\); (b) \(\langle f,g\rangle =\frac1{n^2}\langle \hat f,\hat g\rangle \) (Parseval); (d) inversion; (e) under an affine change \(g(x)= f(Ax+b)\), \(\hat g(y)=\omega ^{-\langle A^{-1}b,y\rangle }\hat f((A^{-1})^\top y)\).

\(K(H,S)/(2|S|){\lt}g(H,S){\lt}K(H,S)/2\).

\(L_G\) is positive semidefinite; its smallest eigenvalue is \(0\) with constant eigenfunction.

Every unitary representation decomposes orthogonally into irreducibles, uniquely up to isomorphism.

A new eigenfunction \(\psi \) satisfies \(\sum _{f(x)=v}\psi (x)=0\) for every \(v\).

There is a partial order so that inside the diamond, for each \(z\), among \(T_1^{\pm 1}z,T_2^{\pm 1}z\) either three exceed \(z\) and one is below, or two exceed \(z\) and two are incomparable.

Every irreducible representation of \(H\) appears in the regular representation.

Every connected component \(Z\) of \(\mathrm{Sch}(H,X,S)\) has \(\lambda (Z)\le \lambda (H,S)\).

\(G_n\) is a \((d^{4n},d^2,1/2)\)-graph for all \(n\).

Undirected \(s\)-\(t\) connectivity is solvable by a polynomial-length random walk in randomized logspace (\(SL\subseteq RL\)).

For \(B\) of density \(\beta \) in an \((n,d,\alpha )\)-graph, \(\Pr [(B,t)]\le (\beta +\alpha )^t\).

If \(\beta {\gt}6\alpha \) then \(\beta (\beta +2\alpha )^t\ge \Pr [(B,t)]\ge \beta (\beta -2\alpha )^t\).

Every \((n,d)\)-graph has \(\lambda \ge 2\sqrt{d-1}-o_n(1)\).

There is \(c\) such that every \((n,d)\)-graph of diameter \(\Delta \) has \(\lambda _2\ge 2\sqrt{d-1}(1-c/\Delta ^2)\).

A random \(S\subseteq H\) of size \(100\log |H|\) has \(\lambda (C(H,S)){\lt}1/2\) with probability \(\ge 0.5\).

If \(B\) acts on \(A\) so that the generating set \(S_A\) is a single \(B\)-orbit of \(x\), then \(S=\{ (1,s):s\in S_B\} \cup \{ (x,1)\} \) generates \(A\rtimes B\) and \(C(A\rtimes B,S)\) is the replacement product of \(C(A,S_A)\) and \(C(B,S_B)\).

For every \(d\ge 3\) there is a mildly explicit family of \((n,d,\alpha )\)-graphs with \(\alpha d=O(\sqrt{d\log ^3d})\).

Every \(n\)-point metric embeds into Euclidean space with distortion \(O(\log n)\).

Almost every \(2d\)-regular graph has \(\lambda (G)=O(d^{3/4})\).

\(c_2(X,d)\) is computable in polynomial time by semidefinite programming.

\(c_2(X,d)=\max _{P\in \mathrm{PSD},\, P\mathbf1=0} \sqrt{\frac{\sum _{p_{ij}{\gt}0}p_{ij}d(x_i,x_j)^2}{-\sum _{p_{ij}{\lt}0}p_{ij}d(x_i,x_j)^2}}\).

For a \(d\)-regular graph, \(\frac{d-\lambda _2}2\le h(G)\le \sqrt{2d(d-\lambda _2)}\).

For a \(d\)-regular graph, \(h(G)\ge \tfrac {d-\lambda _2}2\), equivalently \(\lambda _2\ge d-2h(G)\).

For a \(d\)-regular graph, \(h(G)\le \sqrt{2d(d-\lambda _2)}\).

The smallest positive Laplacian eigenvalue satisfies \(\lambda \ge h(M)^2/4\).

There is \(\epsilon {\gt}0\) such that a polynomial-time \(A\) with \(n^{-\epsilon }\le A(G)/\omega (G)\le n^{\epsilon }\) on every graph implies \(\mathbf{NP}=\mathbf{P}\).

\(\Phi _E(Q_d,k)\ge k(d-\log _2k)\), with equality when \(k=2^\ell \) (a subcube).

If \(k=\sum _{i\le r}\binom di\) then \(\Phi _V(Q_d,k)=\binom d{r+1}\) (Hamming balls).

An \((n,d,\alpha )\)-graph has diameter \(O(\log n)\).

A graph on \(n\) vertices with minimum degree \(\ge n/2\) has a Hamiltonian cycle.

If \(G\) is an \((n,k)\)-graph with \(\lambda _2\le k-\epsilon \), then \(c_2(G)=\Omega (\log n)\).

There is a group with two bounded generating sets, one giving an expanding Cayley family and the other not.

There are constants \(1{\gt}\delta _1{\gt}\delta _2{\gt}0\) such that it is \(\mathbf{NP}\)-hard to decide whether \(\omega (G)\le \delta _2n\) or \(\omega (G)\ge \delta _1n\).

For almost all high lifts of \(G\) (top eigenvalue \(\lambda _1\), universal cover spectral radius \(\rho \)), all new eigenvalues are \(\le \sqrt{\lambda _1\rho }+o(1)\).

For every \(\epsilon {\gt}0\), a random \((n,d)\)-graph has \(\Pr [\lambda (G)\le 2\sqrt{d-1}+\epsilon ]=1-o_n(1)\).

For a random symmetric \(A\) with independent bounded mean-zero entries (variance \(\sigma ^2\)), w.h.p. all eigenvalues satisfy \(|\lambda _i|{\lt}2\sigma \sqrt n+O(n^{1/3}\log n)\).

There is a (linear) length-\(n\) code of distance \(\ge d\) and size \(\ge 2^n/v(n,d)\).

If a family \(\{ G_i\} \) shares universal cover \(T\) then \(\lambda (G_i)\ge \rho (T)-o(1)\).

Every finite \(2d\)-regular graph is a Schreier graph of some group action.

Let \(G=(L\cup R,E)\) be a bipartite graph. There is a matching saturating \(L\) iff \(|\Gamma (S)|\ge |S|\) for every \(S\subseteq L\).

If the average degree is \(\ge d\) after deleting any radius-\(r\) ball, then \(\lambda (G)\ge 2\sqrt{d-1}(1-c\log r/r)\).

Any \(n\)-point \(\ell _2\) metric embeds into \(O(\log n/\epsilon ^2)\) dimensions with distortion \(\le 1+\epsilon \).

For an \((n,d,\alpha )\)-graph and \(\rho {\gt}0\), \(\Psi '_V(G,\rho n)\ge \frac d2(1-\sqrt{1-4(d-1)/(d^2\alpha ^2)})(1-c\log d/\log (1/\rho ))\).

\(A_d\) has an explicit generating set \(U\) of \(d\)-independent size with \(\lambda (A_d,U){\lt}1/100\).

For \(T\subseteq \{ 0,1\} ^n\) with \(|T|=2^{n-1}\), some coordinate \(j\) has \(\epsilon _{j,T}\ge \Omega (\tfrac {\log n}n2^n)\), and this is tight.

For any distribution \(\mathbf p\) and \(t\ge 1\), \(\| \hat A^t\mathbf p-\mathbf u\| _1\le \sqrt n\, \alpha ^t\).

For any distribution \(\mathbf p\) and \(t\ge 1\), \(\| \hat A^t\mathbf p-\mathbf u\| _2\le \alpha ^t\).

\(\delta _{\max }(G)\le \min _S\frac{|E(S,\overline S)|}{|S|(n-|S|)}\le O(\delta _{\max }(G)\log n)\).

For any \(\epsilon {\gt}0\) and \(M\le N\) there is an explicit family of left \(D\)-regular bipartite \((\Omega (\epsilon M/D),\epsilon )\)-lossless expanders with \(D\le (N/\epsilon M)^c\).

An \((n,3n/4;d)\)-magical graph yields a linear code \(C\subseteq \{ 0,1\} ^n\) with rate \(R\ge \tfrac 14\) and normalized distance \(\delta \ge \tfrac 1{10d}\).

For \(\sum _zf(z)=0\), \(\sum _zf(z)[f(T_1z)+f(T_1z+e_1)+f(T_2z)+f(T_2z+e_2)]\le \tfrac {5\sqrt2}2\sum f^2\).

\(\lambda (G_n)\le 5\sqrt2{\lt}8\) for every \(n\).

For \(F\) with \(F(0,0)=0\), \(\bigl|\sum _z\overline{F(z)}[F(T_2^{-1}z)(1+\omega ^{-z_1})+F(T_1^{-1}z)(1+\omega ^{-z_2})]\bigr| \le \tfrac {5\sqrt2}2\sum |F(z)|^2\).

For nonnegative \(G\) with \(G(0,0)=0\), \(\sum _z2G(z)[G(T_2^{-1}z)|\cos (\pi z_1/n)|+G(T_1^{-1}z)|\cos (\pi z_2/n)|]\le \tfrac {5\sqrt2}2\sum G^2\).

There is \(\epsilon {\gt}0\) such that every measurable \(A\) with \(\mu (A)\le \tfrac 12\) has \(\mu (\Gamma (A)\cup A)\ge (1+\epsilon )\mu (A)\).

It suffices to show: if \(\sum _xf(x)=0\) then \(\sum _{(x,y)\in E}f(x)f(y)\le \tfrac {5\sqrt2}2\sum f^2(x)\).

If \(d\)-regular \(G_n\) have \(o(|V|)\) cycles of each fixed length, their empirical eigenvalue distribution converges to the Kesten–McKay law supported on \([-2\sqrt{d-1},2\sqrt{d-1}]\).

A code of relative distance \(\delta \) has rate \(\le H(1/2-\sqrt{\delta (1-\delta )})\).

If the number of irreducibles of \(H\) of dimension \({\lt}r\) is \({\lt}c^r\), then a constant number of orbits makes \(F_p[H]\) an expander.

There are groups \(H_i=F_{p_{i-1}}[H_{i-1}]\rtimes H_{i-1}\) and generating sets \(U_i\) with \(\lambda (H_n,U_n)\le 1/2\) and \(|U_n|\le \log ^{(n/2)}|H_n|\) (iterated log).

For \(\mathcal L\in \mathbf{RP}\) with bad set of density \(\beta \), the AND over a length-\(t\) walk on a \((2^k,d,\alpha )\)-graph errs with probability \(\le (\beta +\alpha )^t\), using \(k+O(t)\) random bits.

For \(k\)-regular \(G\) and any \(f:V\to \mathbb {R}^n\), \(\mathbb {E}_{u,v}\| f(u)-f(v)\| ^2\le \tfrac k{k-\lambda _2}\mathbb {E}_{(u,v)\in E}\| f(u)-f(v)\| ^2\).

For every prime power \(q=p^k\) there are infinitely many \((q+1)\)-regular Ramanujan graphs.

Undirected \(s\)-\(t\) connectivity is in deterministic logspace, so \(SL=L\).

Writing \(\mathbf p=\mathbf u+\mathbf f\), \(\mathbf f\perp \mathbf u\), \(\mu =\| \mathbf f\| /\| \mathbf p\| \), one has \(H_2(\hat A\mathbf p)\ge H_2(\mathbf p)-\log (1-(1-\alpha ^2)\mu ^2)\).

For \(\mathcal L\in \mathbf{RP}\) with one-sided-error algorithm \(f\) using \(k\) bits, \(n=2^k\), failing on \(B\) with \(|B|\le n/16\): for every \(d\) there is an algorithm evaluating \(f\) exactly \(d\) times, using only the \(k\) random bits, with error \(\le \tfrac 1{10d}\).

If every \(h\in H\) is a commutator, \(U\) is expanding with second eigenvalue \(\le 1/4\), and \(|U|{\lt}d/10^6\), then \(\lambda (H^d,U^{(d)}){\lt}1/2\) for the single \(S_d\)-orbit \(U^{(d)}\).

For every \(d,\epsilon \) there is \(c(\epsilon ,d){\gt}0\) so that every \((n,d)\)-graph has \(\ge cn\) eigenvalues \({\gt}2\sqrt{d-1}-\epsilon \).

Any length-\(n\), distance-\(d\) code has \(|C|\le 2^n/v(n,d/2)\).

If \(L(G,d){\gt}\tfrac 34k\) and \(d_H(y,x)\le d/2\) for a codeword \(x\), then belief-propagation returns \(x\) in a linear number of steps.

If \(L(G,d){\gt}k/2\) then \(\mathrm{dist}(C(G))\ge d\).

There exist super concentrators with \(n\) inputs, \(n\) outputs and \(O(n)\) edges.

For an \((n,d,\alpha )\)-graph and \(\rho {\gt}0\), \(\Psi '_V(G,\rho n)\ge \frac1{\rho (1-\alpha ^2)+\alpha ^2}\).

For \(K\subseteq \{ 0,\dots ,t\} \) and \(B\) of density \(\beta \), \(\Pr [X_i\in B\ \forall i\in K]\le (\beta +\alpha )^{|K|-1}\).

\(\Phi _E(\mathbf{T}_d,k)=k(d-2)+2\) and \(h(\mathbf{T}_d)=d-2\); hence every \((n,d)\)-graph has \(\Phi _E(G,k)\le k(d-2)+2\).

\(\mathrm{spec}(A_T)=[-2\sqrt{d-1},\, 2\sqrt{d-1}]\).

For \(\mathcal L\in \mathbf{BPP}\) with \(\alpha +\beta \le \tfrac 18\), the majority vote over a length-\(t\) walk errs with probability \(O(2^{-t/2})\), using \(k+O(t)\) random bits.

For fixed \(d\ge 3\) and every \(\delta {\gt}0\) there is \(\epsilon {\gt}0\) so that almost every \((n,d)\)-graph has \(\Psi _E(G,\epsilon n),\Psi _V(G,\epsilon n)\ge d-2-\delta \) and \(\Psi '_V(G,\epsilon n)\ge d-1-\delta \) (and \(\ge d-1-\delta \) in the bipartite case).

For sets \(B_0,\dots ,B_t\) of densities \(\beta _i\), \(\Pr [X_i\in B_i\ \forall i]\le \prod _{i=0}^{t-1}(\sqrt{\beta _i\beta _{i+1}}+\alpha )\).

For a random symmetric \(A_n\) with i.i.d. entries (variance \(\sigma ^2\), finite moments), the empirical eigenvalue distribution of \(A_n/(2\sigma \sqrt n)\) converges to the semicircle \(\frac2\pi \int _{-1}^x\sqrt{1-z^2}\, dz\).

If \(G\) is an \((n,m,\alpha )\)-graph and \(H\) an \((m,d,\beta )\)-graph, then \(G\textcircled {z}H\) is an \((nm,d^2,\varphi (\alpha ,\beta ))\)-graph with: (1) \(\varphi {\lt}1\) if \(\alpha ,\beta {\lt}1\); (2) \(\varphi \le \alpha +\beta \); (3) \(\varphi \le 1-(1-\beta ^2)(1-\alpha )/2\).