Expander Graphs and Constraint Graphs

The row sums give $M\mathbf{1}=\mathbf{1}$; symmetry gives $⟨Mf,\mathbf{1}⟩=⟨f,\mathbf{1}⟩$. The real spectral theorem applies since $M$ is a symmetric endomorphism of a finite-dimensional real inner product space. If $Mf=\mu f$ and $\mathrm{\mid }f(v)\mathrm{\mid }$ is maximal and nonzero, then $\mathrm{\mid }\mu \mathrm{\mid }\mathrm{\mid }f(v)\mathrm{\mid }\le {\sum }_u{M}_{vu}\mathrm{\mid }f(u)\mathrm{\mid }\le \mathrm{\mid }f(v)\mathrm{\mid }$, proving the interval bound.

Expansion of the squares gives $⟨f,(I-M)f⟩=(2nd{)}^{-1}{\sum }_{u,v}{A}_{uv}(f(u)-f(v){)}^2$. Its zero vectors are exactly functions constant on each connected component. Thus the eigenspace for eigenvalue one has dimension the component count; the spectral theorem identifies this with multiplicity.

Similarly $⟨f,(I+M)f⟩=(2nd{)}^{-1}{\sum }_{u,v}{A}_{uv}(f(u)+f(v){)}^2$. For a nonzero $-1$ eigenvector all positive slots force $f(v)=-f(u)$. Connectivity propagates one nonzero absolute value to every vertex, excludes loops, and partitions the vertices by sign. Conversely on such a bipartition the vector taking values $+1,-1$ has $Mf=-f$. At $n=1$ positive degree forces loops and $M=[1]$, so no $-1$ eigenvalue occurs and the mean-zero space is zero.

Set $s=\mathrm{\mid }S\mathrm{\mid }\mathrm{/}n$, $t=\mathrm{\mid }T\mathrm{\mid }\mathrm{/}n$, $f={\mathbf{1}}_S-s\mathbf{1}$ and $g={\mathbf{1}}_T-t\mathbf{1}$. Both are mean zero and have normalized squared norms $s(1-s)$ and $t(1-t)$. Since $M$ preserves constants and their orthogonal complement, $e(S,T)\mathrm{/}(nd)-st=⟨f,Mg⟩$. This counts loops and overlap exactly as specified.

Cauchy–Schwarz and the defining operator bound give $\mathrm{\mid }⟨f,Mg⟩\mathrm{\mid }\le \alpha \sqrt{s(1-s)t(1-t)}$. Multiply by $nd$. Empty or full sets give zero centered vectors and equality; at $n=1$ all sets are of that form. No division by a set size or by $\alpha$ is made.

On the nonzero invariant space ${\mathbf{1}}^{\perp }$, the Rayleigh quotient of $I-M$ is at least $\gamma$. For $0<\mathrm{\mid }S\mathrm{\mid }\le n\mathrm{/}2$, the centered indicator has norm squared $\mathrm{\mid }S\mathrm{\mid }(1-\mathrm{\mid }S\mathrm{\mid }\mathrm{/}n)\mathrm{/}n$ and energy $\mathrm{cut}(S)\mathrm{/}(nd)$. Hence $\gamma \le \mathrm{cut}(S)\mathrm{/}(d\mathrm{\mid }S\mathrm{\mid }(1-\mathrm{\mid }S\mathrm{\mid }\mathrm{/}n))\le 2\mathrm{cut}(S)\mathrm{/}(d\mathrm{\mid }S\mathrm{\mid })$. Minimize over the finite nonempty collection of such sets.

Choose a nonzero mean-zero eigenvector $g$ for ${\mu }_2$. It has both positive and negative entries, so one sign has at most $n\mathrm{/}2$ positive entries. Let $f=\max (g,0)$ for this sign. At a positive coordinate, $Mf\ge Mg$ since $f\ge g$ and $M$ is nonnegative; thus $(I-M)f\le (I-M)g=\gamma g$ there. Multiply by $f$, sum, and use $f=0$ elsewhere to obtain the energy bound. This also works when $\gamma =0$ and when some coordinates of $g$ vanish.

