# ALGEBRAIC COMBINATORICS

On symmetric association schemes and associated quotient-polynomial graphs
Algebraic Combinatorics, Volume 4 (2021) no. 6, pp. 947-969.

Let $\Gamma$ denote an undirected, connected, regular graph with vertex set $X$, adjacency matrix $A$, and $d+1$ distinct eigenvalues. Let $𝒜=𝒜\left(\Gamma \right)$ denote the subalgebra of ${\mathrm{Mat}}_{X}\left(ℂ\right)$ generated by $A$. We refer to $𝒜$ as the adjacency algebra of $\Gamma$. In this paper we investigate algebraic and combinatorial structure of $\Gamma$ for which the adjacency algebra $𝒜$ is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) $𝒜$ has a standard basis $\left\{I,{F}_{1},...,{F}_{d}\right\}$; (ii) for every vertex there exists identical distance-faithful intersection diagram of $\Gamma$ with $d+1$ cells; (iii) the graph $\Gamma$ is quotient-polynomial; and (iv) if we pick $F\in \left\{I,{F}_{1},...,{F}_{d}\right\}$ then $F$ has $d+1$ distinct eigenvalues if and only if $\mathrm{span}\left\{I,{F}_{1},...,{F}_{d}\right\}=\mathrm{span}\left\{I,F,...,{F}^{d}\right\}$. We describe the combinatorial structure of quotient-polynomial graphs with diameter $2$ and $4$ distinct eigenvalues. As a consequence of the techniques used in the paper, some simple algorithms allow us to decide whether $\Gamma$ is distance-regular or not and, more generally, which distance-$i$ matrices are polynomial in $A$, giving also these polynomials.

Revised:
Accepted:
Published online:
DOI: 10.5802/alco.187
Classification: 05E30,  05C50
Keywords: Symmetric association scheme, adjacency algebra, quotient-polynomial graph, intersection diagram.
Fiol, Miquel A. 1; Penjić, Safet 2

1 Departament de Matemàtiques Universitat Politécnica de Catalunya Barcelona Graduate School of Mathematics Institut de Matemàtiques de la UPC-BarcelonaTech (IMTech) Catalonia, Spain
2 University of Primorska Andrej Marušič Institute Muzejski trg 2 6000 Koper, Slovenia
@article{ALCO_2021__4_6_947_0,
author = {Fiol, Miquel A. and Penji\'c, Safet},
title = {On symmetric association schemes and associated quotient-polynomial graphs},
journal = {Algebraic Combinatorics},
pages = {947--969},
publisher = {MathOA foundation},
volume = {4},
number = {6},
year = {2021},
doi = {10.5802/alco.187},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.187/}
}
TY  - JOUR
TI  - On symmetric association schemes and associated quotient-polynomial graphs
JO  - Algebraic Combinatorics
PY  - 2021
DA  - 2021///
SP  - 947
EP  - 969
VL  - 4
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.187/
UR  - https://doi.org/10.5802/alco.187
DO  - 10.5802/alco.187
LA  - en
ID  - ALCO_2021__4_6_947_0
ER  - 
%0 Journal Article
%T On symmetric association schemes and associated quotient-polynomial graphs
%J Algebraic Combinatorics
%D 2021
%P 947-969
%V 4
%N 6
%I MathOA foundation
%U https://doi.org/10.5802/alco.187
%R 10.5802/alco.187
%G en
%F ALCO_2021__4_6_947_0
Fiol, Miquel A.; Penjić, Safet. On symmetric association schemes and associated quotient-polynomial graphs. Algebraic Combinatorics, Volume 4 (2021) no. 6, pp. 947-969. doi : 10.5802/alco.187. https://alco.centre-mersenne.org/articles/10.5802/alco.187/

[1] Abiad, Aida; Dalfó, Cristina; Fiol, Miquel Àngel Algebraic characterizations of regularity properties in bipartite graphs, European J. Combin., Volume 34 (2013) no. 8, pp. 1223-1231 | Article | MR: 3082194 | Zbl: 1292.05273

[2] Abiad, Aida; Dalfó, Cristina; Fiol, Miquel Àngel Corrigendum to “Algebraic characterizations of regularity properties in bipartite graphs” [European J. Combin. 34 (2013) 1223–1231][MR3082194], European J. Combin., Volume 38 (2014), pp. 130-132 | Article | MR: 3149687 | Zbl: 1295.05270

