Paper detail

Polynomial properties on large symmetric association schemes

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=θ_0>θ_1>\cdots>θ_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 $θ_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.