Order coordinates $f_1\ge \cdots \ge f_n\ge 0$ and let $a=\mathrm{\mid }\mathrm{supp}f\mathrm{\mid }\le n\mathrm{/}2$. Put $f_{a+1}=0$. Each difference of squared values telescopes across initial segments, so the middle numerator equals ${\sum }_{i=1}^a(f_i^2-f_{i+1}^2)\mathrm{cut}(\{1,\dots ,i\})$. Each cut is at least $dhi$, and ${\sum }_{i=1}^{a}i(f_i^2-f_{i+1}^2)={\sum }_i{f}_i^2$. For $a=0$ all sums are zero.

Factor $\mathrm{\mid }f(u{)}^2-f(v{)}^2\mathrm{\mid }=\mathrm{\mid }f(u)-f(v)\mathrm{\mid }\mathrm{\mid }f(u)+f(v)\mathrm{\mid }$ and apply Cauchy–Schwarz with weights $A_{uv}$ for $u<v$. The first squared sum is $dE(f)$; the second is at most $2{\sum }_{u<v}{A}_{uv}(f(u{)}^2+f(v{)}^2)\le 2d\mathrm{\parallel }f{\mathrm{\parallel }}_0^2$. Dividing by $d$ proves the upper estimate. Loop terms vanish in the difference sum and only reduce the nonloop degree sum.

Multiplying all normalized inner products by $n$ leaves the preceding lemma's inequalities unchanged; thus its positive-part and indicator estimates have exactly the stated unnormalized form. No division by $E(f)$ or $\mathrm{\parallel }f{\mathrm{\parallel }}_0$ was used above, so zero functions and zero energy are included.

Take the nonzero positive part with $E(f)\le \gamma \mathrm{\parallel }f{\mathrm{\parallel }}_0^2$ and combine it with the sweep estimate. Since $\mathrm{\parallel }f{\mathrm{\parallel }}_0^2>0$, this yields $h\le \sqrt{2\gamma }$. The indicator estimate in the same cited result gives $\gamma \mathrm{/}2\le h$. Zero gap is permitted and forces $h=0$.

For any nonempty eligible $S$, each vertex of ${\mathrm{\partial }}_{V}S$ receives at least one and at most $d$ cut slots. Thus $\mathrm{cut}(S)\mathrm{/}d\le \mathrm{\mid }{\mathrm{\partial }}_{V}S\mathrm{\mid }\le \mathrm{cut}(S)$. The first inequality divided by $\mathrm{\mid }S\mathrm{\mid }$ and minimized gives $h\le h_V$. Apply the second to a set minimizing $h$ to obtain $h_V\le dh$. The eligible collection is nonempty and finite because $n\ge 2$; loops never cross its cuts.

For $S\mathrm{\ne }\mathrm{\varnothing }$, mixing with $S=T$ gives $d\mathrm{\mid }S{\mathrm{\mid }}^2\mathrm{/}n\le \alpha d\mathrm{\mid }S\mathrm{\mid }(1-\mathrm{\mid }S\mathrm{\mid }\mathrm{/}n)$. Cancel the positive $d\mathrm{\mid }S\mathrm{\mid }$ and rearrange. For empty $S$ the bound holds directly. If $\alpha =0$ there is no nonempty independent set. In a loopless graph every color class is independent, so summing their sizes gives the color bound when $\alpha >0$.

Every set of size at most $n\mathrm{/}2$ has at least $h$ times its size in external neighbors, by the edge/vertex comparison. A ball therefore grows by a factor at least $1+h$ until it exceeds $n\mathrm{/}2$. With $R=\lceil \log n\mathrm{/}\log (1+h)\rceil +1$, a ball of radius $R$ must exceed half the graph; otherwise successive growth from its initial single vertex contradicts its size bound. Two such balls intersect, giving distance at most $2R$. Positive $h$ also excludes a separate component of size at most half. For $n=1$ use diameter zero without defining $h$.

Each of the four forward affine maps in the definition is a bijection: subtracting its shear and its optional unit shift gives the listed inverse. Pairing a map with its inverse makes the adjacency symmetric. Exactly eight slots are retained at every vertex, regardless of coincidences.

A slot uses additions, subtraction, doubling, and reduction modulo $m$ of integers with $O(\log (m+2))$ bits. School arithmetic performs these in polynomial bit time. Enumerating the $m^2$ coordinate pairs and eight slots proves the total bound. For $m=1$ there is one vertex and eight loop slots; for $m=2$ repeated destinations remain distinct slots.

