Pith. sign in

REVIEW 3 major objections 4 minor 22 references

Bounds and New Constructions for Girth-Constrained Regular Bipartite Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper establishes lower bounds on the number of check nodes in girth-constrained regular bipartite graphs and constructs a semi-regular family with girth 8 that has only $O(\sqrt{n})$ check nodes, matching the bound up to a constant…

desk verdict The paper's advertised constant-factor optimal semi-regular construction is wrong—Roth's theorem forces b_t/t to superlinear—but the girth-8 lower bound and the regular construction still deserve a serious revision. read the letter →

arxiv 2506.11268 v1 pith:OJIPHFUI submitted 2025-06-12 cs.IT math.IT

Sheida Rabeti , Mohsen Moradi , Hessam Mahdavifar This is my paper · ORCID
classification cs.ITmath.IT MSC 05C3505C38
keywords regularbipartitegraphsgirthLDPCcodeschecknodecountthree-termarithmeticprogressionsemi-regularhigh-rateminimumdistance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks how many check nodes a regular bipartite graph must have, for a given number of variable nodes and a given shortest cycle length (girth). It proves that for girth 8 the check count must grow at least like the square root of the variable count, and for girths 10, 12, 14, and 16 it must grow at least like $n^{2/3}$ or $n^{3/4}$, respectively. On the construction side, the paper gives two girth-8 families: a regular one whose minimum distance is $2^{w_c}$, and a semi-regular one built from integer sequences with no three-term arithmetic progression that achieves $m = O(\sqrt{n})$ check nodes, matching the lower bound up to a constant factor. These constructions yield sparse parity-check matrices for high-rate codes, with the semi-regular family approaching rate 1 as the block length grows.

What carries the argument

The load-bearing object for the semi-regular construction is the three-level parity-check matrix $H_s$: column $j$ receives its three 1s at row positions given by affine functions of a free-3-AP integer sequence $b$, namely $r_{1j}=a_j$, $r_{2j}=c_1+b_{i_j}+a_j$, and $r_{3j}=c_2+a_j+r_{2j}$. A 6-cycle in the Tanner graph would reduce to the equation $b_p+b_\ell = 2b_q$, so the no-3-AP property of $b$ is exactly what rules out 6-cycles. For the bounds, the machinery is the standard rooted-tree count: with girth $2\ell$, a height-$\ell$ tree rooted at a check node contains distinct vertices, and double-counting the edges from the last layer yields polynomial inequalities in $m$ and $n$ that are solved, exactly for girth 8 and order-wise for girths 10 through 16.

What would settle it

Construct the semi-regular $H_s$ for a fixed $t$ using a verified free-3-AP sequence and run a brute-force search over all 4- and 6-cycles in the Tanner graph; the presence of any such cycle falsifies Proposition 5's girth-8 claim.

Watch

Extended reading notes

Core claim

The central claim is that girth-8 bipartite graphs can be both regular in column weight and sublinear in check-node count: for $n = t^2$ variable nodes, the semi-regular Tanner graph $H_s$ has only $4t + 2b_t - 3$ check nodes, where $b_t$ is the $t$-th term of a free 3-AP sequence, and since $r(M)$ is nearly linear in $M$, this means $m = O(\sqrt{n})$. The paper proves the girth is exactly 8 by showing that any candidate 6-cycle would force three sequence elements to satisfy $b_p + b_\ell = 2b_q$, contradicting the absence of length-3 arithmetic progressions. It further establishes a matching lower bound for any girth-8 regular bipartite graph: with column weight $w_c$, variable count $n$, and check count $m$, one must have $m \geq \frac{-w_c(w_c-2) + w_c\sqrt{(w_c-2)^2+4(w_c-1)n}}{2}$. Order-wise lower bounds $m = \Omega(n^{2/3})$ for girths 10 and 12, and $m = \Omega(n^{3/4})$ for girths 14 and 16, are also claimed.

Load-bearing premise

For girths 10 through 16, the claimed bounds depend on a table of counting inequalities that the paper lists but does not prove, and whose polynomial coefficients are left unspecified.

Editorial extensions

