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 e i} frac{theta_0-theta_j}{theta_i-theta_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.
Download