Asymptotics for Tanner graphs with cycles

It is obvious from Theorem 3.6 that Tanner graphs without cycles cannot support asymptotically good codes. Starting with Theorem 3.6, it is not difficult to show that the same is true for Tanner graphs with cycles, unless the number of cycles increases exponentially with the length of the code as n$\to$$\infty$. To see this, suppose the the cycle rank of a Tanner graph T = (V, E) representing an (n, k, d ) code $\ensuremath{\mathbb{C}}$ is c = | E| - | V| + $\omega$(T). This means that T contains 2^c cycles and unions of disjoint cycles (cf. [48, p.137]). Now let x_i be a symbol vertex that lies on a cycle in T. Then removing x_i and all the edges incident on x_i from T produces a graph whose cycle rank is strictly less than c. This procedure is equivalent to shortening $\ensuremath{\mathbb{C}}$ at the i-th position to obtain an (n', k', d') code $\ensuremath{\mathbb{C}}'$ with n' = n - 1, k'$\ge$k - 1, and d'$\ge$d. Since the cycle rank strictly decreases each time we cut a cycle in T in this way, after repeating this procedure t$\le$c times we obtain a cycle-free code $\ensuremath{\mathbb{C}}^*$. Clearly $\ensuremath{\mathbb{C}}^*$ is an (n^*, k^*, d^*) code with n^* = n - t, k^*$\ge$k - t, and d^*$\ge$d. Thus Theorem 3.6 implies

$$\le \le \left\lfloor\vphantom{{n^* \over k^*+1}}\right. {n^* \over k^*+1} \left.\vphantom{{n^* \over k^*+1}}\right\rfloor \le {n - t \over k - t+1}$$ (9)

Now let $\gamma$ = c/n, and notice that t/n$\le$$\gamma$. Hence if $\lim_{{n \to \infty}}^{}$$\gamma$ = 0, then (3.21) asymptotically reduces to d $\lesssim$ 2/R, as in (3.1). Thus to support an asymptotically good sequence of codes, c must grow linearly with n, which means that the number of cycles 2^c grows exponentially with n. It would be useful to find out how the parameter $\gamma$ = c/n, which has to do with the number of cycles, trades off versus the traditional asymptotic parameters $\delta$ = d /n and R = k/n as n$\to$$\infty$. It would be also interesting to investigate, at least asymptotically, codes that have Tanner graphs of prescribed minimum girth.