If this is right

  • For girth 8 and column weight 2, the lower bound is tight and is met by the base matrix of fair-density parity-check codes, as noted in Remark 1.
  • Any regular bipartite graph with girth 10 or 12 needs $m = \Omega(n^{2/3})$ check nodes, and with girth 14 or 16 needs $m = \Omega(n^{3/4})$ check nodes, so increasing girth forces a polynomial increase in redundancy.
  • The semi-regular construction gives codes with rate $R = 1 - m/n \to 1$ as the block length grows while maintaining girth 8, per Remark 5.
  • The regular construction produces girth-8 codes whose claimed minimum distance is $2^{w_c}$, growing exponentially in the column weight, compared to the linear lower bound for general girth-8 LDPC codes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step, not taken in the paper, is to generalize the semi-regular construction to column weights larger than 3; using higher-order AP-free sets may preserve girth 8 with $m = O(\sqrt{n})$ while increasing the minimum distance.
  • The paper's bounds for girths 10 through 16 rest on a table of counting inequalities that is asserted without derivation; verifying or repairing those inequalities would either strengthen confidence in the $n^{2/3}$ and $n^{3/4}$ thresholds or reveal a gap.
  • The connection between 3-AP-free sets and Tanner graphs suggests a direct pipeline: any improvement in lower bounds for $r(M)$ immediately improves the constant in the $m = O(\sqrt{n})$ construction, and near-optimal empirical sequences could be used to build finite-length high-rate codes.
  • If the $d_{\min} = 2^{w_c}$ claim for the regular construction holds, it gives an explicit trade-off between girth 8 and exponentially growing minimum distance, which could translate into better trapping-set behavior for high-rate LDPC codes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the relation between the number of check nodes m and variable nodes n in regular bipartite graphs with prescribed girth. It derives a lower bound for girth 8 in Theorem 1, states order-wise bounds for girths 10, 12, 14, and 16, and presents two girth-8 constructions: a (w_c, w_r)-regular graph with minimum distance 2w_c, and a semi-regular graph built from a 3-arithmetic-progression-free integer sequence. The semi-regular construction is claimed to achieve m = O(√n) check nodes, matching the lower bound up to a constant.

Significance. The girth-8 lower bound in Theorem 1 is derived rigorously and is a useful addition to the literature. The regular construction with d_min = 2w_c is a solid, explicit construction. The semi-regular construction is a creative application of 3-AP-free sequences, but its central asymptotic claim is not supported: as discussed below, the construction actually yields m = n^{1/2+o(1)}, not m = O(√n). After correcting this claim, the construction remains a valid sublinear-redundancy construction, but the advertised order-optimality is lost.

major comments (3)
  1. [Section IV, Remark 5] The inference that M = O(t) from Theorem 4 is invalid. Theorem 4 is a lower bound on r(M); since {b_1, ..., b_t} is a 3-AP-free subset of [b_t] of size t, Roth's theorem gives r(b_t) = o(b_t), so b_t / t → ∞. Consequently m = 4t + 2b_t - 3 = ω(t), and with n = t^2 this means m = n^{1/2+o(1)}, not O(√n). The claim in Remark 5 and the abstract that the construction is asymptotically optimal is therefore unsupported and must be revised.
  2. [Section IV, Definition 3] The stated row range for Level 3 is inconsistent with the formula for r3j. For a_j = t and b_{i_j} = b_t, we get r3j = (√n - 1 + b_t) + t + (√n - 1 + b_t + t) = 4t + 2b_t - 2, which exceeds the declared last row 4t + 2b_t - 3 by one. The constant c2 should be √n - 2 + b_t for the construction to fit the declared m rows; without this correction, the matrix has a 1 outside its stated dimensions.
  3. [Section II.B, Step 1] The inequalities for girths 10, 12, 14, and 16 are stated without derivation, and the coefficients a_{i,j} in the polynomials P_G(m) are not specified. Because the order-wise bounds (7)-(10) rest on these inequalities, the authors should either provide the double-counting argument in the style of Theorem 1 or cite a reference for each inequality. As written, the reader cannot verify the claimed m = O(n^{2/3}) and m = O(n^{3/4}) results.
