×

New and explicit constructions of unbalanced Ramanujan bipartite graphs. (English) Zbl 1484.05122

Summary: The objectives of this article are threefold. Firstly, we present for the first time explicit constructions of an infinite family of unbalanced Ramanujan bigraphs. Secondly, we revisit some of the known methods for constructing Ramanujan graphs and discuss the computational work required in actually implementing the various construction methods. The third goal of this article is to address the following question: can we construct a bipartite Ramanujan graph with specified degrees, but with the restriction that the edge set of this graph must be distinct from a given set of “prohibited” edges? We provide an affirmative answer in many cases, as long as the set of prohibited edges is not too large.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
05C31 Graph polynomials
68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., Eigenvalues and expanders, Combinatorica, 8, 2, 83-96 (1986) · Zbl 0661.05053 · doi:10.1007/BF02579166
[2] Babai, L.: Group, graphs, algorithms: the graph isomorphism problem. In: Proceedings of the International Congress of Mathematicians, pp. 3303-3320 (2018)
[3] Baldoni, MW; Ciliberto, C.; Cattaneo, GMP, Elementary Number Theory, Cryptography and Codes (2009), New York: Springer, New York · Zbl 1162.11001 · doi:10.1007/978-3-540-69200-3
[4] Ballantine, C.; Ciubotaru, D., Ramanujan bigraphs associated with \(SU(3)\) over a \(p\)-adic field, Proc Am Math Soc, 139, 6, 1939-1953 (2011) · Zbl 1281.22006 · doi:10.1090/S0002-9939-2011-10856-6
[5] Ballantine, C., Feigon, B., Ganapathy, R., Kool, J., Maurischat, K., Wooding, A.: Explicit construction of Ramanujan bigraphs. In: Women in Numbers in Europe, pp. 1-16. Springer (2015) · Zbl 1376.11023
[6] Bibak, K.; Kapron, BM; Srinivasan, V., The Cayley graphs associated with some quasi-perfect Lee codes are Ramanujan graphs, IEEE Trans. Inf. Theory, 62, 11, 6355-6358 (2016) · Zbl 1359.94783 · doi:10.1109/TIT.2016.2595778
[7] Brito, G., Dumitriu, I., Harris, K.D.: Spectral gap in random bipartite biregular graphs and applications. arxiv:1804.07808 (2018)
[8] Burnwal, SP; Vidyasagar, M., Deterministic completion of rectangular matrices using asymmetric Ramanujan graphs: exact and stable recovery, IEEE Trans. Signal Process., 68, 3834-3848 (2020) · Zbl 07591003 · doi:10.1109/TSP.2020.2997180
[9] Candès, E.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772 (2008) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[10] Chandrasekaran, K.; Velingker, A., Shift lifts preserving Ramanujan property, Linear Algebra Appl., 529, 199-214 (2017) · Zbl 1366.05067 · doi:10.1016/j.laa.2017.04.031
[11] Cohen, M.B.: Ramanujan graphs in polynomial time. arXiv:1604.03544v1
[12] Davidoff, G.; Sarnak, P.; Valette, A., Elementary Number Theory, Group Theory, and Ramanujan Graphs (2003), Cambridge: Cambridge University Press, Cambridge · Zbl 1032.11001
[13] Deligne, P., La conjecture de Weil. I. (French). Institut des Hautes Études Scientifiques, Publications Mathématiques, 43, 273-307 (1974) · Zbl 0287.14001 · doi:10.1007/BF02684373
[14] Evra, S., Parzanchevski, O.: Ramanujan complexes and golden gates in \(PU(3)\). arxiv:1810:04710v1 (2018)
[15] Fan, J.L.: Array codes as LDPC codes. In: Proceedings of 2nd International Symposium on Turbo Codes, pp. 543-546 (2000)
[16] Feng, K.; Li, W-CW, Spectra of hypergraphs and applications, J. Number Theory, 60, 1, 1-22 (1996) · Zbl 0874.05041 · doi:10.1006/jnth.1996.0109
[17] Friedman, J.: A proof of Alon’s second eigenvalue conjecture. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 720-724 (2003) · Zbl 1192.05087
[18] Friedman, J., A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Am. Math. Soc., 195, 910, 1-3 (2008) · Zbl 1177.05070
[19] Gunnells, P., Some elementary Ramanujan graphs, Geom. Dedicata., 112, 51-63 (2005) · Zbl 1074.05046 · doi:10.1007/s10711-005-0549-0
[20] Hall, C.; Puder, D.; Sawin, WF, Ramanujan coverings of graphs, Adv. Math., 323, 367-410 (2018) · Zbl 1375.05213 · doi:10.1016/j.aim.2017.10.042
[21] Li, W-CW, Character sums and Abelian Ramanujan graphs, J. Number Theory, 41, 199-217 (1992) · Zbl 0760.11040 · doi:10.1016/0022-314X(92)90120-E
[22] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 3, 261-277 (1988) · Zbl 0661.05035 · doi:10.1007/BF02126799
[23] Marcus, A., Spielman, D.A., Srivastava, N.: Interlacing families I: Bipartite Ramanujan graphs of all degrees. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 529-537 (2013) · Zbl 1316.05066
[24] Marcus, A.; Spielman, DA; Srivastava, N., Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. Math., 182, 1, 307-325 (2015) · Zbl 1316.05066 · doi:10.4007/annals.2015.182.1.7
[25] Marcus, A., Spielman, D.A., Srivastava, N.: Interlacing families IV: Bipartite Ramanujan graphs of all sizes. In: 2015 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 1358-1367 (2015) · Zbl 1409.05185
[26] Margulis, GA, Explicit group theoretical constructions of combinatorial schemes and their application in the construction of expanders and concentrators (English translation), Problemy Peredachi Informatsii, 24, 1, 51-60 (1988) · Zbl 0708.05030
[27] Morgenstern, M., Existence and explicit constructions of \(q + 1\) regular Ramanujan graphs for every prime power \(q\), J. Comb Theory Series B, 62, 1, 44-62 (1994) · Zbl 0814.68098 · doi:10.1006/jctb.1994.1054
[28] Murty, MR, Ramanujan graphs, J. Ramanujan Math. Soc., 18, 1, 1-20 (2003) · Zbl 1038.05038
[29] Recht, B.; Fazel, M.; Parrilo, P., Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[30] Shparlinski, I., On finding primitive roots in finite fields, Theoret. Comput. Sci., 157, 2, 273-275 (1996) · Zbl 0871.11091 · doi:10.1016/0304-3975(95)00164-6
[31] Tattersall, J., Elementary Number Theory in Nine Chapters (1999), Cambridge: Cambridge University Press, Cambridge · Zbl 0958.11001 · doi:10.1017/CBO9780511756351
[32] Yang, K.; Helleseth, T., On the minimum distance of array codes as LDPC codes, IEEE Trans. Inf. Theory, 49, 12, 3268-3271 (2003) · Zbl 1286.94113 · doi:10.1109/TIT.2003.820053
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.