Degree reduction by expander incidence clouds

Fix the alphabet $\mathrm{\Sigma }$ of Constraint graph and labeling value, a total ordering of $\mathrm{\Sigma }$ used for plurality tie breaking, and the reverse-paired degree-$128$ expander family $H_r$ with unnormalized edge expansion at least $h_0=7\mathrm{/}10$ for $r\ge 2$ that is used in Constraint graph regularization.

Let $G$ be a binary constraint graph over $\mathrm{\Sigma }$ in the published convention. The degree-reduction map $R_{\mathrm{deg}}$ is the following deterministic construction, which is the published cloud-and-overlay preprocessing read as a map on explicit encodings.

1. If $E(G)=\mathrm{\varnothing }$, output the empty graph over $\mathrm{\Sigma }$, which has value one.
2. Otherwise delete isolated vertices, and replace every vertex $v$ of degree $r$ by a cloud of its $r$ incidence ports, so that each original edge contributes its two distinct ports, a loop contributing two distinct ports at its vertex. Put a copy of $H_r$ inside the cloud, with equality relations on all its edges, and keep one external edge for each original edge, joining its two designated ports and carrying the same relation in the same endpoint order. The result is the cloud graph $G_1$ of Constraint expander overlay; it has degree $129$ and $2\mathrm{\mid }E(G)\mathrm{\mid }$ vertices.
3. On the $2\mathrm{\mid }E(G)\mathrm{\mid }$ ports add a copy of $H_{2\mathrm{\mid }E(G)\mathrm{\mid }}$ with tautological relations and $65$ ordinary tautological loops at every port, i.e. $130$ loop slots, to obtain the registered graph $G_2$. By the published count, $G_2$ is $387$-regular with $2\mathrm{\mid }E(G)\mathrm{\mid }$ vertices and $387\mathrm{\mid }E(G)\mathrm{\mid }$ ordinary edges, its normalized adjacency satisfies $\alpha (G_2)\le {\rho }_2=(259+128{\rho }_0)\mathrm{/}387<1$, and its alphabet is still $\mathrm{\Sigma }$.

The decoding map $D$ sends a labeling $\tau$ of $G_2$ (equivalently of $G_1$, on which it depends only through the ports) to the labeling $D\tau$ of $G$ that assigns to each original vertex the most frequent label among the ports of its cloud, breaking ties by the fixed ordering; deleted isolated vertices receive the first symbol of $\mathrm{\Sigma }$. This is the plurality decoding of Constraint graph regularization.

Every step is a fixed function of the explicit input encoding: listing the $H_r$ adjacency lists, copying $2\mathrm{\mid }E(G)\mathrm{\mid }$ relation tables and adding $387\mathrm{\mid }E(G)\mathrm{\mid }$ tautological slots takes time and output length polynomial in the input encoding length, and the output parameters $2\mathrm{\mid }E(G)\mathrm{\mid }$, $387\mathrm{\mid }E(G)\mathrm{\mid }$, $387$, ${\rho }_2$ depend only on the fixed family and on $\mathrm{\mid }E(G)\mathrm{\mid }$. The map is the first of the two transformations composed in A complete uniform graph gap-amplification step; its quantitative unsatisfiability guarantee is stated and proved there, not here.