For $m>1$, ${\sum }_{j=0}^{m-1}{\omega }^{cj}$ is $m$ if $c=0$ modulo $m$, and otherwise is zero because multiplication by $1-{\omega }^c\mathrm{\ne }0$ telescopes to $1-{\omega }^{cm}=0$. Applying this to each coordinate shows $⟨{\chi }_b,{\chi }_c⟩$ is one for $b=c$ and zero otherwise. At $m=1$ the one character has norm one directly.

There are $m^2$ orthonormal characters in the $m^2$-dimensional function space, hence they form a basis: linear independence follows by taking inner products, and an independent list of that length spans by elementary elimination. Expansion in this basis gives inversion and, on taking its squared norm, Parseval. The zero coefficient is exactly the normalized sum, establishing both directions of the mean-zero criterion.

Substitute $u=Tx+a$ in the defining sum. The exponent becomes $-y\cdot T^{-1}(u-a)=-(T^{-\mathsf{T}}y)\cdot u+y\cdot T^{-1}a$. Bijection of this substitution preserves the sum and its normalization, giving the positive phase in the displayed formula. It covers $a=0$, constant and zero functions, and the singleton torus as well.

The Fourier identities give $g(0)=0$ and the stated norm equality. Since $T_1^{\mathsf{T}}=T_2$, the transform of the first pair of summands in $Kf$ is $(1+{\omega }^{z_1})\widehat{f}(T_2^{-1}z)$; the second pair gives $(1+{\omega }^{z_2})\widehat{f}(T_1^{-1}z)$. The phase uses $T_j^{-1}{e}_j=e_j$.

Parseval's inner-product identity (obtained by expanding both functions in the orthonormal character basis) expresses $⟨f,Kf⟩$ as the coefficient inner product. Apply the triangle inequality and $\mathrm{\mid }1+e^{2i\theta }\mathrm{\mid }=2\mathrm{\mid }\cos \theta \mathrm{\mid }$ to obtain $Q(g)$. The absolute cosines are independent of residue representatives.

The four slots defining $K$ are exactly the forward slots in the Margulis construction, and the other four are their inverses. Inverse permutations are the adjoints of the forward permutation operators under uniform counting, so $A=K+K^{\ast }$. Therefore $⟨f,Af⟩=2\mathrm{Re}⟨f,Kf⟩$, proving the last bound. For the singleton torus every mean-zero function vanishes and all displayed sums are zero.

Represent each coordinate in $[-m\mathrm{/}2,m\mathrm{/}2)$. Define $z\succ u$ when both absolute coordinates of $z$ are at least those of $u$, with one strict. Put $w(z,u)=5\mathrm{/}4$ if $z\succ u$, $4\mathrm{/}5$ if $u\succ z$, and $1$ otherwise; then $w(z,u)w(u,z)=1$. Squaring $\sqrt{w}a-b\mathrm{/}\sqrt{w}$ gives $2ab\le w{a}^2+w^{-1}{b}^2$. Apply this to each term of $Q$ and reindex the inverse-shear terms; a shear leaves its corresponding cosine coordinate fixed. The coefficient at $g(z{)}^2$ is bounded by $c_1(z)[w(z,T_{2}z)+w(z,T_2^{-1}z)]+c_2(z)[w(z,T_{1}z)+w(z,T_1^{-1}z)]$, where $c_j(z)=\mathrm{\mid }\cos (\pi z_j\mathrm{/}m)\mathrm{\mid }$.

Outside the open diamond $\mathrm{\mid }{z}_1\mathrm{\mid }+\mathrm{\mid }{z}_2\mathrm{\mid }<m\mathrm{/}2$, let $a=\pi \mathrm{\mid }{z}_1\mathrm{\mid }\mathrm{/}m$ and $b=\pi \mathrm{\mid }{z}_2\mathrm{\mid }\mathrm{/}m$. They lie in $[0,\pi \mathrm{/}2]$ with $a+b\ge \pi \mathrm{/}2$, so $\cos a+\cos b\le \cos a+\sin a\le \sqrt{2}$. Each weight is at most $5\mathrm{/}4$, giving coefficient at most $5\sqrt{2}\mathrm{/}2<73\mathrm{/}20$. This includes the diamond boundary and the centered-coordinate endpoints.

