pith. sign in

arxiv: 2604.12332 · v2 · submitted 2026-04-14 · 💻 cs.IT · math.CO· math.IT

Tur\'{a}n-Theoretic Bounds on Several Elementary Trapping Sets in LDPC Codes

Ziyang Zhao , Haoran Xiong , Zicheng Ye , Guiying Yan This is my paper

Pith reviewed 2026-05-13 06:30 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.IT
keywords LDPC codeselementary trapping setsTurán numberserror floorgirthTanner graphQC-LDPC
0
0 comments X

The pith

Turán numbers bound the size of elementary trapping sets in girth-8 LDPC codes

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper applies extremal graph theory to derive a new lower bound on elementary trapping sets in LDPC codes. For variable-regular codes of degree gamma with girth 8, where no two 8-cycles share a variable node, the number of unsatisfied checks b in an (a,b)-ETS is at least a gamma minus a times the quantity (sqrt of 24a minus 23 minus 1) divided by 4. A sympathetic reader would care because these trapping sets limit the performance of LDPC codes at high signal-to-noise ratios by causing the error floor. The authors further demonstrate that certain chorded cycle structures can be removed to eliminate some small ETSs and raise their minimum sizes.

Core claim

We prove that any (a,b)-ETS with g=8 variable-regular γ satisfies b≥ aγ - a(√(24a-23)-1)/4 provided that any two 8-cycles in the Tanner graph do not share common variable node. In addition, we can also eliminate ETSs by removing certain short-cycle structures with chords. The minimum sizes of ETSs obtained through these methods are significantly increased. To assess practical impact, we analyze spectral radii of the ETSs and construct QC-LDPC codes to show frame error rates in the error floor region.

What carries the argument

The Turán numbers of θ(2,2,2), θ(1,3,3) and D(4,4;0) that provide upper bounds on the number of certain subgraphs in the bipartite Tanner graph associated with the trapping set.

If this is right

  • The derived bound increases the minimum possible size of ETSs.
  • Removing short cycles with chords eliminates additional small ETSs.
  • Spectral radius analysis and QC-LDPC constructions confirm reduced frame error rates in the error floor region.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This counting method could be adapted to bound trapping sets in codes with larger girth or irregular degree distributions.
  • Practical code design tools might integrate these forbidden configurations to avoid error floors.
  • The assumption of disjoint 8-cycles may hold in many pseudorandom constructions, making the bound applicable to a wide range of LDPC codes.

Load-bearing premise

Any two 8-cycles in the Tanner graph share no common variable node, allowing the Turán number arguments to count the structures without overlap.

What would settle it

Construct or simulate a girth-8 variable-regular LDPC code whose Tanner graph has no two 8-cycles sharing a variable node, but contains an (a,b)-ETS violating the inequality b ≥ aγ - a(√(24a-23)-1)/4.

Figures

Figures reproduced from arXiv: 2604.12332 by Guiying Yan, Haoran Xiong, Zicheng Ye, Ziyang Zhao.

