New and explicit constructions of unbalanced Ramanujan bipartite graphs

DOI10.1007/S11139-021-00384-0MaRDI QIDQ2115273zbMATH OpenOpenAlexFDO

Authors Shantanu Prasad Burnwal, Kaneenika Sinha, M. Vidyasagar

Publication date 15 March 2022

Published in The Ramanujan Journal (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.03937

zbMATH Keywords

computational complexityexplicit constructionRamanujan graphs

Mathematics Subject Classification ID

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

Abstract: The objectives of this article are three-fold. Firstly, we present for the first time explicit constructions of an infinite family of extit{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.

Recommendations

• Explicit construction of Ramanujan bigraphs
• Interlacing families. IV: Bipartite Ramanujan graphs of all sizes
• scientific article; zbMATH DE number 1376670
• scientific article; zbMATH DE number 1552122
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees

Cites work

• scientific article; zbMATH DE number 2042680 (Why is no real title available?)
• scientific article; zbMATH DE number 1470721 (Why is no real title available?)
• scientific article; zbMATH DE number 1849959 (Why is no real title available?)
• A proof of Alon’s second eigenvalue conjecture and related problems
• A proof of alon's second eigenvalue conjecture
• Character sums and abelian Ramanujan graphs (with an appendix by Keqin Feng and Wen-Ch'ing Winnie Li)
• Deterministic Completion of Rectangular Matrices Using Asymmetric Ramanujan Graphs: Exact and Stable Recovery
• Eigenvalues and expanders
• Elementary number theory, cryptography and codes. Transl. from the Italian
• Exact matrix completion via convex optimization
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit construction of Ramanujan bigraphs
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. IV: Bipartite Ramanujan graphs of all sizes
• La conjecture de Weil. I
• On finding primitive roots in finite fields
• On the minimum distance of array codes as LDPC codes
• Ramanujan bigraphs associated with \(\mathrm{SU}(3)\) over a \(p\)-adic field
• Ramanujan coverings of graphs
• Ramanujan graphs
• Shift lifts preserving Ramanujan property
• Some elementary Ramanujan graphs
• Spectra of hypergraphs and applications
• The Cayley Graphs Associated With Some Quasi-Perfect Lee Codes Are Ramanujan Graphs

Cited in

(3)

• Explicit construction of Ramanujan bigraphs
• Explicit bounded-degree unique-neighbor concentrators
• Interlacing families. IV: Bipartite Ramanujan graphs of all sizes

This page was built for publication: New and explicit constructions of unbalanced Ramanujan bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115273)