Ramanujan Graphs and the Matrix Completion Problem by Prof. M. Vidyasagar FRS (IIT Hyderabad)

Graphs consist of vertices, and edges between vertices. A graph is said to be d-regular if every vertex has degree d, that is, exactly d other vertices connected to it. For each graph one can associate an Adjacency matrix A, of size n by n where n is the number of vertices. If the graph is d-regular, then d is always an eigenvalue of A. Such a graph is called a “Ramanujan graph” if the second largest eigenvalue of A is no larger than twice the square root of d-1. In this talk I will explain where this rather strange-looking bound comes from, and show that in fact it is the best one can achieve in any graph as n becomes large. Explicit constructions of Ramanujan graphs are still very few, and I will provide a couple of such procedures. Finally, I will discuss the “matrix completion problem” which has applications in many engineering domains, and show how it can be solved using Ramanujan graphs.

[@samirahmad1559]

can i have the ppt please