New and explicit constructions of unbalanced Ramanujan bipartite graphs

DOI10.1007/S11139-021-00384-0zbMATH Open1484.05122arXiv1910.03937OpenAlexW3155663002MaRDI QIDQ2115273FDOQ2115273

M. Vidyasagar, Shantanu Prasad Burnwal, Kaneenika Sinha

Publication date: 15 March 2022

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exact matrix completion via convex optimization
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Eigenvalues and expanders
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• La conjecture de Weil. I
• Elementary number theory, cryptography and codes. Transl. from the Italian
• Ramanujan graphs
• On the minimum distance of array codes as LDPC codes
• Spectra of hypergraphs and applications
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• A proof of Alon’s second eigenvalue conjecture and related problems
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• On finding primitive roots in finite fields
• Some elementary Ramanujan graphs
• 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)
• Ramanujan coverings of graphs
• Shift lifts preserving Ramanujan property
• Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
• Explicit Construction of Ramanujan Bigraphs
• The Cayley Graphs Associated With Some Quasi-Perfect Lee Codes Are Ramanujan Graphs
• Ramanujan bigraphs associated with $SU(3)$ over a $p$-adic field
• Deterministic Completion of Rectangular Matrices Using Asymmetric Ramanujan Graphs: Exact and Stable Recovery

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)