<p>Your question is somewhat ill-posed: given <span class="math-container">$n$</span> and <span class="math-container">$k$</span>, it is easy to construct a Tanner graph with a 4-cycle and column weight at most 2.</p>

<p>Instead, you can ask the question of what is the maximum column weight of a Tanner graph, given that is has no 4-cycle. Assuming uniform column weights, then the maximum column weight is <span class="math-container">$O(\sqrt{k})$</span>. This is known as the Kővári–Sós–Turán theorem (see e.g. <a href="https://en.wikipedia.org/wiki/Zarankiewicz_problem#Upper_bounds" rel="nofollow noreferrer">here</a>), which states that the number of edges in an <span class="math-container">$(n,k)$</span>-bipartite graph without 4-cycle is at most
<span class="math-container">$$
(n-1)\sqrt{k} + k.
$$</span>
If the Tanner graph has uniform column weights <span class="math-container">$d$</span>, then it has <span class="math-container">$nd$</span> edges, which gives the bound on <span class="math-container">$d$</span>.</p>

<p>This is tight up to constants for the case where <span class="math-container">$k = n$</span> (see e.g. <a href="https://en.wikipedia.org/wiki/Zarankiewicz_problem#Lower_bounds" rel="nofollow noreferrer">here</a>).</p>

CC BY-SA 4.0
2020-02-19T12:45:37.830Z
By allowed I meant max weight. Anyway, the fact that this expression doesn't have $k$ in it is making me a little worried. I think in the form the answer is, it gives freedom to select any $k$ and then solve for max t for given $n$.
Root
CC BY-SA 4.0
2020-02-19T12:47:50.593Z
I agree, if $k$ is small then the bound should be smaller. As I mention, the bound is tight up to constant when $k = n$.
smapers
CC BY-SA 4.0
2020-02-19T12:56:11.960Z
I improved to answer.
smapers
CC BY-SA 4.0
2020-02-19T12:33:07.600Z
2020-02-19T12:55:30.297Z
2020-02-19T12:55:30.297Z
smapers
<p>Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles in tanner graph, in particular length 4 cycles are to be avoided. Naturally, this puts some bound on column weight in such a parity matrix. What is the general column weight <span class="math-container">$t$</span> that is allowed (in terms of code dimensions <span class="math-container">$k,n$</span>) so that there are no 4-cycles?  </p>

<p>To state it formally</p>

<p>given n and k what is maximum value of <span class="math-container">$t$</span> for which tanner graph (bipartite t regular) has no 4 cycle? </p>

<co.combinatorics><coding-theory><combinatorics>
weights in low density codes
Root
# weights in low density codes

(Asked by: username_0 on 2020-02-19)

Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles in tanner graph, in particular length 4 cycles are to be avoided. Naturally, this puts some bound on column weight in such a parity matrix. What is the general column weight $t$ that is allowed (in terms of code dimensions $k,n$) so that there are no 4-cycles?

To state it formally

given n and k what is maximum value of $t$ for which tanner graph (bipartite t regular) has no 4 cycle?

**Tags:** co.combinatorics, coding-theory, combinatorics

---

## 1 answers

### Answer by username_1 on 2020-02-19. Score: 1 | Accepted answer

Your question is somewhat ill-posed: given $n$ and $k$, it is easy to construct a Tanner graph with a 4-cycle and column weight at most 2.

Instead, you can ask the question of what is the maximum column weight of a Tanner graph, given that is has no 4-cycle. Assuming uniform column weights, then the maximum column weight is $O(\sqrt{k})$. This is known as the Kővári–Sós–Turán theorem (see e.g. [here](https://en.wikipedia.org/wiki/Zarankiewicz_problem#Upper_bounds)), which states that the number of edges in an $(n,k)$-bipartite graph without 4-cycle is at most
$$
(n-1)\sqrt{k} + k.
$$
If the Tanner graph has uniform column weights $d$, then it has $nd$ edges, which gives the bound on $d$.

This is tight up to constants for the case where $k = n$ (see e.g. [here](https://en.wikipedia.org/wiki/Zarankiewicz_problem#Lower_bounds)).

> **Comments:**
> **username_0**: By allowed I meant max weight. Anyway, the fact that this expression doesn't have $k$ in it is making me a little worried. I think in the form the answer is, it gives freedom to select any $k$ and then solve for max t for given $n$.  
> **username_1**: I agree, if $k$ is small then the bound should be smaller. As I mention, the bound is tight up to constant when $k = n$.  
> **username_1**: I improved to answer.  

---

