The Subconstituent Algebra of an Association Scheme, (Part I)
Paul Terwilliger
DOI: 10.1023/A:1022494701663
Abstract
We introduce a method for studying commutative association schemes with \mathbb C \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 structure 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.
Pages: 363–388
Keywords: association scheme; $P$-polynomial; $Q$-polynomial; distance-regular graph
Full Text: PDF
References
1. R. Askey, J. Wilson, "A set of orthogonal polynomials that generalize the Racah coefficients on 6-j symbols," SIAM J. Math. Anal. 10 (1979), 1008-1016.
2. R. Askey, J. Wilson, "Some basic hypergeometric orthogonal polynomials that generalize the Jacobi polynomials," Mem. Amer. Math. Soc. 319, 1985.
3. E. Bannai, T. Ito, "Algebraic Combinatorics I: Association Schemes," Benjamin-Cummings Lecture Note
58. Menlo Park, 1984.
4. E. Bannai, T. Ito, "Current researches on algebraic combinatorics," Graphs Combin. 2 (1986), 287-308.
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. TERWILLIGER
6. E. Bannai, "Orthogonal polynomials in coding theory and algebraic combinatorics." Orthogonal Polynomials: Theory and Practice (Paul Nevai, Ed.), Kluwer Academic, Boston (1990), 25-53.
7. T. Bier, "Lattices associated to the Rectangular Association Scheme," ATS Combin. 23 A (1987), 41-50.
8. T. Bier, "Totient-numbers of the rectangular association scheme," Graphs Combin. 6 (1990), 5-15.
9. N. Biggs, "Some Odd graph theory," Ann. New York Acad. Sci. 319 (1979), 71-81.
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. A. Brouwer, J. Hemmeter, "A new family of distance-regular graphs and the (0,1,2)-cliques in dual polar graphs," European J. Combin. 13 (1992), 71-79.
13. A. Calderbank, P. Delsarte, N. Sloane, "A strengthening of the Assmus-Mattson theorem," IEEE Trans. Inform. Theory 37 (1991), 1261-1268.
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.
15. A. Calderbank, P. Delsarte, "On error-correcting codes and invariant linear forms," preprint.
16. P. Cameron, "Dual polar spaces," Geom. Dedicata 12 (1982), 75-85.
17. P. Cameron, J. Goethals, J. Seidel, "The Krein condition, spherical designs, Norton algebras, and permutation groups," Indag. Math. 40 (1978), 196-206.
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. R. Clayton, "Perfect multiple coverings in metric schemes," Coding theory and design theory, Part I," 51-64, IMA Vol. Math. Appl., 20, Springer, New York-Berlin, 1990.
20. C. Curtis, I. Reiner, "Representation Theory of Finite Groups and Associative Algebras", Interscience, New York, 1962.
21. C. Delorme, "Distance bi-regular bipartite graphs," European J. Combin., submitted.
22. P. Delsarte, "An algebraic approach to the association schemes of coding theory," Philips Res. Reports Suppl. 10 (1973).
23. P. Delsarte, "Association schemes and t-designs in regular semi-lattices," J. Combin. Theory Ser. A 20 (1976), 230-243.
24. M. Doob, "On graph products and association schemes," Utilitas Math. 1 (1972), 291-302.
25. C. Dunkl, "An addition theorem for some q-Hahn polynomials," Monatsh. Math. 85 (1977), 5-37.
26. Y. Egawa, "Association schemes of quadratic forms," J. Combin. Theory Ser. A 38 (1985), 1-14.
27. Y. Egawa, "Characterization of H(n, q) by the parameters" J. Combin. Theory Ser. A 31 (1981), 108-125.
28. I. Faradzhev, A.A. Ivanov, "Distance-transitive representations of groups G with PSL2(q) C G C PFL2(q)," European J. Combin. 11 (1990), 347-356.
29. I. Faradzhev, A.A. Ivanov, M. Klin, "Galois correspondence between permutation groups and cellular rings (association schemes)," Graphs Combin. 6 (1990), 303-332.
30. G. Gasper, M. Rahman, "Basic hypergeometric series," Encyclopedia Math. Appl., Cambridge University Press, Cambridge, 1990.
31. C. Godsil, J. Shawe-laylor, "Distance-regularized graphs are distance-regular or distance-biregu lar," J. Combin. Theory Ser. B 43 (1987), 14-24.
32. J. Hemmeter, "The large cliques in the graph of quadratic forms," European J. Combin. 9 (1988), 395-410.
33. J. Hemmeter and A. Woldar, "Classification of the maximal cliques of size > q+4 in the quadratic forms graph in odd characteristic," European J. Combin. 11 (1990), 433-450.
34. J. Hemmeter and A. Woldar, "On the maximal cliques of the quadratic forms graph in even characteristic," European J. Combin. 11 (1990), 119-126.
35. T. Huang, "A characterization of the association schemes of bilinear forms," European J. Combin. 8 (1987), 159-173.
36. T. Huang, "Further results on the E-K-R theorem for the distance regular graphs Hq(k,n)," Bull. Inst. Math. Acad. Sinica 16 (1988), 347-356.
37. T. Huang and M. Laurant, "(s, r : u)-nets and alternating forms graphs," submitted.
38. T. Ito, A. Munemasa, and M. Yamada, "Amorphous association schemes over the Galois rings of characteristic 4," European J. Combin. 12 (1991), 513-526.
39. A. A. Ivanov, "Distance-transitive graphs that admit elations," Izv. Akad. Nauk SSSR Ser. Mat. S3 (1989), 971-1000.
40. A. Ivanov, M. Muzichuk, and V. Ustimenko, "On a new family of (P and Q)-polynomial schemes," European J. Combin. 10 (1989), 337-345.
41. A. Ivanov and S. Shpektorov, "The association schemes of the dual polar spaces of type 2A2d-1 (pf) are characterized by their parameters if d > 3," Linear Algebra Appl. 114/115 (1989), 133-139.
42. A. Ivanov and S. Shpektorov, "Characterization of the association schemes of Hermitian forms over GF(22)," Geom. Dedicata 30 (1989), 23-33.
43. N. Kawanaka and H. Matsuyama, "A twisted version of the Frobenius-Schur indicator and multiplicity-free permutation representations," Hokkaido Math. J. 19 (1990), 495-508.
44. E. Lambeck, "Contributions to the theory of distance-regular graphs," Thesis, Eindhoven, 1990.
45. D. Leonard, "Directed distance-regular graphs with the Q-polynomial property," J. Combin. Theory Ser. B 48 (1990), 191-196.
46. D. Leonard, "Non-symmetric, metric, cometric association schemes are self-dual," J. Combin. Theory Ser. B 51 (1991), 244-247.
47. D. Leonard, "Orthogonal polynomials, duality, and association schemes", SIAM J. Math. Anal. 13 (1982), 656-663.
48. S.L. Ma, "On association schemes, Schur rings, strongly regular graphs and partial difference sets," Ars. Combin. 27 (1989), 211-220.
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. A. Moon, "Characterization of the Odd graphs Ok by the parameters," Discrete Math. 42 (1982), 91-97.
51. A. Munemasa, "On non-symmetric P-and Q-polynomial association schemes," J. Combin. Theory Ser. B 51 (1991), 314-328.
52. A. Neumaier, "Characterization of a class of distance-regular graphs," J. Reine Angew. Math. 357 (1985), 182-192.
53. A. Neumaier, "Krein conditions and near polygons," J. Combin. Theory Ser. A 54 (1990), 201-209.
54. K. Nomura, "Distance-regular graphs of Hamming type," J. Combin. Theory Ser. B 50 (1990), 160-167.
55. K. Nomura, "Intersection diagrams of distance-biregular graphs," J. Combin. Theory Ser. B 50 (1990), 214-221.
56. K. Nomura, "On local structure of a distance-regular graph of Hamming type," J. Combin. Theory Ser. B 47 (1989), 120-123.
57. D. Powers, "Semi-regular graphs and their algebra," Linear and Multilinear Algebra 24 (1988), 27-37.
58. C.E. Praeger, J. Saxl, and K. Yokoyama, "Distance-transitive graphs and finite simple groups," Proc. London Math. Soc. (3) 55 (1987), 1-21.
59. J. Rifa and L. Huguet, "Classification of a class of distance-regular graphs via completely regular codes," Southampton Conference on Combinatorial Optimization (Southampton, 1987) Discrete Appl. Math. 26 (1990), 289-300.
60. J. Rifa, "On the construction of completely regular linear codes from distance-regular graphs," Applied algebra, algebraic combinatorics and error-correcting codes (Menorca, 1987), Lecture notes in Comput. Sci., 356, Springer, Berlin-New York, 1989, 376-393.
61. N. Sloane, "An introduction to association schemes and coding theory," In Theory and Application of Special functions (R. Askey, Ed.), Academic Press, New York, 1975, 225-260. TERWILLIGER
62. P. Sole, "A Lloyd theorem in weakly metric association schemes," European J. Combin. 10 (1989), 189-196.
63. D. Stanton, "Harmonics on posets," J. Combin. Theory Ser. A 40 (1985), 136-149.
64. D. Stanton, "Some q-Krawtchouk polynomials on Chevalley groups," Amer. J. Math. 102 (4) (1980), 625-662.
65. H. Suzuki "t-designs in H(d,q)," Hokkaido Math. J. 19 (1990), 403-415.
66. P. Terwilliger, "A characterization of P- and Q-polynomial association schemes," J. Combin. Theory Ser. A 45 (1987), 8-26.
67. P. Terwilliger, "A class of distance-regular graphs that are Q-polynomial," J. Combin. Theory Ser. B 40 (1986), 213-223.
68. P. Terwilliger, "A generalization of Jackson's 8P7 sum," in preparation.
69. P. Terwilliger, "Counting 4-vertex configurations in P- and Q-polynomial association schemes" Algebras Groups Geom. 2 (1985), 541-554.
70. P. Terwilliger, "Leonard pairs and the q-Racah polynomials," in preparation.
71. P. Terwilliger, "Root systems and the Johnson and Hamming graphs," European J. Combin. 8 (1987), 73-102.
72. P. Terwilliger, "The classification of distance-regular graphs of type IIB," Combinatorica 8 (1988), 125-132.
73. P. Terwilliger, "The classification of finite connected hypermetric spaces," Graphs Combin. 3 (1987), 293-298.
74. P. Terwilliger, "The incidence algebra of a uniform poset," Coding Theory and Design Theory part I: Coding Theory, IMA volumes in Mathematics and its applications Vol.
20. Springer, New York (1990), 193-212.
75. P. Terwilliger, "The Johnson graph J(d,r) is unique if (d,r) = (8,2)," Discrete Math., 58 (1986), 175-189.
76. P. Terwilliger, "P-and Q-polynomial schemes with q = -1," J. Combin. Theory Ser. B 42 (1987), 64-67.
77. P. Weichsel, "Distance-regular graphs in block form," Linear Algebra Appl. 126 (1989), 135-148.
78. M. Yamada, "Distance-regular digraphs of girth 4 over an extension ring of Z/4Z" Graphs Combin. 6 (1990), 381-394.
2. R. Askey, J. Wilson, "Some basic hypergeometric orthogonal polynomials that generalize the Jacobi polynomials," Mem. Amer. Math. Soc. 319, 1985.
3. E. Bannai, T. Ito, "Algebraic Combinatorics I: Association Schemes," Benjamin-Cummings Lecture Note
58. Menlo Park, 1984.
4. E. Bannai, T. Ito, "Current researches on algebraic combinatorics," Graphs Combin. 2 (1986), 287-308.
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. TERWILLIGER
6. E. Bannai, "Orthogonal polynomials in coding theory and algebraic combinatorics." Orthogonal Polynomials: Theory and Practice (Paul Nevai, Ed.), Kluwer Academic, Boston (1990), 25-53.
7. T. Bier, "Lattices associated to the Rectangular Association Scheme," ATS Combin. 23 A (1987), 41-50.
8. T. Bier, "Totient-numbers of the rectangular association scheme," Graphs Combin. 6 (1990), 5-15.
9. N. Biggs, "Some Odd graph theory," Ann. New York Acad. Sci. 319 (1979), 71-81.
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. A. Brouwer, J. Hemmeter, "A new family of distance-regular graphs and the (0,1,2)-cliques in dual polar graphs," European J. Combin. 13 (1992), 71-79.
13. A. Calderbank, P. Delsarte, N. Sloane, "A strengthening of the Assmus-Mattson theorem," IEEE Trans. Inform. Theory 37 (1991), 1261-1268.
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.
15. A. Calderbank, P. Delsarte, "On error-correcting codes and invariant linear forms," preprint.
16. P. Cameron, "Dual polar spaces," Geom. Dedicata 12 (1982), 75-85.
17. P. Cameron, J. Goethals, J. Seidel, "The Krein condition, spherical designs, Norton algebras, and permutation groups," Indag. Math. 40 (1978), 196-206.
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. R. Clayton, "Perfect multiple coverings in metric schemes," Coding theory and design theory, Part I," 51-64, IMA Vol. Math. Appl., 20, Springer, New York-Berlin, 1990.
20. C. Curtis, I. Reiner, "Representation Theory of Finite Groups and Associative Algebras", Interscience, New York, 1962.
21. C. Delorme, "Distance bi-regular bipartite graphs," European J. Combin., submitted.
22. P. Delsarte, "An algebraic approach to the association schemes of coding theory," Philips Res. Reports Suppl. 10 (1973).
23. P. Delsarte, "Association schemes and t-designs in regular semi-lattices," J. Combin. Theory Ser. A 20 (1976), 230-243.
24. M. Doob, "On graph products and association schemes," Utilitas Math. 1 (1972), 291-302.
25. C. Dunkl, "An addition theorem for some q-Hahn polynomials," Monatsh. Math. 85 (1977), 5-37.
26. Y. Egawa, "Association schemes of quadratic forms," J. Combin. Theory Ser. A 38 (1985), 1-14.
27. Y. Egawa, "Characterization of H(n, q) by the parameters" J. Combin. Theory Ser. A 31 (1981), 108-125.
28. I. Faradzhev, A.A. Ivanov, "Distance-transitive representations of groups G with PSL2(q) C G C PFL2(q)," European J. Combin. 11 (1990), 347-356.
29. I. Faradzhev, A.A. Ivanov, M. Klin, "Galois correspondence between permutation groups and cellular rings (association schemes)," Graphs Combin. 6 (1990), 303-332.
30. G. Gasper, M. Rahman, "Basic hypergeometric series," Encyclopedia Math. Appl., Cambridge University Press, Cambridge, 1990.
31. C. Godsil, J. Shawe-laylor, "Distance-regularized graphs are distance-regular or distance-biregu lar," J. Combin. Theory Ser. B 43 (1987), 14-24.
32. J. Hemmeter, "The large cliques in the graph of quadratic forms," European J. Combin. 9 (1988), 395-410.
33. J. Hemmeter and A. Woldar, "Classification of the maximal cliques of size > q+4 in the quadratic forms graph in odd characteristic," European J. Combin. 11 (1990), 433-450.
34. J. Hemmeter and A. Woldar, "On the maximal cliques of the quadratic forms graph in even characteristic," European J. Combin. 11 (1990), 119-126.
35. T. Huang, "A characterization of the association schemes of bilinear forms," European J. Combin. 8 (1987), 159-173.
36. T. Huang, "Further results on the E-K-R theorem for the distance regular graphs Hq(k,n)," Bull. Inst. Math. Acad. Sinica 16 (1988), 347-356.
37. T. Huang and M. Laurant, "(s, r : u)-nets and alternating forms graphs," submitted.
38. T. Ito, A. Munemasa, and M. Yamada, "Amorphous association schemes over the Galois rings of characteristic 4," European J. Combin. 12 (1991), 513-526.
39. A. A. Ivanov, "Distance-transitive graphs that admit elations," Izv. Akad. Nauk SSSR Ser. Mat. S3 (1989), 971-1000.
40. A. Ivanov, M. Muzichuk, and V. Ustimenko, "On a new family of (P and Q)-polynomial schemes," European J. Combin. 10 (1989), 337-345.
41. A. Ivanov and S. Shpektorov, "The association schemes of the dual polar spaces of type 2A2d-1 (pf) are characterized by their parameters if d > 3," Linear Algebra Appl. 114/115 (1989), 133-139.
42. A. Ivanov and S. Shpektorov, "Characterization of the association schemes of Hermitian forms over GF(22)," Geom. Dedicata 30 (1989), 23-33.
43. N. Kawanaka and H. Matsuyama, "A twisted version of the Frobenius-Schur indicator and multiplicity-free permutation representations," Hokkaido Math. J. 19 (1990), 495-508.
44. E. Lambeck, "Contributions to the theory of distance-regular graphs," Thesis, Eindhoven, 1990.
45. D. Leonard, "Directed distance-regular graphs with the Q-polynomial property," J. Combin. Theory Ser. B 48 (1990), 191-196.
46. D. Leonard, "Non-symmetric, metric, cometric association schemes are self-dual," J. Combin. Theory Ser. B 51 (1991), 244-247.
47. D. Leonard, "Orthogonal polynomials, duality, and association schemes", SIAM J. Math. Anal. 13 (1982), 656-663.
48. S.L. Ma, "On association schemes, Schur rings, strongly regular graphs and partial difference sets," Ars. Combin. 27 (1989), 211-220.
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. A. Moon, "Characterization of the Odd graphs Ok by the parameters," Discrete Math. 42 (1982), 91-97.
51. A. Munemasa, "On non-symmetric P-and Q-polynomial association schemes," J. Combin. Theory Ser. B 51 (1991), 314-328.
52. A. Neumaier, "Characterization of a class of distance-regular graphs," J. Reine Angew. Math. 357 (1985), 182-192.
53. A. Neumaier, "Krein conditions and near polygons," J. Combin. Theory Ser. A 54 (1990), 201-209.
54. K. Nomura, "Distance-regular graphs of Hamming type," J. Combin. Theory Ser. B 50 (1990), 160-167.
55. K. Nomura, "Intersection diagrams of distance-biregular graphs," J. Combin. Theory Ser. B 50 (1990), 214-221.
56. K. Nomura, "On local structure of a distance-regular graph of Hamming type," J. Combin. Theory Ser. B 47 (1989), 120-123.
57. D. Powers, "Semi-regular graphs and their algebra," Linear and Multilinear Algebra 24 (1988), 27-37.
58. C.E. Praeger, J. Saxl, and K. Yokoyama, "Distance-transitive graphs and finite simple groups," Proc. London Math. Soc. (3) 55 (1987), 1-21.
59. J. Rifa and L. Huguet, "Classification of a class of distance-regular graphs via completely regular codes," Southampton Conference on Combinatorial Optimization (Southampton, 1987) Discrete Appl. Math. 26 (1990), 289-300.
60. J. Rifa, "On the construction of completely regular linear codes from distance-regular graphs," Applied algebra, algebraic combinatorics and error-correcting codes (Menorca, 1987), Lecture notes in Comput. Sci., 356, Springer, Berlin-New York, 1989, 376-393.
61. N. Sloane, "An introduction to association schemes and coding theory," In Theory and Application of Special functions (R. Askey, Ed.), Academic Press, New York, 1975, 225-260. TERWILLIGER
62. P. Sole, "A Lloyd theorem in weakly metric association schemes," European J. Combin. 10 (1989), 189-196.
63. D. Stanton, "Harmonics on posets," J. Combin. Theory Ser. A 40 (1985), 136-149.
64. D. Stanton, "Some q-Krawtchouk polynomials on Chevalley groups," Amer. J. Math. 102 (4) (1980), 625-662.
65. H. Suzuki "t-designs in H(d,q)," Hokkaido Math. J. 19 (1990), 403-415.
66. P. Terwilliger, "A characterization of P- and Q-polynomial association schemes," J. Combin. Theory Ser. A 45 (1987), 8-26.
67. P. Terwilliger, "A class of distance-regular graphs that are Q-polynomial," J. Combin. Theory Ser. B 40 (1986), 213-223.
68. P. Terwilliger, "A generalization of Jackson's 8P7 sum," in preparation.
69. P. Terwilliger, "Counting 4-vertex configurations in P- and Q-polynomial association schemes" Algebras Groups Geom. 2 (1985), 541-554.
70. P. Terwilliger, "Leonard pairs and the q-Racah polynomials," in preparation.
71. P. Terwilliger, "Root systems and the Johnson and Hamming graphs," European J. Combin. 8 (1987), 73-102.
72. P. Terwilliger, "The classification of distance-regular graphs of type IIB," Combinatorica 8 (1988), 125-132.
73. P. Terwilliger, "The classification of finite connected hypermetric spaces," Graphs Combin. 3 (1987), 293-298.
74. P. Terwilliger, "The incidence algebra of a uniform poset," Coding Theory and Design Theory part I: Coding Theory, IMA volumes in Mathematics and its applications Vol.
20. Springer, New York (1990), 193-212.
75. P. Terwilliger, "The Johnson graph J(d,r) is unique if (d,r) = (8,2)," Discrete Math., 58 (1986), 175-189.
76. P. Terwilliger, "P-and Q-polynomial schemes with q = -1," J. Combin. Theory Ser. B 42 (1987), 64-67.
77. P. Weichsel, "Distance-regular graphs in block form," Linear Algebra Appl. 126 (1989), 135-148.
78. M. Yamada, "Distance-regular digraphs of girth 4 over an extension ring of Z/4Z" Graphs Combin. 6 (1990), 381-394.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition