# zbMATH — the first resource for mathematics

The subconstituent algebra of an association scheme. I. (English) Zbl 0785.05089
From the author’s abstract: We introduce a method for studying commutative association schemes with “many” vanishing intersection numbers and/or Krein parameters, and apply the method to the $$P$$- and $$Q$$-polynomial schemes. Let $$Y$$ denote any commutative association scheme, and fix any vertex $$x$$ of $$Y$$. We introduce a non-commutative, associative, semi-simple $$\mathbb{C}$$-algebra $$T=T(x)$$ whose structure reflects the combinatorial structure of $$Y$$. We call $$T$$ the subconstituent algebra of $$Y$$ with respect to $$x$$. Roughly speaking, $$T$$ is a combinatorial analog of the centralizer algebra of the stabilizer of $$x$$ in the automorphism group of $$Y$$.
In general, the struture of $$T$$ is not determined by the intersection numbers of $$Y$$, but these parameters do give some information. Indeed, we find a relation among the generators of $$T$$ for each vanishing intersection number or Krein parameter.
We identify a class of irreducible $$T$$-modules whose structure is especially simple, and say the members of this class are thin. Expanding on this, we say $$Y$$ is thin if every irreducible $$T(y)$$-module is thin for every vertex $$y$$ of $$Y$$. We compute the possible thin, irreducible $$Y$$-modules when $$Y$$ is $$P$$- and $$Q$$-polynomial. The ones with sufficiently large dimension are indexed by four bounded integer parameters. If $$Y$$ is assumed to be thin, then “sufficiently large dimension” means “dimension at least four”.
We give a combinatorial characterization of the thin $$P$$- and $$Q$$- polynomial schemes, and supply a number of examples of these objects. For each example, we show which irreducible $$T$$-modules actually occur.
We close with some conjectures and open problems.

##### MSC:
 05E30 Association schemes, strongly regular graphs 05C12 Distance in graphs
