An Inequality Involving the Local Eigenvalues of a Distance-Regular Graph
Paul Terwilliger
DOI: 10.1023/B:JACO.0000023004.62272.8c
Abstract
Let \mathbb R \mathbb{R} [ [( h)\tilde] \tilde η = -1 - b 1(1+ \mathbb C \mathbb{C} ) generated by A, E* 0, E* 1, ..., E* D , where A denotes the adjacency matrix of 
and E* i denotes the projection onto the ith subconstituent of with respect to X. T is called the subconstituent algebra or the Terwilliger algebra. An irreducible T-module W is said to be thin whenever dim E* i W 
1 for 0 i D. By the endpoint of W we mean min{ i| E* i W 
0}. We show the following are equivalent: (i) Equality holds in the above inequality for 1 i D - 1; (ii) Equality holds in the above inequality for i = D - 1; (iii) Every irreducible T-module with endpoint 1 is thin.
and E* i denotes the projection onto the ith subconstituent of with respect to X. T is called the subconstituent algebra or the Terwilliger algebra. An irreducible T-module W is said to be thin whenever dim E* i W 1 for 0 i D. By the endpoint of W we mean min{ i| E* i W 0}. We show the following are equivalent: (i) Equality holds in the above inequality for 1 i D - 1; (ii) Equality holds in the above inequality for i = D - 1; (iii) Every irreducible T-module with endpoint 1 is thin.Pages: 143–172
Keywords: distance-regular graph; association scheme; Terwilliger algebra; subconstituent algebra
Full Text: PDF
References
1. E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings, London, 1984.
2. E. Bannai and N.J.A Sloane, “Uniqueness of certain spherical codes,” Canad. J. Math. 33 (1981), 437-449.
3. N. Biggs, Algebraic Graph Theory, Cambridge U. Press, London, 1994.
4. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
5. J.S. Caughman IV, “Spectra of bipartite P- and Q-polynomial association schemes,” Graphs Combin. 14 (1998), 321-343.
6. J.S. Caughman IV, “The Terwilliger algebras of bipartite P- and Q-polynomial association schemes,” Discrete Math. 196 (1999), 65-95.
7. B. Collins, “The girth of a thin distance-regular graph,” Graphs Combin. 13 (1997), 21-30.
8. B. Collins, “The Terwilliger algebra of an almost-bipartite distance-regular graph and its antipodal 2-cover,” Discrete Math. 216 (2000), 35-69.
9. B. Curtin, “Bipartite distance-regular graphs I,” Graphs Combin. 15 (1999), 143-158.
10. B. Curtin, “Bipartite distance-regular graphs II,” Graphs Combin. 15 (1999), 377-391.
11. B. Curtin, “2-homogeneous bipartite distance-regular graphs,” Discrete Math. 187 (1998), 39-70.
12. B. Curtin, “Distance-regular graphs which support a spin model are thin,” 16th British Combinatorial Conference (London, 1997). Discrete Math. 197/198 (1999), 205-216.
13. B. Curtin, “Almost 2-homogenous bipartite distance-regular graphs,” European J. Combin. 21 (2000), 865- 876.
14. B. Curtin and K. Nomura, “Distance-regular graphs related to the quantum enveloping algebra of sl(2),” J. Alg. Combin. 12 (2000), 25-36.
15. B. Curtin, “The local structure of a bipartite distance-regular graph,” European J. Combin. 20 (1999), 739-758.
16. C. Curtis and I. Reiner, Representation Theory of Finite Groups and Associative Algebras, Interscience, New York 1962.
17. G. Dickie, “Twice Q-polynomial distance-regular graphs are thin,” European J. Combin. 16 (1995), 555-560.
18. 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.
19. E. Egge, “A generalization of the Terwilliger algebra,” J. Algebra 233 (2000), 213-252.
20. E. Egge, “The generalized Terwilliger algebra and its finite dimensional modules when d = 2,” J. Algebra 250 (2002), 178-216.
21. J.T. Go, “The Terwilliger algebra of the hypercube,” European J. Combin. 23 (2002), 399-429.
22. J.T. Go and P. Terwilliger, “Tight distance-regular graphs and the subconstituent algebra,” European J. Combin. 23 (2002), 793-816.
23. C.D. Godsil. Algebraic Combinatorics, Chapman and Hall, Inc., New York, 1993.
24. 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.
25. A. Juri\check sić, J. Koolen and P. Terwilliger, “Tight distance-regular graphs,” J. Algebraic Combinatorics 12 (2000), 163-197.
26. K. Tanabe, “The irreducible modules of the Terwilliger algebras of Doob schemes,” J. Alg. Combin. 6 (1997), 173-195.
27. P. Terwilliger, “A new feasibility condition for distance-regular graphs,” Discrete Math. 61 (1986), 311-315. TERWILLIGER
28. P. Terwilliger, “The subconstituent algebra of an association scheme I,” J. Alg. Combin. 1 (1992), 363-388.
29. P. Terwilliger, “The subconstituent algebra of an association scheme II,” J. Alg. Combin. 2 (1993), 73-103.
30. P. Terwilliger, “The subconstituent algebra of an association scheme III,” J. Alg. Combin. 2 (1993), 177-210.
31. P. Terwilliger, “The subconstituent algebra of a distance-regular graph; thin modules with endpoint 1,” Linear Algebra Appl. 356 (2002), 157-187.
32. M. Tomiyama and N. Yamazaki, “The subconstituent algebra of a strongly regular graph,” Kyushu J. Math. 48 (1998), 323-334.
2. E. Bannai and N.J.A Sloane, “Uniqueness of certain spherical codes,” Canad. J. Math. 33 (1981), 437-449.
3. N. Biggs, Algebraic Graph Theory, Cambridge U. Press, London, 1994.
4. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
5. J.S. Caughman IV, “Spectra of bipartite P- and Q-polynomial association schemes,” Graphs Combin. 14 (1998), 321-343.
6. J.S. Caughman IV, “The Terwilliger algebras of bipartite P- and Q-polynomial association schemes,” Discrete Math. 196 (1999), 65-95.
7. B. Collins, “The girth of a thin distance-regular graph,” Graphs Combin. 13 (1997), 21-30.
8. B. Collins, “The Terwilliger algebra of an almost-bipartite distance-regular graph and its antipodal 2-cover,” Discrete Math. 216 (2000), 35-69.
9. B. Curtin, “Bipartite distance-regular graphs I,” Graphs Combin. 15 (1999), 143-158.
10. B. Curtin, “Bipartite distance-regular graphs II,” Graphs Combin. 15 (1999), 377-391.
11. B. Curtin, “2-homogeneous bipartite distance-regular graphs,” Discrete Math. 187 (1998), 39-70.
12. B. Curtin, “Distance-regular graphs which support a spin model are thin,” 16th British Combinatorial Conference (London, 1997). Discrete Math. 197/198 (1999), 205-216.
13. B. Curtin, “Almost 2-homogenous bipartite distance-regular graphs,” European J. Combin. 21 (2000), 865- 876.
14. B. Curtin and K. Nomura, “Distance-regular graphs related to the quantum enveloping algebra of sl(2),” J. Alg. Combin. 12 (2000), 25-36.
15. B. Curtin, “The local structure of a bipartite distance-regular graph,” European J. Combin. 20 (1999), 739-758.
16. C. Curtis and I. Reiner, Representation Theory of Finite Groups and Associative Algebras, Interscience, New York 1962.
17. G. Dickie, “Twice Q-polynomial distance-regular graphs are thin,” European J. Combin. 16 (1995), 555-560.
18. 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.
19. E. Egge, “A generalization of the Terwilliger algebra,” J. Algebra 233 (2000), 213-252.
20. E. Egge, “The generalized Terwilliger algebra and its finite dimensional modules when d = 2,” J. Algebra 250 (2002), 178-216.
21. J.T. Go, “The Terwilliger algebra of the hypercube,” European J. Combin. 23 (2002), 399-429.
22. J.T. Go and P. Terwilliger, “Tight distance-regular graphs and the subconstituent algebra,” European J. Combin. 23 (2002), 793-816.
23. C.D. Godsil. Algebraic Combinatorics, Chapman and Hall, Inc., New York, 1993.
24. 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.
25. A. Juri\check sić, J. Koolen and P. Terwilliger, “Tight distance-regular graphs,” J. Algebraic Combinatorics 12 (2000), 163-197.
26. K. Tanabe, “The irreducible modules of the Terwilliger algebras of Doob schemes,” J. Alg. Combin. 6 (1997), 173-195.
27. P. Terwilliger, “A new feasibility condition for distance-regular graphs,” Discrete Math. 61 (1986), 311-315. TERWILLIGER
28. P. Terwilliger, “The subconstituent algebra of an association scheme I,” J. Alg. Combin. 1 (1992), 363-388.
29. P. Terwilliger, “The subconstituent algebra of an association scheme II,” J. Alg. Combin. 2 (1993), 73-103.
30. P. Terwilliger, “The subconstituent algebra of an association scheme III,” J. Alg. Combin. 2 (1993), 177-210.
31. P. Terwilliger, “The subconstituent algebra of a distance-regular graph; thin modules with endpoint 1,” Linear Algebra Appl. 356 (2002), 157-187.
32. M. Tomiyama and N. Yamazaki, “The subconstituent algebra of a strongly regular graph,” Kyushu J. Math. 48 (1998), 323-334.