[3] Axler, Sheldon Linear algebra done right, Undergraduate Texts in Mathematics, Springer, Cham, 2015, xviii+340 pages | Article | MR: 3308468 | Zbl: 1304.15001

[4] Bailey, Rosemary A. Association schemes. Designed experiments, algebra and combinatorics, Cambridge Studies in Advanced Mathematics, 84, Cambridge University Press, Cambridge, 2004, xviii+387 pages | Article | MR: 2047311

[5] Bannai, Eiichi; Ito, Tatsuro Algebraic combinatorics. I, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984, xxiv+425 pages | MR: 882540 | Zbl: 0555.05019

[6] Biggs, Norman Algebraic graph theory, Cambridge Tracts in Mathematics, Cambridge University Press, London, 1974 no. 67, vii+170 pages | MR: 0347649 | Zbl: 0284.05101

[7] Bose, Raj C.; Mesner, Dale M. On linear associative algebras corresponding to association schemes of partially balanced designs, Ann. Math. Statist., Volume 30 (1959), pp. 21-38 | Article | MR: 102157 | Zbl: 0089.15002

[8] Brouwer, Andries E.; Cohen, Arjeh M.; Neumaier, Arnold Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], 18, Springer-Verlag, Berlin, 1989, xviii+495 pages | Article | MR: 1002568 | Zbl: 0747.05073

[9] Brouwer, Andries E.; Haemers, Willem H. Spectra of graphs, Universitext, Springer, New York, 2012, xiv+250 pages | Article | MR: 2882891 | Zbl: 1231.05001

[10] Cameron, Peter J.; Lint, Jacobus H. van Designs, graphs, codes and their links, London Mathematical Society Student Texts, 22, Cambridge University Press, Cambridge, 1991, x+240 pages | Article | MR: 1148891 | Zbl: 0743.05004

[11] Caughman, John S. IV; Wolff, Nadine The Terwilliger algebra of a distance-regular graph that supports a spin model, J. Algebraic Combin., Volume 21 (2005) no. 3, pp. 289-310 | Article | MR: 2142841 | Zbl: 1064.05152

[12] Dalfó, Cristina; Dam, Edwin R. van; Fiol, Miquel A.; Garriga, Ernest; Gorissen, Bram L. On almost distance-regular graphs, J. Combin. Theory Ser. A, Volume 118 (2011) no. 3, pp. 1094-1113 | Article | MR: 2763058 | Zbl: 1225.05249

[13] Dalfó, Cristina; Fiol, Miquel A. A general method to obtain the spectrum and local spectra of a graph from its regular partitions, Electron. J. Linear Algebra, Volume 36 (2020), pp. 446-460 | Article | MR: 4123950

[14] Dam, Edwin R. van Three-class association schemes, J. Algebraic Combin., Volume 10 (1999) no. 1, pp. 69-107 | Article | MR: 1701285 | Zbl: 0929.05096

[15] Dam, Edwin R. van The spectral excess theorem for distance-regular graphs: a global (over)view, Electron. J. Combin., Volume 15 (2008) no. 1, Paper no. Research Paper 129, 10 pages | Article | MR: 2448879 | Zbl: 1180.05130

[16] Dam, Edwin R. van; Koolen, Jack H.; Tanaka, Hajime Distance-regular graphs, Dynamic Surveys, Electron. J. Combin., 2016, 156 pages | Article | Zbl: 1335.05062

[17] Delsarte, Philippe An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. (1973) no. 10, p. vi+97 | MR: 384310 | Zbl: 1075.05606

[18] Delsarte, Philippe; Levenshtein, Vladimir I. Association schemes and coding theory, IEEE Trans. Inform. Theory, Volume 44 (1998) no. 6, pp. 2477-2504 (Information theory: 1948–1998) | Article | MR: 1658771 | Zbl: 0946.05086

[19] Dickie, Garth A. $Q$-polynomial structures for association schemes and distance-regular graphs (1995) (Ph. D. Thesis) | MR: 2693006

