Expander size adjustment and laziness

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.

Symmetry and even diagonal allow explicit reverse pairing: match opposite off-diagonal slots, and pair diagonal slots in order. At least the added loops remain at every vertex. Integer square-root search, fiber allocation, summation, and padding operate on $O(N)$ slots with polynomial-length labels, in polynomial bit time. For $N=1$ output $128$ loop slots; its mean-zero norm is zero and all cut assertions are vacuous.