minor comments (4)
  1. [Section IV, Proposition 5] The WLOG reduction in the 6-cycle proof is not justified. The authors should explain why any 6-cycle can be relabeled so that the shared rows are r1p = r1q, r2q = r2ℓ, and r3p = r3ℓ; in particular, they should rule out the possibility that two of the three shared rows lie in the same level.
  2. [Section III, Proposition 3] The proof of d_min = 2w_c is only worked out for w_c = 3; the general case is dismissed as 'straightforward using induction' without details. A sketch of the induction step would make the claim verifiable.
  3. [Throughout] There are several typographical issues: 'tanner graph' in Proposition 5 should be 'Tanner graph', 'qubic' in Section II.B should be 'cubic', and the girth notation G=8 appears with inconsistent spacing in a few places.
  4. [Section IV, Example 2] The example in Fig. 2 does not state the resulting matrix dimensions or verify the row ranges from Definition 3; given the off-by-one issue in the row ranges, such a verification would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the bounds and constructions are derived from explicit counting and explicit matrix definitions, with no fitted parameter or self-citation used as the load-bearing premise.

full rationale

The paper's derivation chain is self-contained. Theorem 1 derives a lower bound on m from a 3-level tree rooted at a check node, using the double-counting identity w_r = w_c n/m; this is a standard edge-count relation, not an input that equals the claimed output. The Section II.B order bounds for girth 10-16 are asserted through polynomial inequalities; the 'Step 1' inequalities are indeed stated without proof, making the derivation incomplete, but they are not circular because girth is not defined in terms of those polynomials and no quantity is fitted to data. The Section III construction is explicit via Algorithm 1, and the girth-8 proof uses contradictions among characteristic arrays. Section IV defines H_s explicitly from a 3-AP-free sequence, and Proposition 5 proves girth 8 by showing that a 6-cycle would imply b_p + b_l = 2b_q, i.e., a forbidden arithmetic progression; the claimed property is proved, not assumed. The citation to [14], which shares an author with this paper, is used only as a comparison in Remark 1 and as motivation in the introduction, not as the basis for any new theorem or construction. The notable weaknesses are correctness/rigor concerns rather than circularity: the G=10-16 'inequalities are found as below' lacks derivation, and Remark 5's inference that the Behrend lower bound gives M=O(t) is questionable, since a sublinear lower bound on r(M) does not imply the maximum element of a t-element 3-free set is O(t). These issues do not involve fitting, self-definition, or a self-citation chain, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central results rest on standard Moore-bound tree arguments and on the assumed correctness of the unproved Step 1 inequalities for girths 10-16. No free parameters are fitted; the 3-AP-free sequence is an external object with a cited density guarantee.

assumptions (4)
  • standard math For a graph with girth G=2ℓ, any tree of height ℓ rooted at a vertex contains all distinct vertices up to that height.
    Used in Section II to count nodes in a rooted tree; this is the standard Moore-bound argument, cited as [15].
  • domain assumption The graph is simple, with no parallel edges or loops, and the regular degree assumptions hold.
    Implicit throughout; Tanner graphs of LDPC codes are simple bipartite graphs.
  • domain assumption The free 3-AP sequence satisfies r(M) ≥ c1 M^{1 - c2/sqrt(log M)} (Theorem 4, cited from [19],[21]).
    Used in Remark 5 to conclude m = O(t) because b_t can be chosen close to linear in t. This is an external theorem from the literature, not proven in the paper.
  • ad hoc to paper The inequalities for G=10-16 listed in Step 1 of Section II.B are correct.
    The paper asserts these inequalities without proof; they are the foundation for the order-wise bounds. Treating them as axioms makes the grounding explicit.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bounds and New Constructions for Girth-Constrained Regular Bipartite Graphs." pith.science (2026). https://pith.science/paper/OJIPHFUI

@misc{pith2026250611268,
  author       = {Pith},
  title        = {Pith review of: Bounds and New Constructions for Girth-Constrained Regular Bipartite Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OJIPHFUI}},
  note         = {Machine review of arXiv:2506.11268}
}
abstract

