A characterization of \(P\)- and \(Q\)-polynomial association schemes. (English) Zbl 0663.05016

Let \(Y=(X,(R_ i)\), \(0\leq i\leq d)\) be a symmetric \(d\)-class association scheme, with intersection numbers \(p^ h_{ij}\) and Krein parameters \(q^ h_{ij}\) (0\(\leq h,i,j\leq d)\), and for each \(i\) \((0\leq i\leq d)\) define the ith (reduced) intersection diagram \(D_ i\) (resp. representation diagram \(D^*_ i)\) on the nodes \(0,1,...,d\) drawing an undirected arc between any distinct \(h\), \(j\) for which \(p^ h_{ij}>0\) (resp. \(q^ h_{ij}>0)\). \(Y\) is called \(P\)-polynomial (resp. \(Q\)-polynomial) if some \(D_ i\) (resp. \(D^*_ i)\) is a path.We obtain pointwise semi-definite matrices \(G(i)\) and \(G(i)^*\) (0\(\leq i\leq d)\) that yield new inequalities for the \(p^ h_{ij}\) and \(q^ h_{ij}\). We show for each \(i\) \((0\leq i\leq d)\), \(D^*_ i\) being a forest, the vanishing of \(G(i)\), and the existence of a certain geometric representation of \(X\) are all equivalent. A similar result relates \(G(i)^*\) and \(D_ i\). Denoting by a leaf in any diagram a node adjacent to exactly one other, we show there is at most one leaf besides the \(O\)-node in any connected \(D^*_ i\) for a \(P\)-polynomial scheme. We combine this with the above results and get an interpretation of the \(Q\)-polynomial property for \(P\)-polynomial schemes. Finally, we use equations induced by the vanishing of some \(G(i)\) to obtain a simple proof of a theorem of D. Leonard, that the intersection numbers of a \(P\)- and \(Q\)-polynomial scheme can be found from 5 parameters.


05B30 Other designs, configurations
Full Text: DOI


[1] Bannai, E; Ito, T, Algebraic combinatorics I: association schemes, (), Menlo Park, Cal. · Zbl 0555.05019
[2] Biggs, N, Algebraic graph theory, (1974), Cambridge Univ. Press Cambridge · Zbl 0284.05101
[3] Bollobas, B, Graph theory, an introductory course, () · Zbl 0688.05016
[4] Delsarte, P, An algebraic approach to the association schemes of coding theory, Phillips res. rep. suppl., 10, (1973) · Zbl 1075.05606
[5] Egawa, Y, Characterization of H(n, q) by the parameters, J. combin. theory ser. A, 31, 108-125, (1981) · Zbl 0472.05056
[6] Huang, T, ()
[7] Lancaster, P, Theory of matrices, (1969), Academic Press New York/London · Zbl 0186.05301
[8] Leonard, D, Parameters of assocation schemes that are both P- and Q-polynomial, J. combin. theory ser. A, 36, 355-363, (1984) · Zbl 0533.05016
[9] {\scA. Neumaier}, A characterization of a class of distance-regular graphs, J. Reine Angew. Math., in press. · Zbl 0552.05042
[10] Sloane, N, An introduction to association schemes and coding theory, (), 225-260
[11] Sprague, A, Characterization of projective graphs, J. combin. theory ser. B, 24, 294-300, (1978) · Zbl 0321.05142
[12] Stanton, D, Some q-krawtchouk polynomials on Chevalley groups, Amer. J. math., 102, 625-662, (1980) · Zbl 0448.33019
[13] {\scP. Terwilliger}, A class of distance-regular graphs with the Q-polynomial property, submitted for publication.
[14] Terwilliger, P, Distance-regular graphs and generalizations, () · Zbl 0727.05050
[15] {\scP. Terwilliger}, Root systems and the Johnson and Hamming graphs, submitted for publication. · Zbl 0614.05048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.