Polynomial properties on large symmetric association schemes

Abstract

In this paper we characterize "large" regular graphs using certain entries in the projection matrices onto the eigenspaces of the graph. As a corollary of this result, we show that "large" association schemes become $P$-polynomial association schemes. Our results are summarized as follows. Let $G=(V,E)$ be a connected $k$-regular graph with $d+1$ distinct eigenvalues $k={\theta }_0>{\theta }_1>\cdots >{\theta }_d$. Since the diameter of $G$ is at most $d$, we have the Moore bound \[ |V| \leq M(k,d)=1+k \sum_{i=0}^{d-1}(k-1)^i. \] Note that if $|V|>M(k,d-1)$ holds, the diameter of $G$ is equal to $d$. Let $E_i$ be the orthogonal projection matrix onto the eigenspace corresponding to ${\theta }_i$. Let $\partial (u,v)$ be the path distance of $u,v\in V$. Theorem. Assume $|V|>M(k,d-1)$ holds. Then for $x,y\in V$ with $\partial (x,y)=d$, the $(x,y)$-entry of $E_i$ is equal to \[ -\frac{1}{|V|}\prod_{j=1,2,\ldots,d, j \ne i} \frac{θ_0-θ_j}{θ_i-θ_j}. \] If a symmetric association scheme $\mathfrak{X}=(X,\{R_i{\}}_{i=0}^d)$ has a relation $R_i$ such that the graph $(X,R_i)$ satisfies the above condition, then $\mathfrak{X}$ is $P$-polynomial. Moreover we show the "dual" version of this theorem for spherical sets and $Q$-polynomial association schemes.

9 pages, no figure

References in corpus (2)

• Some Spectral and Quasi-Spectral Characterizations of Distance-Regular Graphs
• Linear programming bounds for regular graphs