# Graphs, groups, and more: celebrating Brian Alspach’s 80th and Dragan Marušič’s 65th birthdays

28 May 2018 to 1 June 2018
Koper
UTC timezone

## Bermond/Bollobas Problem and Ramanujan Graphs

Not scheduled
15m
UP FHS (Koper)

### UP FHS

#### Koper

Titov trg 5,Koper

### Speaker

Prof. Robert Jajcay (Comenius University, Bratislava, and University of Primorska, Koper)

### Description

If we denote by $n(k, d)$ 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 $k \geq 3, d \geq 2$. While the inequality has been proven 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 a question of Bermond and Bollobas who asked whether it is true that for any a positive integer $c>0$ there exist a pair $k$ and $d$, such that $n(k, d)\leq M(k,d)-c$. We show a surprising connection of this question to the value $2\sqrt{k-1}$, which is also essential in the definition of the Ramanujan graphs which are $k$-regular graphs having the property that their second largest eigenvalue (in modulus) does not exceed $2 \sqrt{k-1}$. We further reinforce this surprising connection by showing an interesting consequence of a negative answer to the problem of Bermond and Bollobas. Namely, we show that if there exists a $c > 0$ such that $n(k,d) \geq M(k,d) - c$, for all $k \geq 3, d \geq 2$, then for any fixed $k$ and all sufficiently large $d$'s, the largest undirected graphs of degree $k$ and diameter $d$ must be Ramanujan graphs. Since Ramanujan graphs are scarce, our result seems to suggest a positive answer to the question of Bermond and Bollobas. This is a joint work with Slobodan Filipovski.

### Primary author

Prof. Robert Jajcay (Comenius University, Bratislava, and University of Primorska, Koper)

### Co-author

Mr Slobodan Filipovski (University of Primorska, Koper)

### Presentation Materials

There are no materials yet.