A construction of random bigraphs and their application to error correction codes*
Hareshkumar Jadav, Ashita Gupta, Ranveer Singh · Journal of Statistical Mechanics Theory and Experiment · 2025
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 c , d ⩾ 3 . In this article, we give a construction of an infinite sequence of random (c, d)-biregular graphs G k , k = 1 , 2 , … , ∞ , where G k + 1 can be constructed from Gk 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.