Figure 1
Figure 1. Figure 1: Figures (a) and (b) depict two 8-cycles that share two common check [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 4
Figure 4. Figure 4: Figures (a), (b) and (c) depict three substructures [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 3
Figure 3. Figure 3: The complete bipartite graph K3,3 and the triangular prism graph H3. Lemma 4. The following statements are true: 1) ex(6, G3) = 12, and the 6-order extremal graph is G = K3 ∨ K3; 2) ex(7, G3) = 15, and the 7-order extremal graph is G = (K3 + K1) ∨ K3, G = K3 ∨ K4, or G = S4 ∨ K3; 3) ex(8, G3) = 19, and the 7-order extremal graph is G = (K3 + K1) ∨ K4 or G = S4 ∨ K4. The proof of Lemma 4 is relegated to App… view at source ↗
Figure 5
Figure 5. Figure 5: Figures (a), (b), (c), and (d) depict the VN graphs of (10,0), (11,1), [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FER performance of C1 and its counterparts [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FER performance of C2 and its counterparts [PITH_FULL_IMAGE:figures/full_fig_p007_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: G′ is the 6-order extremal graph of G2. For 2), suppose that G is a G2-free graph with 7 vertices and 14 edges. First we show that the minimum degree of G, denoted by d1, must be 4. If d1 ≥ 5, then |E(G)| ≥ 5×7 2 > 17, which is a contradiction. If d1 ≤ 3, consider the graph G − v1, which satisfies |E(G − v1)| ≥ 14 − 3 = 11. Since G − v1 is also G2-free, we have G−v1 = G′ . Note that the minimum degree of G… view at source ↗
Figure 9
Figure 9. Figure 9: The graph G satisfying NG(v1) = NG(v2). Case 2: NG(v1) ̸= NG(v2). It is easy to see that |NG(v1) ∩ NG(v2)| = 3. Suppose that NG(v1) = {v3, v4, v5, v6} and NG(v2) = {v3, v4, v5, v7}. Noting that d6 = d7 = 4 and vertices v6 and v7 must share at least one common neighbour, let v3 ∈ NG(v6) ∩ NG(v7). As illustrated in [PITH_FULL_IMAGE:figures/full_fig_p009_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The graph G satisfying NG(v1) ̸= NG(v2). On the other hand, the graph (K2 + K1) ∨ K4 and is a G2-free graph with 13 edges, which implies ex(7, G2) ≥ 13. This proves that ex(7, G2) = 13. B. Proof of Lemma 4 Lemma 4. The following statements are true: 1) ex(6, G3) = 12, and the 6-order extremal graph is G = K3 ∨ K3; 2) ex(7, G3) = 15, and the 7-order extremal graph is G = (K3 + K1) ∨ K3, G = K3 ∨ K4, or G =… view at source ↗
Figure 12
Figure 12. Figure 12: G = S4 ∨ K3 is the 7-order extremal graph of G3. Subcase 2.2: πG = (4, 4, 4, 4, 4, 5, 5). In this subcase, G must have two non-adjacent vertices of degree 4, say v1 and v2. If |NG(v1) ∩ NG(v2)| = 4, then G must be isomorphic to the graph [PITH_FULL_IMAGE:figures/full_fig_p009_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Figures (a) and (b) depict the graph G satisfying |NG(v1) ∩ NG(v2)| = 4 and |NG(v1) ∩ NG(v2)| = 3 respectively. For 3), suppose G is a graph of order 8 that contains no G3 as a subgraph. We first show that |E(G)| ≤ 19. Assume for contradiction that |E(G)| = 20. Then the minimum degree of G, denoted by d1, must be 5. Indeed, if d1 ≥ 6, then |E(G)| ≥ 6×8 2 = 24, which is a contradiction; if d1 ≤ 4, consider… view at source ↗
read the original abstract

LDPC codes have attracted significant attention because of their superior performance close to the Shannon limit. Elementary trapping sets are the main cause of the error floor phenomenon in LDPC codes. We consider typical graphs related to trapping sets, including theta graphs, dumbbell graphs, and short cycles with chords. Based on the Tur\'{a}n numbers of $\theta(2,2,2)$, $\theta(1,3,3)$ and $D(4,4;0)$, we prove that any $(a,b)$-ETS with $g=8$ variable-regular $\gamma$ satisfies the inequality $b\geq a\gamma-\frac{a(\sqrt{24a-23}-1)}{4}$, provided that any two 8-cycles in the Tanner graph do not share common variable node. In addition, we can also eliminate ETSs by removing certain short-cycle structures with chords. The minimum sizes of ETSs obtained through these methods are significantly increased. To assess practical impact , we analyze spectral radii of the ETSs and construct QC-LDPC codes to show frame error rates in the error floor region.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that in variable-regular LDPC Tanner graphs of girth 8, any (a,b)-elementary trapping set satisfies the inequality b ≥ aγ − a(√(24a−23)−1)/4 whenever any two 8-cycles are variable-disjoint. The proof applies the Turán numbers ex(n, θ(2,2,2)), ex(n, θ(1,3,3)) and ex(n, D(4,4;0)) to forbid theta graphs, dumbbells and chorded 8-cycles, thereby obtaining a quadratic lower bound on the number of unsatisfied checks. The paper further shows that deleting certain chorded short cycles increases the minimum ETS size and validates the approach via spectral-radius calculations and explicit QC-LDPC constructions whose frame-error-rate curves improve in the error-floor region.

Significance. If the conditional bound is correct, the work supplies a parameter-free, extremal-graph-theoretic tool for lower-bounding ETS size that is stronger than purely combinatorial or simulation-based estimates. The explicit use of Turán numbers to control forbidden subconfigurations is a clear methodological advance. The authors are credited for stating the variable-disjointness hypothesis up front rather than claiming an unconditional result, and for connecting the bound to concrete code constructions and FER data.

major comments (2)
  1. [Proof of the main bound] The central inequality (abstract and main theorem) is derived by additively summing the maximum number of forbidden subgraphs permitted by the cited Turán numbers; this summation step invokes the hypothesis that 8-cycles are pairwise variable-disjoint. When the hypothesis fails, the same counting no longer upper-bounds the number of allowable dense substructures, so the quadratic term √(24a−23) may not be obtained and the claimed lower bound on b need not hold. The manuscript states the condition but supplies neither a density estimate for graphs satisfying it nor a relaxed bound that accounts for possible overlaps.
  2. [Elimination of ETS by chord removal] Table or figure reporting minimum ETS sizes after chord removal (section on elimination of ETS): the claim that 'minimum sizes of ETSs are significantly increased' is not accompanied by explicit numerical values or a comparison table showing the increase in a for fixed γ before and after removal; without these data the quantitative improvement cannot be verified.
minor comments (2)
  1. [Introduction] The notation ex(n, θ(2,2,2)), ex(n, θ(1,3,3)) and ex(n, D(4,4;0)) is used without a brief definition or reference in the introduction; readers outside extremal graph theory would benefit from a one-sentence explanation.
  2. [Practical constructions] In the QC-LDPC construction section, the spectral-radius plots and FER curves should include explicit legends indicating which curves correspond to the original versus the modified codes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for the thorough review, positive assessment of the methodological contribution, and recommendation for minor revision. We address each major comment point by point below.

read point-by-point responses

  1. Referee: [Proof of the main bound] The central inequality (abstract and main theorem) is derived by additively summing the maximum number of forbidden subgraphs permitted by the cited Turán numbers; this summation step invokes the hypothesis that 8-cycles are pairwise variable-disjoint. When the hypothesis fails, the same counting no longer upper-bounds the number of allowable dense substructures, so the quadratic term √(24a−23) may not be obtained and the claimed lower bound on b need not hold. The manuscript states the condition but supplies neither a density estimate for graphs satisfying it nor a relaxed bound that accounts for possible overlaps.

    Authors: We thank the referee for this precise analysis. The theorem is indeed conditional on the variable-disjointness of 8-cycles, which is stated explicitly in the abstract and the main theorem statement. This condition ensures that the variable nodes involved in the forbidden subgraphs (theta graphs θ(2,2,2), θ(1,3,3), and dumbbells D(4,4;0)) do not overlap, permitting the direct additive application of the Turán numbers ex(n, ·) to bound the total number of such substructures. Without this hypothesis, overlaps could occur, and the counting argument would require adjustment, potentially weakening the quadratic term. The manuscript does not include a density estimate for the class of graphs satisfying the disjointness condition nor a relaxed unconditional bound, as our primary contribution is the derivation of the stated conditional bound. We will revise the manuscript to include an additional remark in the discussion section acknowledging this limitation and noting that deriving bounds without the disjointness assumption remains an open direction for future research. revision: partial

  2. Referee: [Elimination of ETS by chord removal] Table or figure reporting minimum ETS sizes after chord removal (section on elimination of ETS): the claim that 'minimum sizes of ETSs are significantly increased' is not accompanied by explicit numerical values or a comparison table showing the increase in a for fixed γ before and after removal; without these data the quantitative improvement cannot be verified.

    Authors: We agree with the referee that the quantitative improvement should be supported by explicit data. In the revised version, we will add a new table in the section on elimination of ETS by chord removal. This table will list, for several values of γ and a, the minimum b (or equivalently the increase in minimum a for fixed b) before and after the removal of chorded short cycles, demonstrating the significant increase in the minimum ETS size. revision: yes

Circularity Check

1 steps flagged

Minor self-citation of prior graph-theoretic results; central bound derived independently from external Turán numbers

specific steps
  1. self citation load bearing [Abstract and proof outline]
    "Based on the Turán numbers of θ(2,2,2), θ(1,3,3) and D(4,4;0), we prove that any (a,b)-ETS with g=8 variable-regular γ satisfies the inequality b≥aγ−a(√(24a−23)−1)/4, provided that any two 8-cycles in the Tanner graph do not share common variable node."

    The cited Turán numbers originate in the authors' prior work; while the present counting argument applies them to ETSs, the self-citation supplies the numerical values used to obtain the quadratic term √(24a−23). This is minor and non-load-bearing because the combinatorial reduction itself remains external and the bound is not forced by definition.

full rationale

The paper derives the bound b ≥ aγ − a(√(24a−23)−1)/4 by applying known Turán numbers ex(n, θ(2,2,2)), ex(n, θ(1,3,3)) and ex(n, D(4,4;0)) to forbid theta graphs, dumbbells and chorded cycles under the explicit assumption that 8-cycles are variable-disjoint. This counting argument is combinatorial and independent of the target ETS parameters; it does not fit any quantity to the same data set nor reduce the inequality to a tautology by definition. The only potential circularity is a standard self-citation of the authors' earlier results on those specific Turán numbers, which is not load-bearing for the central claim. No self-definitional steps, fitted-input predictions, or ansatz smuggling occur.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The derivation rests on standard extremal graph theory (Turán numbers) plus the domain assumption that the Tanner graph is variable-regular of girth 8 and that no two 8-cycles share a variable node. No free parameters are introduced; the bound is parameter-free once γ and a are given.

axioms (2)
  • domain assumption The Tanner graph is variable-regular of degree γ and girth exactly 8.
    Invoked to apply the Turán counting to θ(2,2,2) and related graphs.
  • domain assumption Any two 8-cycles share no common variable node.
    Required for the counting argument that produces the closed-form bound.

pith-pipeline@v0.9.0 · 5506 in / 1537 out tokens · 42821 ms · 2026-05-13T06:30:04.324908+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Low-density parity-check codes,

    R. Gallager, “Low-density parity-check codes,”IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21–28, 1962

    work page 1962

  2. [2]

    On the design of low-density parity-check codes within 0.0045 db of the shannon limit,

    S.-Y . Chung, G. Forney, T. Richardson, and R. Urbanke, “On the design of low-density parity-check codes within 0.0045 db of the shannon limit,”IEEE Communications Letters, vol. 5, no. 2, pp. 58–60, 2001

    work page 2001

  3. [3]

    Error floors of ldpc codes on the binary symmetric channel,

    S. K. Chilappagari, S. Sankaranarayanan, and B. Vasic, “Error floors of ldpc codes on the binary symmetric channel,” in2006 IEEE International Conference on Communications, vol. 3, 2006, pp. 1089–1094

    work page 2006

  4. [4]

    A general method for finding low error rates of ldpc codes,

    C. A. Cole, S. G. Wilson, E. K. Hall, and T. R. Gial- lorenzi, “A general method for finding low error rates of ldpc codes,”arXiv preprint cs/0605051, 2006

    work page arXiv 2006

  5. [5]

    Asymptotic spectra of trapping sets in regular and irregular ldpc code ensembles,

    O. Milenkovic, E. Soljanin, and P. Whiting, “Asymptotic spectra of trapping sets in regular and irregular ldpc code ensembles,”IEEE Transactions on Information Theory, vol. 53, no. 1, pp. 39–55, 2007

    work page 2007

  6. [6]

    On the hardness of approximating stopping and trapping sets,

    A. McGregor and O. Milenkovic, “On the hardness of approximating stopping and trapping sets,”IEEE Transactions on Information Theory, vol. 56, no. 4, p. 1640–1650, 2010

    work page 2010

  7. [7]

    Construction of girth-8 qc-ldpc codes free of small trapping sets,

    S. Naseri and A. H. Banihashemi, “Construction of girth-8 qc-ldpc codes free of small trapping sets,”IEEE Communications Letters, vol. 23, no. 11, pp. 1904–1908, 2019

    work page 1904

  8. [8]

    On the construction of ldpc codes free of small trapping sets by controlling cycles,

    X. Tao, Y . Li, Y . Liu, and Z. Hu, “On the construction of ldpc codes free of small trapping sets by controlling cycles,”IEEE Communications Letters, vol. 22, no. 1, pp. 9–12, 2018

    work page 2018

  9. [9]

    Protograph-based ldpc codes with chordless short cycles and large minimum distance,

    F. Amirzade, M.-R. Sadeghi, and D. Panario, “Protograph-based ldpc codes with chordless short cycles and large minimum distance,” in2022 17th Canadian Workshop on Information Theory (CWIT), 2022, pp. 16–20

    work page 2022

  10. [10]

    Construction of time invariant spatially coupled ldpc codes free of small trapping sets,

    S. Naseri and A. H. Banihashemi, “Construction of time invariant spatially coupled ldpc codes free of small trapping sets,”IEEE Transactions on Communications, vol. 69, no. 6, pp. 3485–3501, 2021

    work page 2021

  11. [11]

    Theoretical bounds for the size of elementary trapping sets by graph theory methods,

    H. Xiong, Z. Ye, H. Zhang, J. Wang, K. Liu, D. Yin, G. Wang, G. Yan, and Z. Ma, “Theoretical bounds for the size of elementary trapping sets by graph theory methods,” in2024 IEEE Information Theory Workshop (ITW), 2024, pp. 193–198

    work page 2024

  12. [12]

    Lower bounds on the size of smallest elementary and non-elementary trapping sets in variable-regular ldpc codes,

    Y . Hashemi and A. H. Banihashemi, “Lower bounds on the size of smallest elementary and non-elementary trapping sets in variable-regular ldpc codes,”IEEE Com- munications Letters, vol. 21, no. 9, pp. 1905–1908, 2017

    work page 1905

  13. [13]

    Con- struction of protograph-based ldpc codes with chordless short cycles,

    F. Amirzade, M.-R. Sadeghi, and D. Panario, “Con- struction of protograph-based ldpc codes with chordless short cycles,”IEEE Transactions on Information Theory, vol. 70, no. 1, pp. 51–74, 2024

    work page 2024

  14. [14]

    Edge-coloring tech- nique to analyze elementary trapping sets of spatially- coupled ldpc convolutional codes,

    M.-R. Sadeghi and F. Amirzade, “Edge-coloring tech- nique to analyze elementary trapping sets of spatially- coupled ldpc convolutional codes,”IEEE Communica- tions Letters, vol. 24, no. 4, pp. 711–715, 2020

    work page 2020

  15. [15]

    On characteri- zation of elementary trapping sets of variable-regular ldpc codes,

    M. Karimi and A. H. Banihashemi, “On characteri- zation of elementary trapping sets of variable-regular ldpc codes,”IEEE Transactions on Information Theory, vol. 60, no. 9, pp. 5188–5203, 2014

    work page 2014

  16. [16]

    On the tur ´an number of theta graphs,

    M. Zhai, L. Fang, and J. Shu, “On the tur ´an number of theta graphs,”Graphs and Combinatorics, vol. 37, 2021

    work page 2021

  17. [17]

    On an extremal problem in graph theory,

    P. Tur ´an, “On an extremal problem in graph theory,” Matematikai e ´s Fizikai Lapok, vol. 48, 1941

    work page 1941

  18. [18]

    A recursive approach to low complex- ity codes,

    R. Tanner, “A recursive approach to low complex- ity codes,”IEEE Transactions on Information Theory, vol. 27, no. 5, pp. 533–547, 1981

    work page 1981

  19. [19]

    Pseudo- codewords of cycle codes via zeta functions,

    R. Koetter, W.-C. Li, P. V ontobel, and J. Walker, “Pseudo- codewords of cycle codes via zeta functions,” inInfor- mation Theory Workshop, 2004, pp. 7–12

    work page 2004

  20. [20]

    Error floor approximation for ldpc codes in the awgn channel,

    B. K. Butler and P. H. Siegel, “Error floor approximation for ldpc codes in the awgn channel,”IEEE Transactions 11 on Information Theory, vol. 60, no. 12, pp. 7416–7441, 2014

    work page 2014

  21. [21]

    B. McKay. (2009) nauty user’s guide. [Online]. Available: https://users.cecs.anu.edu.au/ bdm/nauty/

    work page 2009

  22. [22]

    The impact of the distance between cycles on elementary trapping sets,

    H. Xiong, G. Wang, Z. Ma, and G. Yan, “The impact of the distance between cycles on elementary trapping sets,” IEEE Transactions on Information Theory, vol. 72, no. 1, pp. 298–314, 2026

    work page 2026

  23. [23]

    Regular and irregular progressive edge-growth tanner graphs,

    X. Hu, E. Eleftheriou, and D. Arnold, “Regular and irregular progressive edge-growth tanner graphs,”IEEE Transactions on Information Theory, vol. 51, no. 1, pp. 386–398, 2005

    work page 2005

  24. [24]

    On the search of smallest QC-LDPC code with girth six and eight,

    J. Singh, M. Gupta, and J. S. Bhullar, “On the search of smallest QC-LDPC code with girth six and eight,” Cryptography and Communications, vol. 12, pp. 711– 723, 2019, springer Science+Business Media, LLC, part of Springer Nature 2019

    work page 2019

  25. [25]

    Relation between gcd constraint and full-length row-multiplier qc-ldpc codes with girth eight,

    G. Zhang, Y . Hu, Y . Fang, and D. Ren, “Relation between gcd constraint and full-length row-multiplier qc-ldpc codes with girth eight,”IEEE Communications Letters, vol. 25, no. 9, pp. 2820–2823, 2021

    work page 2021

  26. [26]

    (4, l) regular girth-8 qc- ldpc short codes based on reversal of dual sequences,

    G. Zhang, J. Yu, and Y . Zhou, “(4, l) regular girth-8 qc- ldpc short codes based on reversal of dual sequences,” Mobile Communications, vol. 48, no. 05, pp. 27–31, 2024

    work page 2024