Distance Regular Graphs and the Bannai-Ito Conjecture

Specialeforsvar ved Thomas Møller Nielsen

Titel: Distance Regular Graphs and the Bannai-Ito Conjecture 

Abstract:  In this thesis we will study a class of graphs that are subject to high amounts of symmetry, namely the class of distance regular graphs. A graph $G$ is called distance regular if it is connected and satisfies that for any two vertices $u,v \in V(G)$ the number of vertices at distance $i$ from $u$ and at distance $j$ from $v$ depends only on $i,j$ and the the distance from $u$ to $v$ in $G$, and not on the choice of vertices. We will emphasize on giving the proof of the recently proven Bannai-Ito conjecture, stating that there are only finitely many distance regular graphs. In order to do so, we will review the needed basics of spectral graph theory and use this to derive some properties about the spectrum of a distance regular graph. More precisely we will study certain combinatorial parameters associated to a distance regular graph called the intersection numbers. These parameters will generate a sequence of polynomials uniquely, and this sequence turns out to fully determine the spectrum of the graph. Accordingly we shall study these parameters and the associated polynomials in the first part of the thesis, in the second part we will use the results to prove the Bannai-Ito conjecture. 

Vejleder: Bergfinnur Durhuus
Censor:   Tom Høholdt, DTU