A construction of random bigraphs and their application to error correction codes^*

Abstract Recently, it has been shown that almost every ( c , d )-bigraph is ‘almost’ Ramanujan. Marcus, Spielman, and Srivastava also demonstrated the existence of infinite sequence of ( c , d )-bigraphs that are Ramanujan for all <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> <mml:mtext>⩾</mml:mtext> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> . In this article, we give a construction of an infinite sequence of random ( c , d )-biregular graphs <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi mathvariant="normal">∞</mml:mi> </mml:mrow> </mml:math> , where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msub> <mml:mi>G</mml:mi> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> can be constructed from G k in constant time. Experimental results show that they tend to be Ramanujan graphs in very few iterations. Additionally, we use this sequence of random ( c , d )-biregular graphs as an error-correcting code proposed by Sipser and Spielman. Experimental results suggest that our graphs, when combined with a bit-flipping algorithm, can successfully correct a significant fraction of errors.