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=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.

تحميل البحث