Algorithm for describing the Terwilliger and quantum adjacency algebras of a distance-regular graph

Document Type : Original paper

Authors

1 Master Program in Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

2 Department of Mathematics and Statistics, De La Salle University, Manila, Philippines

3 Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

Abstract

In this paper we consider an algorithm for determining a basis for the Terwilliger and quantum adjacency algebras of a distance-regular graph. For the Terwilliger algebra, we consider the generating set. For the quantum adjacency algebra, we consider the generating set consisting of the raising, flat, and lowering matrices. We give optimization method by using generating matrices with a block-matrix structure so that the number of matrix multiplications required is reduced.

Keywords

Main Subjects

References

[1] J. Alman and V.V. Williams, A refined laser method and faster matrix multiplication, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) (D. Marx, ed.), SIAM, 2024, pp. 522 – 539. https://doi.org/10.1137/1.9781611976465.32
[2] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings, 1984.
[3] B. Fernández and Š. Miklavič, On the terwilliger algebra of distance-biregular graphs, Linear Algebra Appl. 597 (2020), 18–32.  https://doi.org/10.1016/j.laa.2020.03.016
[4] B. Fernández and Š. Miklavič, On bipartite graphs with exactly one irreducible T-module with endpoint 1, which is thin, European J. Combin. 97 (2021), 103387. https://doi.org/10.1016/j.ejc.2021.103387
[5] J.M. Goethals and J.J. Seidel, Strongly regular graphs derived from combinatorial designs, Canad. J. Math. 22 (1970), no. 3, 597–614.  https://doi.org/10.4153/CJM-1970-067-9
[6] A. Hanaki and M. Yoshikawa, Terwilliger algebras and some related algebras defined by finite connected simple graphs, Discrete Math. 346 (2023), no. 9, 113509.  https://doi.org/10.1016/j.disc.2023.113509
[7] A. Hora and N. Obata, Quantum Probability and Spectral Analysis of Graphs, Springer, Berlin, 2007.
[8] S.D. Li, Y.Z. Fan, T. Ito, M. Karimi, and J. Xu, The isomorphism problem of trees from the viewpoint of terwilliger algebras, J. Combin. Theory Ser. A 177 (2021), 105328.  https://doi.org/10.1016/j.jcta.2020.105328
[9] Y. Tan, Y. Zhang, T. Xia, and X. Liang, Terwilliger algebras of a fan graph, Journal of Hefei University of Technology Natural Science Edition 46 (2023),  no. 3, 419–425.
[10] P. Terwilliger, The subconstituent algebra of an association scheme,(part I), J. Algebraic Combin. 1 (1992), no. 4, 363–388.  https://doi.org/10.1023/A:1022494701663
[11] P. Terwilliger and A. Žitnik, The quantum adjacency algebra and subconstituent algebra of a graph, J. Combin. Theory Ser. A 166 (2019), 297–314. https://doi.org/10.1016/j.jcta.2019.02.022
[12] J. Xu, T. Ito, and S.D. Li, Irreducible representations of the Terwilliger algebra of a tree, Graphs Combin. 37 (2021), no. 5, 1749–1773.  https://doi.org/10.1007/s00373-021-02384-9
Communications in Combinatorics and Optimization
Volume 11, Issue 3
September 2026
Pages 975-984

Files

Share

How to cite

Statistics