The Terwilliger Algebra Associated with a Set of Vertices in a Distance-Regular Graph
Hiroshi Suzuki
Department of Mathematics International Christian University Mitaka Tokyo 181-8585 Japan
DOI: 10.1007/s10801-005-2504-4
Abstract
Let Γ be a distance-regular graph of diameter D. Let X denote the vertex set of Γ and let Y be a nonempty subset of X. We define an algebra τ = τ ( Y). This algebra is finite dimensional and semisimple. If Y consists of a single vertex then τ is the corresponding subconstituent algebra defined by P. Terwilliger. We investigate the irreducible τ -modules. We define endpoints and thin condition on irreducible τ -modules as a generalization of the case when Y consists of a single vertex. We determine when an irreducible module is thin. When the module is generated by the characteristic vector of Y, it is thin if and only if Y is a completely regular code of Γ . By considering a suitable subset Y, every irreducible τ ( x)-module of endpoint i can be regarded as an irreducible τ ( Y)-module of endpoint 0.
Pages: 5–38
Keywords: keywords distance-regular graph; association scheme; subconstituent algebra; Terwilliger algebra; tight graph; completely regular code
Full Text: PDF
References
1. E. Bannai and T. Ito, Algebraic Combinatorics I, Benjamin/Cummings, California, 1984.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer Verlag, Berlin, Heidelberg, 1989.
3. J.S. Caughman IV, “Spectra of bipartite P- and Q-polynomial association schemes,” Graphs Combin. 14 (1998), 321-343.
4. J.S. Caughman IV, “The Terwilliger algebras of bipartite P- and Q-polynomial association schemes,” Discrete Math. 196 (1999), 65-95.
5. T.S. Chihara, An Introduction to Orthogonal Polynomials, Mathematics and its Applications, 13 (1978), Gordon and Breach Science Publishers.
6. B. Collins, “The girth of a thin distance-regular graph,” Graphs Combin. 13 (1997), 21-30.
7. B. Collins, “The Terwilliger algebra of an almost-bipartite distance-regular graph and its antipodal 2-cover,” Discrete Math. 216 (2000), 35-69.
8. B. Curtin, “Bipartite distance-regular graphs I,” Graphs Combin. 15 (1999), 143-158.
9. B. Curtin, “Bipartite distance-regular graphs II,” Graphs Combin. 15 (1999), 377-391.
10. B. Curtin, “2-homogeneous bipartite distance-regular graphs,” Discrete Math. 187 (1998), 39-70.
11. B. Curtin, “Distance-regular graphs with support a spin model are thin,” in 16th British Combinatorial Conference (London, 1997), Discrete Math. 1999, vol. 197/198, pp. 205-216.
12. B. Curtin, “Almost 2-homogeneous bipartite distance-regular graphs,” Europ. J. Combin. 21 (2000), 865- 876.
13. B. Curtin and K. Nomura, “Distance-regular graphs related to the quantum enveloping algebra of sl(2),” J. Alg. Combin. 12 (2000), 25-36.
14. B. Curtin, “The local structure of a bipartite distance-regular graph,” Europ. J. Combin. 20 (1999), 739- 758.
15. P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Phillips Research Reports Suppl. 10 (1973).
16. G. Dickie, “Twice Q-polynomial distance-regular graphs are thin,” Europ. J. Combin. 16 (1995), 555-560.
17. G. Dickie and P. Terwilliger, “A note on thin P-polynomial and dual-thin Q-polynomial symmetric association schemes,” J. Alg. Combin. 7 (1998), 5-15.
18. E. Egge, “A generalization of the Terwilliger algebra,” J. Algebra 233 (2000), 213-252.
19. E. Egge, “The generalized Terwilliger algebra and its finite dimensional modules when d = 2,” Journal of Algebra 250 (2002), 178-216.
20. M.A. Fiol and E. Garriga, “On the algebraic theory of pseudo-distance-regularity around a set,” Linear Algebra Appl. 298 (1999), 115-141.
21. M.A. Fiol and E. Garriga, “An algebraic characterization of completely regular codes in distance-regular graphs,” SIAM J. Discrete Math. 15 (2001/02), 1-13.
22. J.T. Go, “The Terwilliger algebra of the Hypercube,” Europ. J. Combin. 23 (2002), 399-430.
23. J.T. Go and P. Terwilliger, “Tight distance-regular graphs and the subconstituent algebra,” Europ. J. Combin. 23 (2002), 793-816.
24. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, Inc., New York, 1993.
25. M. Giudice and C.E. Praeger, “Completely transitive codes in Hamming graphs,” European J. Combin. 20 (1999), 647-661.
26. S.A. Hobart and T. Ito, “The structure of nonthin irreducible T -modules: Ladder bases and classical parameters,” J. Alg. Combin. 7 (1998), 53-75.
27. A. Juri\check sić and J. Koolen, “A local approach to 1-homogeneous graphs,” Designs, Codes, and Cryptography 21 (2000), 127-147.
28. A. Juri\check sić and J. Koolen, “Nonexistence of some antipodal distance-regular graphs of diameter four,” Europ. J. Combin. 21 (2000), 1039-1046.
29. A. Juri\check sić and J. Koolen, “1-homogeneous graphs with cocktail party μ-graphs,” J. Alg. Combin. 18 (2003), 79-98.
30. A. Juri\check sić and J. Koolen, “Krein parameters and antipodal tight graphs with diameter 3 and 4,” Discrete Math. 244 (2002), 181-202.
31. A. Juri\check sić, J. Koolen, and P. Terwilliger, “Tight distance-regular graphs,” J. Alg. Combin. 12 (2000), 163-197.
32. M. MacLean, “An inequality involving two eigenvalues of a bipartite distance-regular graph,” Discrete Math. 225 (2000), 193-216.
33. M. MacLean, “Taut distance-regular graphs of odd diameter,” J. Alg. Combin. 17 (2003), 125-148.
34. W.J. Martin, “Completely regular designs,” J. Combin. Des. 6 (1998), 261-273.
35. A. Neumaier, “Completely regular codes,” Discrete Math. 106/107 (1992), 353-360.
36. A.A. Pascasio, “Tight graphs and their primitive idempotents,” J. Alg. Combin. 10 (1999), 47-59.
37. A.A. Pascasio, “Tight distance-regular graphs and Q-polynomial property,” Graphs Combin. 17 (2001), 149- 169.
38. A.A. Pascasio, “An inequality on the cosine of a tight distance-regular graph,” Linear Algebra Appl. 325 (2001), 147-159.
39. A.A. Pascasio, “An inequality in character algebra,” Discrete Math. 264 (2003), 201-210.
40. G. Szeg\ddot o, Orthogonal Polynomials, American Mathematical Society, Providence, Rhode Island, 1939.
41. H. Suzuki, “Distance semi-regular graphs,” Algebraic Colloquium 2 (1995), 315-328.
42. H. Suzuki, “An introduction to distance-regular graphs,” Lecture Note, in Three Lectures in Algebra, Sophia University Lecture Note Series No. 41 (1999), pp. 57-132.
43. K. Tanabe, “The irreducible modules of the Terwilliger algebras of Doob schemes,” J. Alg. Combin. 6 (1997), 173-195.
44. P. Terwilliger, “A new feasibility condition for distance-regular graphs,” Discrete Math. 61 (1986), 311-315.
45. P. Terwilliger, “The subconstituent algebra of an association scheme, (Part I),” J. Alg. Combin. 1 (1992), 363-388.
46. P. Terwilliger, “The subconstituent algebra of an association scheme, (Part II),” J. Alg. Combin. 2 (1993), 73-103. SUZUKI
47. P. Terwilliger, “The subconstituent algebra of an association scheme, (Part III),” J. Alg. Combin. 2 (1993), 177-210.
48. P. Terwilliger, “The subconstituent algebra of a distance-regular graph; thin modules with endpoint one,” Linear Algebra Appl. 356 (2002), 157-187.
49. P. Terwilliger, “An inequality involving the local eigenvalues of a distance-regular graph,” J. Alg. Combin. 19 (2004), 143-172.
50. M. Tomiyama and N. Yamazaki, “The subconstituent algebra of a strongly regular graph,” Kyushu J. Math. 48 (1998), 323-334.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer Verlag, Berlin, Heidelberg, 1989.
3. J.S. Caughman IV, “Spectra of bipartite P- and Q-polynomial association schemes,” Graphs Combin. 14 (1998), 321-343.
4. J.S. Caughman IV, “The Terwilliger algebras of bipartite P- and Q-polynomial association schemes,” Discrete Math. 196 (1999), 65-95.
5. T.S. Chihara, An Introduction to Orthogonal Polynomials, Mathematics and its Applications, 13 (1978), Gordon and Breach Science Publishers.
6. B. Collins, “The girth of a thin distance-regular graph,” Graphs Combin. 13 (1997), 21-30.
7. B. Collins, “The Terwilliger algebra of an almost-bipartite distance-regular graph and its antipodal 2-cover,” Discrete Math. 216 (2000), 35-69.
8. B. Curtin, “Bipartite distance-regular graphs I,” Graphs Combin. 15 (1999), 143-158.
9. B. Curtin, “Bipartite distance-regular graphs II,” Graphs Combin. 15 (1999), 377-391.
10. B. Curtin, “2-homogeneous bipartite distance-regular graphs,” Discrete Math. 187 (1998), 39-70.
11. B. Curtin, “Distance-regular graphs with support a spin model are thin,” in 16th British Combinatorial Conference (London, 1997), Discrete Math. 1999, vol. 197/198, pp. 205-216.
12. B. Curtin, “Almost 2-homogeneous bipartite distance-regular graphs,” Europ. J. Combin. 21 (2000), 865- 876.
13. B. Curtin and K. Nomura, “Distance-regular graphs related to the quantum enveloping algebra of sl(2),” J. Alg. Combin. 12 (2000), 25-36.
14. B. Curtin, “The local structure of a bipartite distance-regular graph,” Europ. J. Combin. 20 (1999), 739- 758.
15. P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Phillips Research Reports Suppl. 10 (1973).
16. G. Dickie, “Twice Q-polynomial distance-regular graphs are thin,” Europ. J. Combin. 16 (1995), 555-560.
17. G. Dickie and P. Terwilliger, “A note on thin P-polynomial and dual-thin Q-polynomial symmetric association schemes,” J. Alg. Combin. 7 (1998), 5-15.
18. E. Egge, “A generalization of the Terwilliger algebra,” J. Algebra 233 (2000), 213-252.
19. E. Egge, “The generalized Terwilliger algebra and its finite dimensional modules when d = 2,” Journal of Algebra 250 (2002), 178-216.
20. M.A. Fiol and E. Garriga, “On the algebraic theory of pseudo-distance-regularity around a set,” Linear Algebra Appl. 298 (1999), 115-141.
21. M.A. Fiol and E. Garriga, “An algebraic characterization of completely regular codes in distance-regular graphs,” SIAM J. Discrete Math. 15 (2001/02), 1-13.
22. J.T. Go, “The Terwilliger algebra of the Hypercube,” Europ. J. Combin. 23 (2002), 399-430.
23. J.T. Go and P. Terwilliger, “Tight distance-regular graphs and the subconstituent algebra,” Europ. J. Combin. 23 (2002), 793-816.
24. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, Inc., New York, 1993.
25. M. Giudice and C.E. Praeger, “Completely transitive codes in Hamming graphs,” European J. Combin. 20 (1999), 647-661.
26. S.A. Hobart and T. Ito, “The structure of nonthin irreducible T -modules: Ladder bases and classical parameters,” J. Alg. Combin. 7 (1998), 53-75.
27. A. Juri\check sić and J. Koolen, “A local approach to 1-homogeneous graphs,” Designs, Codes, and Cryptography 21 (2000), 127-147.
28. A. Juri\check sić and J. Koolen, “Nonexistence of some antipodal distance-regular graphs of diameter four,” Europ. J. Combin. 21 (2000), 1039-1046.
29. A. Juri\check sić and J. Koolen, “1-homogeneous graphs with cocktail party μ-graphs,” J. Alg. Combin. 18 (2003), 79-98.
30. A. Juri\check sić and J. Koolen, “Krein parameters and antipodal tight graphs with diameter 3 and 4,” Discrete Math. 244 (2002), 181-202.
31. A. Juri\check sić, J. Koolen, and P. Terwilliger, “Tight distance-regular graphs,” J. Alg. Combin. 12 (2000), 163-197.
32. M. MacLean, “An inequality involving two eigenvalues of a bipartite distance-regular graph,” Discrete Math. 225 (2000), 193-216.
33. M. MacLean, “Taut distance-regular graphs of odd diameter,” J. Alg. Combin. 17 (2003), 125-148.
34. W.J. Martin, “Completely regular designs,” J. Combin. Des. 6 (1998), 261-273.
35. A. Neumaier, “Completely regular codes,” Discrete Math. 106/107 (1992), 353-360.
36. A.A. Pascasio, “Tight graphs and their primitive idempotents,” J. Alg. Combin. 10 (1999), 47-59.
37. A.A. Pascasio, “Tight distance-regular graphs and Q-polynomial property,” Graphs Combin. 17 (2001), 149- 169.
38. A.A. Pascasio, “An inequality on the cosine of a tight distance-regular graph,” Linear Algebra Appl. 325 (2001), 147-159.
39. A.A. Pascasio, “An inequality in character algebra,” Discrete Math. 264 (2003), 201-210.
40. G. Szeg\ddot o, Orthogonal Polynomials, American Mathematical Society, Providence, Rhode Island, 1939.
41. H. Suzuki, “Distance semi-regular graphs,” Algebraic Colloquium 2 (1995), 315-328.
42. H. Suzuki, “An introduction to distance-regular graphs,” Lecture Note, in Three Lectures in Algebra, Sophia University Lecture Note Series No. 41 (1999), pp. 57-132.
43. K. Tanabe, “The irreducible modules of the Terwilliger algebras of Doob schemes,” J. Alg. Combin. 6 (1997), 173-195.
44. P. Terwilliger, “A new feasibility condition for distance-regular graphs,” Discrete Math. 61 (1986), 311-315.
45. P. Terwilliger, “The subconstituent algebra of an association scheme, (Part I),” J. Alg. Combin. 1 (1992), 363-388.
46. P. Terwilliger, “The subconstituent algebra of an association scheme, (Part II),” J. Alg. Combin. 2 (1993), 73-103. SUZUKI
47. P. Terwilliger, “The subconstituent algebra of an association scheme, (Part III),” J. Alg. Combin. 2 (1993), 177-210.
48. P. Terwilliger, “The subconstituent algebra of a distance-regular graph; thin modules with endpoint one,” Linear Algebra Appl. 356 (2002), 157-187.
49. P. Terwilliger, “An inequality involving the local eigenvalues of a distance-regular graph,” J. Alg. Combin. 19 (2004), 143-172.
50. M. Tomiyama and N. Yamazaki, “The subconstituent algebra of a strongly regular graph,” Kyushu J. Math. 48 (1998), 323-334.