Polynomial properties on large symmetric association schemes

DOI10.1007/S00026-016-0300-6MaRDI QIDQ295296zbMATH OpenOpenAlexFDO

Authors Hiroshi Nozaki

Publication date 13 June 2016

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2539

zbMATH Keywords

graph spectrumMoore bound\(s\)-distance setabsolute boundpolynomial association scheme

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Distance in graphs (05C12)

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=het{a}_0>het{a}_1>cdots>het{a}_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 $het{a}_i$. Let $partial(u,v)$ be the path distance of $u,vinV$. Theorem. Assume $|V|>M(k,d-1)$ holds. Then for $x,yinV$ 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{ heta_0- heta_j}{ heta_i- heta_j}. ] If a symmetric association scheme $mathfrakX=(X,{R_i}_{i=0}^d)$ has a relation $R_i$ such that the graph $(X,R_i)$ satisfies the above condition, then $mathfrakX$ is $P$-polynomial. Moreover we show the "dual" version of this theorem for spherical sets and $Q$-polynomial association schemes.

Recommendations

• A characterization of \(P\)- and \(Q\)-polynomial association schemes
• A remark on association schemes with two P-polynomial structures
• Bounds on special subsets in graphs, eigenvalues and association schemes
• A spectral equivalent condition of the P-polynomial property for association schemes
• scientific article; zbMATH DE number 863484

Cites work

• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• A characterization of \(Q\)-polynomial association schemes
• A generalization of Larman-Rogers-Seidel's theorem
• A spectral equivalent condition of the P-polynomial property for association schemes
• An excess theorem for spherical 2-designs
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• Linear programming bounds for regular graphs
• Some spectral and quasi-spectral characterizations of distance-regular graphs
• Spherical codes and designs
• Tridiagonal matrices with nonnegative entries
• Two-point homogeneous spaces
• Universally optimal distribution of points on spheres

Cited in

(2)

• A spectral equivalent condition of the P-polynomial property for association schemes
• On symmetric association schemes and associated quotient-polynomial graphs

This page was built for publication: Polynomial properties on large symmetric association schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q295296)