Applying Changes to LDPC Codes by Using 3-Induced Matchings and Eigenvalues
Abstract
The 2-switch operation for reducing the number of short cycles in Tanner graphs of LDPC codes has been utilized in some works. If this operation is appropriately applied to a 2-induced matching in a bipartite graph, then it surely preserves the bipartiteness of the graph. With a 2-induced matching, we have only one choice for applying this type of change to the graph. Using 3-induced matchings creates more potential and flexibility to apply certain changes to the Tanner graph. We present a necessary and sufficient condition for the existence of a 3-induced matching in bipartite graphs with girth at least 6. A 3-induced matching helps us to have more choices for applying a change to a bipartite graph while surely preserving the bipartiteness of the graph and keeping the degree sequences unchanged. Among all changes that we consider, we select the best change for reducing the number of cycles of length 6. The eigenvalues of subgraphs are used to reach a 3-induced matching, and a condition in some steps can be checked to ensure that the subgraph has at least one 3-induced matching. We present some numerical results regarding the steps at which the condition that guarantees the existence of a 3-induced matching is checked.
Related
- Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
- Random Signs into Matchings: A Godsil-Gutman Identity, Formalized in Lean 4 (Part I)
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- Balanced weightings and permutation matchings applied to the monoid of order-preserving mappings
- A simple classification of the special matchings in the symmetric group
BibTeX
@misc{dehaghani2026applying,
title = {{Applying Changes to LDPC Codes by Using 3-Induced Matchings and Eigenvalues}},
author = {Alireza Eshraghi Dehaghani and Sara Saeedi Madani and Dariush Kiani},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00082},
eprint = {2611.00082},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00082},
}
RIS
TY - UNPB
TI - Applying Changes to LDPC Codes by Using 3-Induced Matchings and Eigenvalues
AU - Alireza Eshraghi Dehaghani
AU - Sara Saeedi Madani
AU - Dariush Kiani
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00082
UR - https://arxiv.org/abs/2611.00082
AB - The 2-switch operation for reducing the number of short cycles in Tanner graphs of LDPC codes has been utilized in some works. If this operation is appropriately applied to a 2-induced matching in a bipartite graph, then it surely preserves the bipartiteness of the graph. With a 2-induced matching, we have only one choice for applying this type of change to the graph. Using 3-induced matchings creates more potential and flexibility to apply certain changes to the Tanner graph. We present a necessary and sufficient condition for the existence of a 3-induced matching in bipartite graphs with girth at least 6. A 3-induced matching helps us to have more choices for applying a change to a bipartite graph while surely preserving the bipartiteness of the graph and keeping the degree sequences unchanged. Among all changes that we consider, we select the best change for reducing the number of cycles of length 6. The eigenvalues of subgraphs are used to reach a 3-induced matching, and a condition in some steps can be checked to ensure that the subgraph has at least one 3-induced matching. We present some numerical results regarding the steps at which the condition that guarantees the existence of a 3-induced matching is checked.
ER -