[20] Evdokimov, Sergei; Ponomarenko, Ilia Permutation group approach to association schemes, European J. Combin., Volume 30 (2009) no. 6, pp. 1456-1476 | Article | MR: 2535396 | Zbl: 1228.05311

[21] Ferguson, Pamela A.; Turull, Alexandre Algebraic decompositions of commutative association schemes, J. Algebra, Volume 96 (1985) no. 1, pp. 211-229 | Article | MR: 808849 | Zbl: 0573.20051

[22] Filipovski, Slobodan A lower bound for the discriminant of polynomials related to Chebyshev polynomials, Discrete Math., Volume 344 (2021) no. 3, Paper no. 112235, 6 pages | Article | MR: 4179000 | Zbl: 07302662

[23] Fiol, Miquel A. Eigenvalue interlacing and weight parameters of graphs, Linear Algebra Appl., Volume 290 (1999) no. 1-3, pp. 275-301 | Article | MR: 1673001 | Zbl: 0933.05099

[24] Fiol, Miquel A. On pseudo-distance-regularity, Linear Algebra Appl., Volume 323 (2001) no. 1-3, pp. 145-165 | Article | MR: 1809765 | Zbl: 0978.05050

[25] Fiol, Miquel A. Algebraic characterizations of distance-regular graphs, Discrete Math., Volume 246 (2002) no. 1-3, pp. 111-129 Formal power series and algebraic combinatorics (Barcelona, 1999) | Article | MR: 1887483 | Zbl: 1025.05060

[26] Fiol, Miquel A. Quotient-polynomial graphs, Linear Algebra Appl., Volume 488 (2016), pp. 363-376 | Article | MR: 3419791 | Zbl: 1326.05174

[27] Fiol, Miquel A.; Gago, Silvia; Garriga, Ernest A simple proof of the spectral excess theorem for distance-regular graphs, Linear Algebra Appl., Volume 432 (2010) no. 9, pp. 2418-2422 | Article | MR: 2599871

[28] Fiol, Miquel A.; Garriga, Ernest From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, Volume 71 (1997) no. 2, pp. 162-183 | Article | MR: 1483473 | Zbl: 0888.05056

[29] Fiol, Miquel A.; Garriga, Ernest; Yebra, J. Luis A. Locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, Volume 68 (1996) no. 2, pp. 179-205 | Article | MR: 1417795 | Zbl: 0861.05064

[30] Fiol, Miquel A.; Penjić, Safet On a version of the spectral excess theorem, Electron. J. Graph Theory Appl. (EJGTA), Volume 8 (2020) no. 2, pp. 391-400 | Article | MR: 4174841

[31] Friedland, Shmuel Coherent algebras and the graph isomorphism problem, Discrete Appl. Math., Volume 25 (1989) no. 1-2, pp. 73-98 Combinatorics and complexity (Chicago, IL, 1987) | Article | MR: 1031264 | Zbl: 0704.05023

[32] Godsil, Christopher D. Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993, xvi+362 pages | MR: 1220704 | Zbl: 0784.05001

[33] Goldberg, Felix On quasi-strongly regular graphs, Linear Multilinear Algebra, Volume 54 (2006) no. 6, pp. 437-451 | Article | MR: 2259601 | Zbl: 1108.05097

[34] Higman, Donald G. Coherent configurations. I. Ordinary representation theory, Geometriae Dedicata, Volume 4 (1975) no. 1, pp. 1-32 | Article | MR: 398868 | Zbl: 0333.05010

[35] Higman, Donald G. Coherent algebras, Linear Algebra Appl., Volume 93 (1987), pp. 209-239 | Article | MR: 898557 | Zbl: 0618.05014

[36] Hoffman, Alan J. On the polynomial of a graph, Amer. Math. Monthly, Volume 70 (1963), pp. 30-36 | Article | MR: 156333 | Zbl: 0112.14901

[37] Horn, Roger A.; Johnson, Charles R. Matrix analysis, Cambridge University Press, Cambridge, 2013, xviii+643 pages | MR: 2978290 | Zbl: 1267.15001

[38] Isbell, John R. On coherent algebras and strict algebras, J. Algebra, Volume 13 (1969), pp. 299-307 | Article | MR: 249484 | Zbl: 0181.31503

[39] Jones, Gareth A.; Klin, Mikhail; Moshe, Yossi Primitivity of permutation groups, coherent algebras and matrices, J. Combin. Theory Ser. A, Volume 98 (2002) no. 1, pp. 210-217 | Article | MR: 1897935 | Zbl: 1011.20003

[40] Kharaghani, Hadi; Suda, Sho Commutative association schemes obtained from twin prime powers, Fermat primes, Mersenne primes, Finite Fields Appl., Volume 63 (2020), Paper no. 101631, 22 pages | Article | MR: 4053825 | Zbl: 1433.05334

[41] Klin, Mikhail; Munemasa, Akihiro; Muzychuk, Mikhail; Zieschang, Paul-Hermann Directed strongly regular graphs obtained from coherent algebras, Linear Algebra Appl., Volume 377 (2004), pp. 83-109 | Article | MR: 2021604 | Zbl: 1030.05119

[42] Klin, Mikhail; Rücker, Christoph; Rücker, Gerta; Tinhofer, Gottfried Algebraic combinatorics in mathematical chemistry. Methods and algorithms. I. Permutation groups and coherent (cellular) algebras, Match (1999) no. 40, pp. 7-138 | MR: 1729482 | Zbl: 1029.05151

[43] Laub, Alan J. Matrix analysis for scientists & engineers, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005, xiv+157 pages | Article | MR: 2128817 | Zbl: 1077.15001

[44] Lint, Jacobus H. van; Wilson, Richard M. A course in combinatorics, Cambridge University Press, Cambridge, 2001, xiv+602 pages | Article | MR: 1871828 | Zbl: 0980.05001

[45] MacLean, Mark S.; Miklavič, Štefko On bipartite distance-regular graphs with exactly one non-thin $T$-module with endpoint two, European J. Combin., Volume 64 (2017), pp. 125-137 | Article | MR: 3658824 | Zbl: 1365.05078

[46] MacLean, Mark S.; Miklavič, Štefko On bipartite distance-regular graphs with exactly two irreducible T-modules with endpoint two, Linear Algebra Appl., Volume 515 (2017), pp. 275-297 | Article | MR: 3588548 | Zbl: 1352.05196

[47] MacLean, Mark S.; Miklavič, Štefko; Penjić, Safet On the Terwilliger algebra of bipartite distance-regular graphs with ${\Delta }_{2}=0$ and ${c}_{2}=1$, Linear Algebra Appl., Volume 496 (2016), pp. 307-330 | Article | MR: 3464074 | Zbl: 1331.05237

[48] MacLean, Mark S.; Miklavič, Štefko; Penjić, Safet An $A$-invariant subspace for bipartite distance-regular graphs with exactly two irreducible $T$-modules with endpoint 2, both thin, J. Algebraic Combin., Volume 48 (2018) no. 3, pp. 511-548 | Article | MR: 3864738 | Zbl: 1404.05042

[49] MacWilliams, F. Jessie; Sloane, Neil J. A. The theory of error-correcting codes. I, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977, p. i-xv and 1–369 | MR: 0465509

[50] Martin, William J. Scaffolds: a graph-theoretic tool for tensor computations related to Bose-Mesner algebras, Linear Algebra Appl., Volume 619 (2021), pp. 50-106 | Article | MR: 4223362 | Zbl: 07337639

[51] Martin, William J.; Tanaka, Hajime Commutative association schemes, European J. Combin., Volume 30 (2009) no. 6, pp. 1497-1525 | Article | MR: 2535398 | Zbl: 1228.05317

[52] Miklavič, Štefko On bipartite $Q$-polynomial distance-regular graphs with diameter 9, 10, or 11, Electron. J. Combin., Volume 25 (2018) no. 1, Paper no. P1.52, 12 pages | Article | MR: 3785031 | Zbl: 1391.05174

[53] Morales, John Vincent S. On Lee association schemes over ${ℤ}_{4}$ and their Terwilliger algebra, Linear Algebra Appl., Volume 510 (2016), pp. 311-328 | Article | MR: 3551635 | Zbl: 1352.05197

[54] Muzychuk, Mikhail; Xu, Bangteng Terwilliger algebras of wreath products of association schemes, Linear Algebra Appl., Volume 493 (2016), pp. 146-163 | Article | MR: 3452732 | Zbl: 1329.05313

