×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] R. Askey, J. Wilson, “Some basic hypergeometric orthogonal polynomials that generalize the Jacobi polynomials,” Mem. Amer. Math. Soc.319, 1985. · Zbl 0572.33012
[3] E. Bannai, T. Ito, “Algebraic Combinatorics I: Association Schemes,” Benjamin-Cummings Lecture Note 58. Menlo Park, 1984.
[4] Bannai, E.; Ito, T., Current researches on algebraic combinatorics, Graphs Combin., 2, 287-308, (1986) · Zbl 0685.05030
[5] 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.
[6] Bannai, E.; Nevai, Paul (ed.), Orthogonal polynomials in coding theory and algebraic combinatorics, 25-53, (1990), Boston
[7] Bier, T., Lattices associated to the Rectangular Association Scheme, Ars Combin., 23A, 41-50, (1987) · Zbl 0624.05021
[8] Bier, T., Totient-numbers of the rectangular association scheme, Graphs Combin., 6, 5-15, (1990) · Zbl 0696.05013
[9] Biggs, N., Some Odd graph theory, Ann. New York Acad. Sci., 319, 71-81, (1979)
[10] J. Van Bon, “Affine distance-transitive groups,” thesis, C.W.I., The Netherlands, 1990.
[11] A. Brouwer, A. Cohen, A. Neumaier, Distance-Regular Graphs, Springer Verlag, New York, 1989.
[12] 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
[13] Calderbank, A.; Delsarte, P.; Sloane, N., A strengthening of the Assmus-Mattson theorem, IEEE Trans. Inform. Theory, 37, 1261-1268, (1991) · Zbl 0734.94018
[14] 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
[15] A. Calderbank, P. Delsarte, “On error-correcting codes and invariant linear forms,” preprint. · Zbl 0768.94020
[16] Cameron, P., Dual polar spaces, Geom. Dedicata, 12, 75-85, (1982) · Zbl 0473.51002
[17] 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
[18] 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.
[19] Clayton, R., Perfect multiple coverings in metric schemes, No. 20, 51-64, (1990), New York-Berlin
[20] C. Curtis, I. Reiner, “Representation Theory of Finite Groups and Associative Algebras”, Interscience, New York, 1962. · Zbl 0131.25601
[21] C. Delorme, “Distance bi-regular bipartite graphs,” European J. Combin., submitted. · Zbl 0804.05031
[22] P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Res. Reports Suppl.10 (1973).
[23] Delsarte, P., Association schemes and \(t\)-designs in regular semi-lattices, J. Combin. Theory Ser. A, 20, 230-243, (1976) · Zbl 0342.05020
[24] Doob, M., On graph products and association schemes, Utilitas Math., 1, 291-302, (1972) · Zbl 0315.05130
[25] Dunkl, C., An addition theorem for some \(q\)-Hahn polynomials, Monatsh. Math., 85, 5-37, (1977) · Zbl 0345.33010
[26] Egawa, Y., Association schemes of quadratic forms, J. Combin. Theory Ser. A, 38, 1-14, (1985) · Zbl 0564.05014
[27] Egawa, Y., Characterization of \(H(n, q)\) by the parameters, J. Combin. Theory Ser. A, 31, 108-125, (1981) · Zbl 0472.05056
[28] 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)
[29] 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
[30] Gasper, G.; Rahman, M., Basic hypergeometric series, (1990), Cambridge · Zbl 0695.33001
[31] 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
[32] Hemmeter, J., The large cliques in the graph of quadratic forms, European J. Combin., 9, 395-410, (1988) · Zbl 0672.05044
[33] 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
[34] 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
[35] Huang, T., A characterization of the association schemes of bilinear forms, European J. Combin., 8, 159-173, (1987) · Zbl 0675.05064
[36] 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
[37] T. Huang and M. Laurant, “\((s,r\):μ)-nets and alternating forms graphs,” submitted.
[38] 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
[39] Ivanov, A. A., Distance-transitive graphs that admit elations, Izv. Akad. Nauk SSSR Ser. Mat., 53, 971-1000, (1989)
[40] 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
[41] 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)
[42] Ivanov, A.; Shpektorov, S., Characterization of the association schemes of Hermitian forms over GF(22), Geom. Dedicata, 30, 23-33, (1989)
[43] 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
[44] E. Lambeck, “Contributions to the theory of distance-regular graphs,” Thesis, Eindhoven, 1990. · Zbl 0758.05047
[45] Leonard, D., Directed distance-regular graphs with the \(Q\)-polynomial property, J. Combin. Theory Ser. B, 48, 191-196, (1990) · Zbl 0723.05065
[46] Leonard, D., Non-symmetric, metric, cometric association schemes are self-dual, J. Combin. Theory Ser. B, 51, 244-247, (1991) · Zbl 0754.05076
[47] Leonard, D., Orthogonal polynomials, duality, and association schemes, SIAM J. Math. Anal., 13, 656-663, (1982) · Zbl 0495.33006
[48] Ma, S. L., On association schemes, Schur rings, strongly regular graphs and partial difference sets, Ars. Combin., 27, 211-220, (1989) · Zbl 0666.05015
[49] N. Manickam, “Distribution invariants of association schemes,” Seventeenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1987), Congr. Numer. 61 (1988), 121-131.
[50] Moon, A., Characterization of the Odd graphs \(O\_{}\{k\}\) by the parameters, Discrete Math., 42, 91-97, (1982) · Zbl 0494.05035
[51] Munemasa, A., On non-symmetric \(P\)-and \(Q\)-polynomial association schemes, J. Combin. Theory Ser. B, 51, 314-328, (1991) · Zbl 0754.05078
[52] Neumaier, A., Characterization of a class of distance-regular graphs, J. Reine Angew. Math., 357, 182-192, (1985) · Zbl 0552.05042
[53] Neumaier, A., Krein conditions and near polygons, J. Combin. Theory Ser. A, 54, 201-209, (1990) · Zbl 0738.05025
[54] Nomura, K., Distance-regular graphs of Hamming type, J. Combin. Theory Ser. B, 50, 160-167, (1990) · Zbl 0719.05070
[55] Nomura, K., Intersection diagrams of distance-biregular graphs, J. Combin. Theory Ser. B, 50, 214-221, (1990) · Zbl 0719.05071
[56] 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
[57] Powers, D., Semi-regular graphs and their algebra, Linear and Multilinear Algebra, 24, 27-37, (1988) · Zbl 0697.05041
[58] 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
[59] 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
[60] Rifa, J., On the construction of completely regular linear codes from distance-regular graphs, No. 356, 376-393, (1989), Berlin-New York
[61] Sloane, N.; Askey, R. (ed.), An introduction to association schemes and coding theory, 225-260, (1975), New York
[62] Sole, P., A Lloyd theorem in weakly metric association schemes, European J. Combin., 10, 189-196, (1989) · Zbl 0722.05061
[63] Stanton, D., Harmonics on posets, J. Combin. Theory Ser. A, 40, 136-149, (1985) · Zbl 0573.06001
[64] Stanton, D., Some \(q\)-Krawtchouk polynomials on Chevalley groups, Amer. J. Math., 102, 625-662, (1980) · Zbl 0448.33019
[65] Suzuki “, H.\(, t\)-designs in \(H(d,\)q), Hokkaido Math. J., 19, 403-415, (1990) · Zbl 0726.05013
[66] Terwilliger, P., A characterization of \(P\)-and \(Q\)-polynomial association schemes, J. Combin. Theory Ser. A, 45, 8-26, (1987) · Zbl 0663.05016
[67] Terwilliger, P., A class of distance-regular graphs that are \(Q\)-polynomial, J. Combin. Theory Ser. B, 40, 213-223, (1986) · Zbl 0579.05029
[68] P. Terwilliger, “A generalization of Jackson”s _{8φ7} sum,” in preparation.
[69] Terwilliger, P., Counting 4-vertex configurations in \(P\)-and \(Q\)-polynomial association schemes, Algebras Groups Geom., 2, 541-554, (1985) · Zbl 0592.05011
[70] P. Terwilliger, “Leonard pairs and the \(q\)-Racah polynomials,” in preparation. · Zbl 1075.05090
[71] Terwilliger, P., Root systems and the Johnson and Hamming graphs, European J. Combin., 8, 73-102, (1987) · Zbl 0614.05048
[72] Terwilliger, P., The classification of distance-regular graphs of type IIB, Combinatorica, 8, 125-132, (1988) · Zbl 0727.05050
[73] Terwilliger, P., The classification of finite connected hypermetric spaces, Graphs Combin., 3, 293-298, (1987) · Zbl 0618.05043
[74] Terwilliger, P., The incidence algebra of a uniform poset, No. 20, 193-212, (1990), New York · Zbl 0737.05032
[75] Terwilliger, P., The Johnson graph \(J(d,r)\) is unique if \((d,r) \)≠ (8,2), Discrete Math., 58, 175-189, (1986) · Zbl 0587.05038
[76] Terwilliger, P.\(, P\)-and \(Q\)-polynomial schemes with \(q \)= −1, J. Combin. Theory Ser. B, 42, 64-67, (1987) · Zbl 0675.05016
[77] Weichsel, P., Distance-regular graphs in block form, Linear Algebra Appl., 126, 135-148, (1989) · Zbl 0715.05051
[78] 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.