Seminar: May 1
John Wilmes, University of Chicago
On the Banni-Ito conjecture on distance-regular graphs
A graph is distance-transitive if whenever two ordered pairs of vertices, (x,y) and (u,v), are at equal distance, they are equivalent under the automorphism group. In 1983, Cameron, Praeger, Saxl, and Seitz proved, using the classification of finite simple groups, that for every k greater than 2, there are only finitely many distance-transitive graphs of valency k. Distance-regularity is a combinatorial relaxation of distance-transitivity: a graph is distance-regular if for every triple (h,i,j) of positive integers there is an integer p(h,i,j) such that for every pair (x,y) of vertices at distance h, the number of vertices z at distance i from x and at distance j from y is p(h,i,j).
A long-standing conjecture in algebraic graph theory, referred to as the Bannai--Ito conjecture (1984), states that the CPSS result extends to distance-regular graphs: there are only finitely many distance-regular graphs of any fixed valency k greater than 2. A. A. Ivanov proved the conjecture for triangle-free graphs of bounded girth (1982). Bannai and Ito verified the conjecture for bipartite graphs and for graphs of valency at most 4. Bang, Dubickas, Koolen, and Moulton recently announced a proof of the full conjecture (see http://arXiv.org/abs/0909.5253 ) based on an intricate analysis of the interaction between the "intersection numbers" p(h,i,j) and the eigenvalues of the adjacency matrix of the graph.
In this talk, I will review the classical theory of distance-regular graphs and discuss some of the techniques used by BDKM.