# Suzuki, Hiroshi; Matematični kolokvij julij 2009

## An introduction to algebraic graph theory (Spectrum, Terwilliger algebra and its generalization)

Hiroshi Suzuki

International Christian University, Mitaka, Tokio, Japonska

23. julij 2009

In algebraic graph theory, we study structures of graphs by properties of algebraic objects associated to them. The first one to look at is the spectrum of a graph. But it turns out that many basic properties cannot be retrieved from its spectrum.

In 70s Delsarte developed an algebraic theory of a subset Y of the base set X of a symmetric association scheme $\mathcal{X} = (X,\{R_{i}\}_{0\leq i\leq d})$. His theory was successfully applied to design theory and coding theory. In 90s Terwilliger defined the subconstituent algebra of an association scheme, which is also called the Terwilliger algebra. The Terwilliger algebra was successfully applied mainly to P- and Q-polynomial association schemes.

Recently in a paper titled Width and dual width of subsets in polynomial association schemes", Brouwer, Godsil, Koolen and Martin studied the theory of a subset of the base set of a P- and/or Q-polynomial association scheme from a view point different from Delsarte.

In this talk, we define the Terwiliger algebra of a polynomial space consisting of a Hermitian matrix $A\in \mathrm{Mat}_n(\boldsymbol C)$ and an orthogonal direct sum decomposition of the Hermitian space $V = \boldsymbol{C}^n$ into subspaces $V_0, V_1, \ldots, V_t$ satisfying

$AV_i \subset V_{i-1} + V_i + V_{i+1}, \mbox{ for all } i\in \{0, 1, \ldots, t\}$
with $V_{-1} = V_{t+1} = \boldsymbol 0$. We develop basic theory and introduce results on thin irreducible modules and the shortest modules. These results give a partial generalization of the theory developed by Brouwer, Godsil, Koolen and Martin.