A connection between a question of Bermond and Bollobas and Ramanujan graphs

If we let n(k, d) denote the order of the largest undirected graphs of maximum degree k and diameter d, and let M(k,d) denote the corresponding Moore bound, then n(k,d)leq M(k,d), for all kgeq 3, dgeq 2. Whilethe inequality has been proved strict for all but very few pairs k and d, the exact relation between the values n(k,d) and M(k,d) is unknown, and the uncertainty of the situation is captured by an open question of Bermond and Bollobas who asked whether it is true that for any positive integer c>0 there exist a pair k and d, such that n(k,d)leq M(k,d)-c.

In this talk we present a  connection of this question to the value 2sqrt{k-1}, which is also essential in the definition of the Ramanujan graphs defined as k-regular graphs whose second largest eigenvalue (in modulus) does not exceed 2sqrt{k-1}. We further reinforce this surprising connection by showing that if the answer to the question of Bermond and Bollobas were negative and there existed a c > 0 such that n(k,d) geq M(k,d) – c, for all kgeq 3, dgeq 2, then, for any fixed k and all sufficiently large even d's, the largest undirected graphs of degree k and diameter d would have to be Ramanujan graphs. This would imply a positive answer to the open question whether infinitely many non-bipartite k-regular Ramanujan graphs exist for any degree k.