In this paper, we explore the design and analysis of regular bipartite graphs motivated by their application in low-density parity-check (LDPC) codes specifically with constrained girth and in the high-rate regime. We focus on the relation between the girth of the graph, and the size of the sets of variable and check nodes. We derive bounds on the size of the vertices in regular bipartite graphs, showing how the required number of check nodes grows with respect to the number of variable nodes as girth grows large. Furthermore, we present two constructions for bipartite graphs with girth $\mathcal{G} = 8$; one based on a greedy construction of $(w_c, w_r)$-regular graphs, and another based on semi-regular graphs which have uniform column weight distribution with a sublinear number of check nodes. The second construction leverages sequences of integers without any length-$3$ arithmetic progression and is asymptotically optimal while maintaining a girth of $8$. Also, both constructions can offer sparse parity-check matrices for high-rate codes with medium-to-large block lengths. Our results solely focus on the graph-theoretic problem but can potentially contribute to the ongoing effort to design LDPC codes with high girth and minimum distance, specifically in high code rates.

Figures

Figures reproduced from arXiv: 2506.11268 by the authors.

Figure 1
Figure 1. (wr, wc)-regular Hreg after the first iteration of Level 3 Observation 1: Consider two vertices v1 and v2 with char￾acteristic arrays a1 = (t1,1, ..., t1,wc−2, ℓ1, j1) and a2 = (t2,1, ..., t2,wc−2, ℓ2, j2). If a check node connects v1 and v2, then a1 and a2 are identical at wc − 2 indices and differ in exactly one index. Observation 2: Assume that check node c12 connects two ver￾tices v1 and v2, and c13 connects v1 … view at source ↗
Figure 2
Figure 2. n = 64, G = 8, b = {1, 2, 4, 5, 10, 11, 13, 14}. Consider an increasing free 3-AP sequence bi . Using this sequence, we construct the parity-check matrix Hs, where each column has a weight of 3, and the matrix has a girth of 8. Definition 3: Let n = t 2 for some integer t ⩾ 0. The matrix Hs of dimension m × n has three distinct levels of rows: • Level 1: Contains the first 1s of all columns (rows 1 to t). • Level 2:… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

  1. [1]

    Good error-correcting codes based on very sparse matrices,

    D. J. MacKay, “Good error-correcting codes based on very sparse matrices,”IEEE transactions on Information Theory, vol. 45, no. 2, pp. 399–431, 1999

    work page 1999

  2. [2]

    The capacity of low-density parity- check codes under message-passing decoding,

    T. J. Richardson and R. L. Urbanke, “The capacity of low-density parity- check codes under message-passing decoding,”IEEE Transactions on information theory, vol. 47, no. 2, pp. 599–618, 2001

    work page 2001

  3. [3]

    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

    1962

  4. [4]

    A Survey on Trapping Sets and Stopping Sets

    A. Price and J. Hall, “A survey on trapping sets and stopping sets,”arXiv preprint arXiv:1705.05996, 2017

    work page Pith review arXiv 2017

  5. [5]

    A unifying framework to construct QC-LDPC tanner graphs of desired girth,

    R. Smarandache and D. G. Mitchell, “A unifying framework to construct QC-LDPC tanner graphs of desired girth,”IEEE Transactions on Infor- mation Theory, vol. 68, no. 9, pp. 5802–5822, 2022

    work page 2022

  6. [6]

    Quasi-cyclic LDPC codes: Influence of proto-and tanner-graph structure on minimum Hamming distance upper bounds,

    R. Smarandache and P. O. V ontobel, “Quasi-cyclic LDPC codes: Influence of proto-and tanner-graph structure on minimum Hamming distance upper bounds,”IEEE Transactions on Information Theory, vol. 58, no. 2, pp. 585–607, 2012

    work page 2012

  7. [7]

    Quasi-Cyclic low-density parity-check codes with girth larger than12,

    S. Kim, J.-S. No, H. Chung, and D.-J. Shin, “Quasi-Cyclic low-density parity-check codes with girth larger than12,”IEEE Transactions on Information Theory, vol. 53, no. 8, pp. 2885–2891, 2007

    work page 2007

  8. [8]

    Efficient search of girth-optimal QC-LDPC codes,

    A. Tasdighi, A. H. Banihashemi, and M.-R. Sadeghi, “Efficient search of girth-optimal QC-LDPC codes,”IEEE Transactions on Information Theory, vol. 62, no. 4, pp. 1552–1564, 2016

    work page 2016

