Laplacian code[1]
Description
A binary linear code whose parity-check matrix is the graph Laplacian reduced mod 2. For an undirected graph \(\Gamma\) with degree matrix \(D\) and adjacency matrix \(A\), the parity-check matrix is the symmetric matrix \(H=(D-A)\bmod 2\).Protection
A connected graph always contributes at least one logical bit. For generic sparse bounded-degree graph ensembles, the logical dimension stays \(O(1)\), while highly symmetric graphs such as square lattices or complete graphs can have much larger rank deficiency [1].Rate
Generic sparse-graph Laplacian-code families have vanishing rate with only \(O(1)\) logical bits, whereas more symmetric families can exhibit enhanced rank deficiency [1].Cousins
- Low-density parity-check (LDPC) code— Laplacian codes on bounded-degree graph families are classical LDPC codes.
- Pinwheel code— The pinwheel code is derived from the graph Laplacian of the pinwheel tiling, with a fraction of boundary checks removed.
- Anisotropic \(\mathbb{Z}_2\) Laplacian model code— The anisotropic \(\mathbb{Z}_2\) Laplacian model is the hypergraph product of a cyclic repetition code and a Laplacian code [1].
Primary Hierarchy
Parents
Incidence matrices of graphs have no repeated columns since that would correspond to multi-edges. Therefore, Laplacian codes can be interpreted as projective codes.
Laplacian code
References
- [1]
- Y. Tan, B. Roberts, N. Tantivasadakarn, B. Yoshida, and N. Y. Yao, “Fracton models from product codes”, Physical Review Research 7, (2025) arXiv:2312.08462 DOI
Page edit log
- Victor V. Albert (2026-04-21) — most recent
Cite as:
“Laplacian code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/laplacian
Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/graph/laplacian.yml.