×

zbMATH — the first resource for mathematics

Scaffolds: a graph-theoretic tool for tensor computations related to Bose-Mesner algebras. (English) Zbl 1462.05362
Summary: We introduce a pictorial notation for certain tensors arising in the study of association schemes, based on earlier ideas of Terwilliger, Neumaier and Jaeger. These tensors, which we call “scaffolds”, obey a simple set of rules which generalize common linear-algebraic operations such as trace, matrix product and entrywise product. We first study an elementary set of “moves” on scaffolds and illustrate their use in combinatorics. Next we re-visit results of Dickie, Suzuki and Terwilliger. The main new results deal with the relationships among vector spaces of scaffolds with edge weights chosen from a fixed coherent algebra and various underlying diagrams. As one consequence, we provide simple descriptions of the Terwilliger algebras of triply regular and dually triply regular association schemes. We finish with a conjecture connecting the duality of Bose-Mesner algebras to the graph-theoretic duality of circular planar graphs.
MSC:
05E30 Association schemes, strongly regular graphs
15A72 Vector and tensor algebra, theory of invariants
16S50 Endomorphism rings; matrix rings
05C83 Graph minors
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bannai, E.; Ito, T., Algebraic Combinatorics I: Association Schemes (1984), Benjamin-Cummings: Benjamin-Cummings Menlo Park · Zbl 0555.05019
[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073
[3] Cameron, P. J.; Goethals, J.-M.; Seidel, J. J., The Krein condition, spherical designs, Norton algebras and permutation groups, Proc. K. Ned. Akad. Wet., Indag. Math., 40, 2, 196-206 (1978) · Zbl 0408.05016
[4] Coolsaet, K.; Jurišić, A., Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs, J. Comb. Theory, Ser. A, 115, 6, 1086-1095 (2008) · Zbl 1182.05132
[5] Curtis, E. B.; Ingerman, D.; Morrow, J. A., Circular planar graphs and resistor networks, Linear Algebra Appl., 283, 115-150 (1998) · Zbl 0931.05051
[6] van Dam, E. R.; Koolen, J. H.; Tanaka, H., Distance-regular graphs, Electron. J. Comb., DS22 (2016) · Zbl 1335.05062
[7] Delsarte, P., An algebraic approach to the association schemes of coding theory, Philips Res. Rep., Suppl., 10 (1973) · Zbl 1075.05606
[8] Dickie, G. A., Q-polynomial structures for association schemes and distance-regular graphs (1995), University of Wisconsin, Ph.D. thesis
[9] Diestel, R., Graph Theory (2005), Springer-Verlag: Springer-Verlag Heidelberg · Zbl 1074.05001
[10] Gavrilyuk, A. L.; Suda, S.; Vidali, J., On tight 4-designs in Hamming association schemes, Combinatorica, 40, 345-362 (2020) · Zbl 1463.05541
[11] Gitler, I.; López, I., On topological spin models and generalized \(\operatorname{\Delta} - Y\) transformations, Adv. Appl. Math., 32, 263-292 (2004) · Zbl 1053.05126
[12] Godsil, C. D., Algebraic Combinatorics (1993), Chapman and Hall: Chapman and Hall New York · Zbl 0814.05075
[13] Hestenes, M. D.; Higman, D. G., Rank 3 groups and strongly regular graphs, (Proc. Symp. Applied Math. (1971), Amer. Math. Soc.: Amer. Math. Soc. Providence RI), 141-160 · Zbl 0253.05127
[14] Jaeger, F., On spin models, triply regular association schemes, and duality, J. Algebraic Comb., 4, 103-144 (1995) · Zbl 0820.05063
[15] Lovász, L., Large Networks and Graph Limits, AMS Colloquium Publications, vol. 60 (2012), Amer. Math. Soc. · Zbl 1292.05001
[16] Martin, W. J.; Tanaka, H., Commutative association schemes, Eur. J. Comb., 30, 1497-1525 (2009) · Zbl 1228.05317
[17] Martin, W. J., Scaffolds: a graph-based system for computations in Bose-Mesner algebras (January 2020), preprint
[18] Penjić, S.; Neumaier, A., A unified view of inequalities for distance-regular graphs. Part I (2018), manuscript
[19] Penjić, S.; Neumaier, A., A unified view of inequalities for distance-regular graphs. Part II (2018), manuscript
[20] Reichard, S., Strongly regular graphs with the 7-vertex condition, J. Algebraic Comb., 41, 817-842 (2015) · Zbl 1314.05235
[21] Suzuki, H., Imprimitive Q-polynomial association schemes, J. Algebraic Comb., 7, 165-180 (1998) · Zbl 0974.05083
[22] Suzuki, H., Association schemes with multiple Q-polynomial structures, J. Algebraic Comb., 7, 181-196 (1998) · Zbl 0974.05082
[23] Terwilliger, P., A characterization of P- and Q-polynomial association schemes, J. Comb. Theory, Ser. A, 45, 8-26 (1987) · Zbl 0663.05016
[24] Terwilliger, P., The subconstituent algebra of an association scheme (part I), J. Algebraic Comb., 1, 363-388 (1992) · Zbl 0785.05089
[25] Terwilliger, P., Course lecture notes, Math 846 Algebraic Graph Theory, Spring term 2009, University of Wisconsin
[26] Truemper, K., On the delta-wye reduction for planar graphs, J. Graph Theory, 13, 141-148 (1989) · Zbl 0677.05020
[27] Zhao, D., On eigenmatrices of polynomial association schemes (2018), Lecture notes. G2R2@Novosibirsk, August 7
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.