Show all 22 references
  1. [9]

    A family of cubical graphs,

    W. T. Tutte, “A family of cubical graphs,” inMathematical Proceedings of the Cambridge Philosophical Society, vol. 43, no. 4. Cambridge University Press, 1947, pp. 459–474

    1947

  2. [10]

    The Moore bound for irregular graphs,

    N. Alon, S. Hoory, and N. Linial, “The Moore bound for irregular graphs,” Graphs and Combinatorics, vol. 18, pp. 53–57, 2002

    2002

  3. [11]

    Extremal problems in graph theory,

    P. Erdös, “Extremal problems in graph theory,”Publ. House Cszechoslo- vak Acad. Sci., Prague, pp. 29–36, 1964

    1964

  4. [12]

    De Caen and L

    D. De Caen and L. A. Székely,The maximum size of 4-and 6-cycle free bipartite graphs on m, n vertices. Rheinische Friedrich-Wilhelms- Universität, 1991

    1991

  5. [13]

    Graphs without cycles of even length,

    T. Lam, “Graphs without cycles of even length,”Bulletin of the Australian Mathematical Society, vol. 63, no. 3, pp. 435–440, 2001

    2001

  6. [14]

    High-rate fair-density parity-check codes,

    H. Mahdavifar, “High-rate fair-density parity-check codes,”arXiv preprint arXiv:2402.06814, 2024

    2024 arXiv

  7. [15]

    Constructions for cubic graphs with large girth,

    N. L. Biggs, “Constructions for cubic graphs with large girth,”Electron. J. Comb., vol. 5, 1998. [Online]. Available: https://api.semanticscholar. org/CorpusID:7695157

    1998

  8. [16]

    Graphs of prescribed girth and bi-degree,

    Z. Furedi, F. Lazebnik, A. Seress, V . A. Ustimenko, and A. J. Woldar, “Graphs of prescribed girth and bi-degree,”Journal of Combinatorial Theory, Series B, vol. 64, no. 2, pp. 228–239, 1995

    1995

  9. [17]

    Progressive edge-growth tanner graphs,

    X.-Y . Hu, E. Eleftheriou, and D.-M. Arnold, “Progressive edge-growth tanner graphs,” inGLOBECOM’01. IEEE Global Telecommunications Conference (Cat. No. 01CH37270), vol. 2. IEEE, 2001, pp. 995–1001

    2001

  10. [18]

    A recursive approach to low complexity codes,

    R. Tanner, “A recursive approach to low complexity codes,”IEEE Transactions on information theory, vol. 27, no. 5, pp. 533–547, 1981

    1981

  11. [19]

    On sets of integers which contain no three terms in arithmetical progression,

    F. A. Behrend, “On sets of integers which contain no three terms in arithmetical progression,”Proceedings of the National Academy of Sciences, vol. 32, no. 12, pp. 331–332, 1946

    1946

  12. [20]

    Sequences containing no 3-term arithmetic progres- sions,

    J. Dybizba ´nski, “Sequences containing no 3-term arithmetic progres- sions,”the electronic journal of combinatorics, pp. P15–P15, 2012

    2012

  13. [21]

    Finding large 3-free sets i: The small n case,

    W. Gasarch, J. Glenn, and C. P. Kruskal, “Finding large 3-free sets i: The small n case,”Journal of Computer and System Sciences, vol. 74, no. 4, pp. 628–655, 2008

    2008

  14. [22]

    On sets of integers which contain no three terms in arithmetical progression,

    R. Salem and D. C. Spencer, “On sets of integers which contain no three terms in arithmetical progression,”Proceedings of the National Academy of Sciences, vol. 28, no. 12, pp. 561–563, 1942

    1942

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.