Full Text:
##### References:
  Askey, R.; Wilson, J., A set of orthogonal polynomials that generalize the Racah coefficients on $$6-j$$ symbols, SIAM J. Math. Anal., 10, 1008-1016, (1979) · Zbl 0437.33014  R. Askey, J. Wilson, “Some basic hypergeometric orthogonal polynomials that generalize the Jacobi polynomials,” Mem. Amer. Math. Soc.319, 1985. · Zbl 0572.33012  E. Bannai, T. Ito, “Algebraic Combinatorics I: Association Schemes,” Benjamin-Cummings Lecture Note 58. Menlo Park, 1984.  Bannai, E.; Ito, T., Current researches on algebraic combinatorics, Graphs Combin., 2, 287-308, (1986) · Zbl 0685.05030  E. Bannai, “On extremal finite sets in the sphere and other metric spaces, algebraic, extremal and metric combinatorics,” 1986 (Montreal, PQ, 1986), 13-38, London Math. Soc. Lecture Note Ser., 131, Cambridge Univ. Press, Cambridge-New York, 1988.  Bannai, E.; Nevai, Paul (ed.), Orthogonal polynomials in coding theory and algebraic combinatorics, 25-53, (1990), Boston  Bier, T., Lattices associated to the Rectangular Association Scheme, Ars Combin., 23A, 41-50, (1987) · Zbl 0624.05021  Bier, T., Totient-numbers of the rectangular association scheme, Graphs Combin., 6, 5-15, (1990) · Zbl 0696.05013  Biggs, N., Some Odd graph theory, Ann. New York Acad. Sci., 319, 71-81, (1979)  J. Van Bon, “Affine distance-transitive groups,” thesis, C.W.I., The Netherlands, 1990.  A. Brouwer, A. Cohen, A. Neumaier, Distance-Regular Graphs, Springer Verlag, New York, 1989.  Brouwer, A.; Hemmeter, J., A new family of distance-regular graphs and the (0,1,2)-cliques in dual polar graphs, European J. Combin., 13, 71-79, (1992) · Zbl 0762.05041  Calderbank, A.; Delsarte, P.; Sloane, N., A strengthening of the Assmus-Mattson theorem, IEEE Trans. Inform. Theory, 37, 1261-1268, (1991) · Zbl 0734.94018  A. Calderbank, P. Delsarte, “The concept of a $$(t, r)$$-regular design as an extension of the classical concept of a t-design,” preprint. · Zbl 0783.05028  A. Calderbank, P. Delsarte, “On error-correcting codes and invariant linear forms,” preprint. · Zbl 0768.94020  Cameron, P., Dual polar spaces, Geom. Dedicata, 12, 75-85, (1982) · Zbl 0473.51002  Cameron, P.; Goethals, J.; Seidel, J., The Krein condition, spherical designs, Norton algebras, and permutation groups, Indag. Math., 40, 196-206, (1978) · Zbl 0399.20001  S. Y. Choi, “An upper bound on the diameter of certain distance-regular graphs.” Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989). Congr. Numer. 70 (1990), 195-198.  Clayton, R., Perfect multiple coverings in metric schemes, No. 20, 51-64, (1990), New York-Berlin  C. Curtis, I. Reiner, “Representation Theory of Finite Groups and Associative Algebras”, Interscience, New York, 1962. · Zbl 0131.25601  C. Delorme, “Distance bi-regular bipartite graphs,” European J. Combin., submitted. · Zbl 0804.05031  P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Res. Reports Suppl.10 (1973).  Delsarte, P., Association schemes and $$t$$-designs in regular semi-lattices, J. Combin. Theory Ser. A, 20, 230-243, (1976) · Zbl 0342.05020  Doob, M., On graph products and association schemes, Utilitas Math., 1, 291-302, (1972) · Zbl 0315.05130  Dunkl, C., An addition theorem for some $$q$$-Hahn polynomials, Monatsh. Math., 85, 5-37, (1977) · Zbl 0345.33010  Egawa, Y., Association schemes of quadratic forms, J. Combin. Theory Ser. A, 38, 1-14, (1985) · Zbl 0564.05014  Egawa, Y., Characterization of $$H(n, q)$$ by the parameters, J. Combin. Theory Ser. A, 31, 108-125, (1981) · Zbl 0472.05056  Faradzhev, I.; Ivanov, A. A., Distance-transitive representations of groups $$G$$ with PSL$$\_{}\{2\}(q) {ie386-1} G$$ie386-2 PΓL$$\_{}\{2\}(q),$$ European J. Combin., 11, 347-356, (1990)  Faradzhev, I.; Ivanov, A. A.; Klin, M., Galois correspondence between permutation groups and cellular rings (association schemes), Graphs Combin., 6, 303-332, (1990) · Zbl 0764.05099  Gasper, G.; Rahman, M., Basic hypergeometric series, (1990), Cambridge · Zbl 0695.33001  Godsil, C.; Shawe-Taylor, J., Distance-regularized graphs are distance-regular or distance-biregular, J. Combin. Theory Ser. B, 43, 14-24, (1987) · Zbl 0616.05041  Hemmeter, J., The large cliques in the graph of quadratic forms, European J. Combin., 9, 395-410, (1988) · Zbl 0672.05044  Hemmeter, J.; Woldar, A., Classification of the maximal cliques of size ≥$$q + 4$$ in the quadratic forms graph in odd characteristic, European J. Combin., 11, 433-450, (1990) · Zbl 0762.05089  Hemmeter, J.; Woldar, A., On the maximal cliques of the quadratic forms graph in even characteristic, European J. Combin., 11, 119-126, (1990) · Zbl 0717.05040  Huang, T., A characterization of the association schemes of bilinear forms, European J. Combin., 8, 159-173, (1987) · Zbl 0675.05064  Huang, T., Further results on the E-K-R theorem for the distance regular graphs $$H\_{}\{q\}(k,n),$$ Bull. Inst. Math. Acad. Sinica, 16, 347-356, (1988) · Zbl 0711.05044  T. Huang and M. Laurant, “$$(s,r$$:μ)-nets and alternating forms graphs,” submitted.  Ito, T.; Munemasa, A.; Yamada, M., Amorphous association schemes over the Galois rings of characteristic 4, European J Combin., 12, 513-526, (1991) · Zbl 0762.05098  Ivanov, A. A., Distance-transitive graphs that admit elations, Izv. Akad. Nauk SSSR Ser. Mat., 53, 971-1000, (1989)  Ivanov, A.; Muzichuk, M.; Ustimenko, V., On a new family of $$(P$$ and $$Q)$$-polynomial schemes, European J. Combin., 10, 337-345, (1989) · Zbl 0709.05015  Ivanov, A.; Shpektorov, S., The association schemes of the dual polar spaces of type $$2A\_{}\{\textit{2d}−1\}(p f)$$ are characterized by their parameters if $$d$$≥ 3, Linear Algebra Appl., 114, 133-139, (1989)  Ivanov, A.; Shpektorov, S., Characterization of the association schemes of Hermitian forms over GF(22), Geom. Dedicata, 30, 23-33, (1989)  Kawanaka, N.; Matsuyama, H., A twisted version of the Frobenius-Schur indicator and multiplicity-free permutation representations, Hokkaido Math. J., 19, 495-508, (1990) · Zbl 0791.20006  E. Lambeck, “Contributions to the theory of distance-regular graphs,” Thesis, Eindhoven, 1990. · Zbl 0758.05047  Leonard, D., Directed distance-regular graphs with the $$Q$$-polynomial property, J. Combin. Theory Ser. B, 48, 191-196, (1990) · Zbl 0723.05065  Leonard, D., Non-symmetric, metric, cometric association schemes are self-dual, J. Combin. Theory Ser. B, 51, 244-247, (1991) · Zbl 0754.05076  Leonard, D., Orthogonal polynomials, duality, and association schemes, SIAM J. Math. Anal., 13, 656-663, (1982) · Zbl 0495.33006  Ma, S. L., On association schemes, Schur rings, strongly regular graphs and partial difference sets, Ars. Combin., 27, 211-220, (1989) · Zbl 0666.05015  N. Manickam, “Distribution invariants of association schemes,” Seventeenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1987), Congr. Numer. 61 (1988), 121-131.  Moon, A., Characterization of the Odd graphs $$O\_{}\{k\}$$ by the parameters, Discrete Math., 42, 91-97, (1982) · Zbl 0494.05035  Munemasa, A., On non-symmetric $$P$$-and $$Q$$-polynomial association schemes, J. Combin. Theory Ser. B, 51, 314-328, (1991) · Zbl 0754.05078  Neumaier, A., Characterization of a class of distance-regular graphs, J. Reine Angew. Math., 357, 182-192, (1985) · Zbl 0552.05042  Neumaier, A., Krein conditions and near polygons, J. Combin. Theory Ser. A, 54, 201-209, (1990) · Zbl 0738.05025  Nomura, K., Distance-regular graphs of Hamming type, J. Combin. Theory Ser. B, 50, 160-167, (1990) · Zbl 0719.05070  Nomura, K., Intersection diagrams of distance-biregular graphs, J. Combin. Theory Ser. B, 50, 214-221, (1990) · Zbl 0719.05071  Nomura, K., On local structure of a distance-regular graph of Hamming type, J. Combin. Theory Ser. B, 47, 120-123, (1989) · Zbl 0628.05054  Powers, D., Semi-regular graphs and their algebra, Linear and Multilinear Algebra, 24, 27-37, (1988) · Zbl 0697.05041  Praeger, C. E.; Saxl, J.; Yokoyama, K., Distance-transitive graphs and finite simple groups, Proc. London Math. Soc., 55, 1-21, (1987) · Zbl 0619.05026  Rifa, J.; Huguet, L., Classification of a class of distance-regular graphs via completely regular codes, Discrete Appl. Math., 26, 289-300, (1990) · Zbl 0687.05015  Rifa, J., On the construction of completely regular linear codes from distance-regular graphs, No. 356, 376-393, (1989), Berlin-New York  Sloane, N.; Askey, R. (ed.), An introduction to association schemes and coding theory, 225-260, (1975), New York  Sole, P., A Lloyd theorem in weakly metric association schemes, European J. Combin., 10, 189-196, (1989) · Zbl 0722.05061  Stanton, D., Harmonics on posets, J. Combin. Theory Ser. A, 40, 136-149, (1985) · Zbl 0573.06001  Stanton, D., Some $$q$$-Krawtchouk polynomials on Chevalley groups, Amer. J. Math., 102, 625-662, (1980) · Zbl 0448.33019  Suzuki “, H.$$, t$$-designs in $$H(d,$$q), Hokkaido Math. J., 19, 403-415, (1990) · Zbl 0726.05013  Terwilliger, P., A characterization of $$P$$-and $$Q$$-polynomial association schemes, J. Combin. Theory Ser. A, 45, 8-26, (1987) · Zbl 0663.05016  Terwilliger, P., A class of distance-regular graphs that are $$Q$$-polynomial, J. Combin. Theory Ser. B, 40, 213-223, (1986) · Zbl 0579.05029  P. Terwilliger, “A generalization of Jackson”s _{8φ7} sum,” in preparation.  Terwilliger, P., Counting 4-vertex configurations in $$P$$-and $$Q$$-polynomial association schemes, Algebras Groups Geom., 2, 541-554, (1985) · Zbl 0592.05011  P. Terwilliger, “Leonard pairs and the $$q$$-Racah polynomials,” in preparation. · Zbl 1075.05090  Terwilliger, P., Root systems and the Johnson and Hamming graphs, European J. Combin., 8, 73-102, (1987) · Zbl 0614.05048  Terwilliger, P., The classification of distance-regular graphs of type IIB, Combinatorica, 8, 125-132, (1988) · Zbl 0727.05050  Terwilliger, P., The classification of finite connected hypermetric spaces, Graphs Combin., 3, 293-298, (1987) · Zbl 0618.05043  Terwilliger, P., The incidence algebra of a uniform poset, No. 20, 193-212, (1990), New York · Zbl 0737.05032  Terwilliger, P., The Johnson graph $$J(d,r)$$ is unique if $$(d,r)$$≠ (8,2), Discrete Math., 58, 175-189, (1986) · Zbl 0587.05038  Terwilliger, P.$$, P$$-and $$Q$$-polynomial schemes with $$q$$= −1, J. Combin. Theory Ser. B, 42, 64-67, (1987) · Zbl 0675.05016  Weichsel, P., Distance-regular graphs in block form, Linear Algebra Appl., 126, 135-148, (1989) · Zbl 0715.05051  Yamada, M., Distance-regular digraphs of girth 4 over an extension ring of ℤ/4ℤ, Graphs Combin., 6, 381-394, (1990) · Zbl 0721.05028
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.