Inside the diamond and away from zero, sign changes and coordinate interchange permute the four shear neighbors and preserve their absolute-coordinate order. First suppose the absolute coordinates are $a>b>0$ with $a+b<m\mathrm{/}2$. The change $a\mapsto a-2b$ strictly decreases its absolute value. For $a+2b$, the centered absolute value is $\min (a+2b,m-a-2b)>a$, since $m>2a+2b$. For $b+2a$, both $b+2a$ and $m-b-2a$ exceed $b$ by the same strict inequality. For $b-2a$, both $2a-b$ and $m-2a+b$ exceed $b$, the latter since $2a<m$. Thus exactly three neighbors dominate and one is dominated, including when a coordinate wraps. The coefficient is at most $3(4\mathrm{/}5)+5\mathrm{/}4=73\mathrm{/}20$.

If $a=b>0$, then $a<m\mathrm{/}4$. Two neighbors preserve the pair of absolute coordinates, and the other two replace one coordinate by $\mathrm{\mid }3a<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m\mathrm{\mid }>a$, because both $3a$ and $m-3a$ exceed $a$. If $a>0,b=0$, two neighbors fix the point and two change the zero coordinate to a nonzero centered residue of $2a$, since $0<2a<m$. In either case there are two weights $1$ and two weights $4\mathrm{/}5$, giving at most $18\mathrm{/}5<73\mathrm{/}20$. The zero point contributes nothing because $g(0)=0$; this also handles $m=1$.

Every point is covered by the preceding cases. Summing the coefficient bounds proves the claim for $Q$. The Fourier reduction gives $\mathrm{\mid }⟨f,Af⟩\mathrm{\mid }\le 2Q(\mathrm{\mid }\widehat{f}\mathrm{\mid })$ and Parseval gives $\sum \mathrm{\mid }\widehat{f}{\mathrm{\mid }}^2=\mathrm{\parallel }f{\mathrm{\parallel }}^2$, proving the stated consequence.

The diamond bound and its Fourier consequence give $\mathrm{\mid }⟨f,Af⟩\mathrm{\mid }\le (73\mathrm{/}10)\mathrm{\parallel }f{\mathrm{\parallel }}^2$ for every real mean-zero $f$. Divide by the degree eight to get $\mathrm{\mid }⟨f,Mf⟩\mathrm{\mid }\le (73\mathrm{/}80)\mathrm{\parallel }f{\mathrm{\parallel }}^2$.

The mean-zero subspace is invariant and $M$ is real symmetric. In its orthonormal eigenbasis the preceding bound applied to each eigenvector gives $\mathrm{\mid }\mu \mathrm{\mid }\le 73\mathrm{/}80$, so the operator norm has that bound. This controls negative as well as positive eigenvalues; in particular $1-{\mu }_2\ge 7\mathrm{/}80$. For $m=1$ use the zero-space norm convention directly.

For $N\ge 2$ put $m=\lceil \sqrt{N}\rceil$. The Margulis graph has algebraic gap at least $7\mathrm{/}80$, so Cheeger's lower bound gives unnormalized cut ratio at least $8(7\mathrm{/}80)\mathrm{/}2=7\mathrm{/}20$. Partition its $m^2$ vertices, in fixed lexicographic order, into $N$ nonempty consecutive fibers of size at most four. Such a partition exists since $N\le m^2\le 4N$, by allocating one vertex per fiber and distributing the remainder up to the capacity four.

Sum adjacency entries across fibers to form the quotient, retaining internal slots on its diagonal. Every row has sum at most $32$; pad its diagonal to row sum $32$. For a quotient cut, the two lifts each have at least as many vertices as their respective sets of fibers. The old cut lower bound therefore yields at least $(7\mathrm{/}20)\min (\mathrm{\mid }S\mathrm{\mid },N-\mathrm{\mid }S\mathrm{\mid })$ crossing slots. Padding changes no cut, so the degree-$32$ graph has normalized $h\ge 7\mathrm{/}640$.

Cheeger's other direction yields algebraic gap at least $h^2\mathrm{/}2\ge 49\mathrm{/}819200$. Add $32$ diagonal slots at each vertex. The normalized matrix becomes $(I+M)\mathrm{/}2$, all its eigenvalues lie in $[0,1]$, and its nontrivial norm is at most $1-49\mathrm{/}1638400$. Double all slots, giving degree $128$ with even diagonal and unchanged normalized matrix. Cuts double, giving the claimed $7\mathrm{/}10$ unnormalized ratio.