Computer and Mathematical Sciences

Mathematical Structures III A03

  • Prof. Hajime Tanaka      
KeywordsAlgebraic Graph Theory, Algebraic Combinatorics, Discrete Mathematics

Algebraic graph theory and related areas

Our lab specializes in algebraic graph theory, which studies finite graphs in terms of the associated real symmetric matrices, especially using their eigenvalues and eigenvectors. We mainly discuss highly regular graphs, such as distance-regular graphs and association schemes. Our study extends to random walks and quantum walks on graphs, the latter of which is an area evolving explosively in the 21st century. Viewing matrices associated with graphs as random variables also relates algebraic graph theory to quantum (or noncommutative) probability theory. In this context, an attractive theme is to consider analogs of the Central Limit Theorem for families of graphs. On the other hand, we also study various discrete objects like codes and designs by viewing them as subsets of the vertex sets of appropriate graphs (or association schemes). This line of research, originating from Philippe Delsarte's Ph.D. thesis in 1973, combines algebraic graph theory with tools from optimization, such as linear programming and semidefinite programming.

  • Normalized joint spectral distributions of Cartesian powers of Paley graphs Paley(q) and their complements