New and Explicit Constructions of Unbalanced Ramanujan Bipartite Graphs

Autor:	Burnwal, Shantanu Prasad, Sinha, Kaneenika, Vidyasagar, Mathukumalli
Rok vydání:	2019
Předmět:	Statistics - Machine Learning Computer Science - Machine Learning Mathematics - Combinatorics Mathematics - Number Theory
Druh dokumentu:	Working Paper
Popis:	The objectives of this article are three-fold. Firstly, we present for the first time explicit constructions of an infinite family of \textit{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. Comment: This paper is a partial replacement of 1910.03937v1. The phase transition part of 1910.03937v1 will be uploaded as a separate submission
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1910.03937 Zobrazit plný text záznamu View this record from Arxiv