[55] Neumaier, Arnold Krein conditions and near polygons, J. Combin. Theory Ser. A, Volume 54 (1990) no. 2, pp. 201-209 | Article | MR: 1059995 | Zbl: 0738.05025

[56] Penjić, Safet On the Terwilliger algebra of bipartite distance-regular graphs with ${𝛥}_{2}=0$ and ${c}_{2}=2$, Discrete Math., Volume 340 (2017) no. 3, pp. 452-466 | Article | MR: 3584832 | Zbl: 1351.05066

[57] Penjić, Safet On the Terwilliger algebra of bipartite distance-regular graphs (2019), x+107 pages (https://osebje.famnit.upr.si/~penjic/research/) (Ph. D. Thesis)

[58] Qiao, Zhi; Du, Shao Fei; Koolen, Jack H. 2-walk-regular dihedrants from group divisible designs, Electron. J. Combin., Volume 23 (2016) no. 2, Paper no. P2.51, 11 pages | Article | MR: 3522135 | Zbl: 1339.05098

[59] Rowlinson, Peter Linear algebra, Graph connections (Oxford Lecture Ser. Math. Appl.), Volume 5, Oxford Univ. Press, New York, 1997, pp. 86-99 | MR: 1634548 | Zbl: 0878.05059

[60] Sankey, Alyssa D. Weighted association schemes, fusions, and minimal coherent closures, J. Algebraic Combin., Volume 41 (2015) no. 3, pp. 785-815 | Article | MR: 3328180 | Zbl: 1332.05156

[61] Sankey, Alyssa D. On $t$-fold covers of coherent configurations, Ars Math. Contemp., Volume 14 (2018) no. 2, pp. 397-413 | Article | MR: 3812029 | Zbl: 1393.05141

[62] Stadler, Peter F.; Tinhofer, Gottfried Equitable partitions, coherent algebras and random walks: applications to the correlation structure of landscapes, Match (1999) no. 40, pp. 215-261 | MR: 1729486 | Zbl: 1029.05128

[63] Suda, Sho Coherent configurations and triply regular association schemes obtained from spherical designs, J. Combin. Theory Ser. A, Volume 117 (2010) no. 8, pp. 1178-1194 | Article | MR: 2677683 | Zbl: 1206.05105

[64] Terwilliger, Paul The subconstituent algebra of an association scheme. I, J. Algebraic Combin., Volume 1 (1992) no. 4, pp. 363-388 | Article | MR: 1203683 | Zbl: 0785.05089

[65] Terwilliger, Paul The subconstituent algebra of an association scheme. II, J. Algebraic Combin., Volume 2 (1993) no. 1, pp. 73-103 | Article | MR: 1210403 | Zbl: 0785.05090

[66] Terwilliger, Paul The subconstituent algebra of an association scheme. III, J. Algebraic Combin., Volume 2 (1993) no. 2, pp. 177-210 | Article | MR: 1229433 | Zbl: 0785.05091

[67] Terwilliger, Paul A new inequality for distance-regular graphs, Discrete Math., Volume 137 (1995) no. 1-3, pp. 319-332 | Article | MR: 1312463 | Zbl: 0814.05074

[68] Terwilliger, Paul Algebraic graph theory (MATH 846) (January 2009) (Lecture notes, University of Wisconsin, https://www.math.wisc.edu/~terwilli/teaching.html)

[69] Veĭsfeĭler, Boris Ju.; Leman, Andrey A. A reduction of a graph to canonical form and an algebra arising during this reduction, NTI, Volume 9 (1968), pp. 12-16 https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf

[70] Weichsel, Paul M. The Kronecker product of graphs, Proc. Amer. Math. Soc., Volume 13 (1962), pp. 47-52 | Article | MR: 133816 | Zbl: 0102.38801

[71] Weichsel, Paul M. On distance-regularity in graphs, J. Combin. Theory Ser. B, Volume 32 (1982) no. 2, pp. 156-161 | Article | MR: 657684 | Zbl: 0477.05047

[72] Xu, Bangteng Pseudo-direct sums and wreath products of loose-coherent algebras with applications to coherent configurations, Linear Algebra Appl., Volume 530 (2017), pp. 202-219 | Article | MR: 3672956 | Zbl: 1368.16038

Cited by Sources: