Polynomial properties on large symmetric association schemes

DOI10.1007/S00026-016-0300-6zbMATH Open1339.05436arXiv1305.2539OpenAlexW1802317609MaRDI QIDQ295296FDOQ295296

Authors: Hiroshi Nozaki 

Publication date: 13 June 2016

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

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.

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

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

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)

Cites Work

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

Cited In (1)

• 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)