Skip to content

Incidence Expansion To Parity Tanner Expansion

Claim/Theorem

This node is a source-grounded corollary schema rather than a named theorem from one paper. Let \(I=(Q\cup V,E_I)\) be a bipartite graph with right degree exactly \(D\), and let \(H=(C\cup J,E_H)\) be a constant bipartite gadget with \(|C|=D\) and \(m=|J|\). For each \(v\in V\), fix a bijection \(\phi_v:N_I(v)\to C\). Define the lifted Tanner graph \(T=T(I,H)\) with left vertex set \(Q\) and right vertex set \(V\times J\), where \(q\in Q\) is connected to \((v,j)\) iff \((q,v)\in E_I\) and \((\phi_v(q),j)\in E_H\).

Set

\[ a_{\min}\;:=\;\min_{c\in C}\deg_H(c), \]

and

\[ \beta_H\;:=\;\min\bigl\{\,|\partial_H W|:\emptyset\neq W\subsetneq V(H),\;W\cap J\notin\{\emptyset,J\}\bigr\}. \]

If \(h_{\varepsilon_I}(I)\ge \alpha_I\), \(a_{\min}>0\), and \(\beta_H>0\), then \(T\) is also a local expander. More precisely,

\[ h_{\varepsilon_T}(T)\;\ge\;\alpha_T, \qquad \varepsilon_T=\frac{\varepsilon_I}{m}, \]

with

\[ \alpha_T\;=\;\frac{1}{4m}\min\!\left\{a_{\min}\alpha_I,\;\frac{\beta_H\alpha_I}{D},\;2\beta_H\right\}. \]

So local expansion of the base incidence graph survives any constant-size right-fiber blow-up whose local gadget has positive coordinate degree and positive partial-fiber boundary.

Dependencies

  • None.

Conflicts/Gaps

  • The theorem is conditional on the finite local gadget constant \(\beta_H\) being positive. This is not automatic for an arbitrary choice of local basis.
  • The statement is for a one-parity Tanner graph built from a right-fiber blow-up. Applying it to a concrete code family still requires identifying the correct base incidence graph and local gadget.
  • This node proves local expansion of the parity Tanner graph, not yet any statement about the contracted Tanner graph or hardware implementation. Those require [[tanner-to-contracted-expansion-transfer.md]] and the existing hardware-side nodes.

Sources

  • 10.48550/arXiv.2202.13641
  • 10.48550/arXiv.2109.14599