On symmetric association schemes and associated quotient-polynomial graphs

Fiol, Miquel A.; Penjić, Safet

doi:10.5802/alco.187

Fiol, Miquel A.¹; Penjić, Safet ²

¹ 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
² University of Primorska Andrej Marušič Institute Muzejski trg 2 6000 Koper, Slovenia

Algebraic Combinatorics, Volume 4 (2021) no. 6, pp. 947-969.

Abstract

Let $Γ$ denote an undirected, connected, regular graph with vertex set $X$ , adjacency matrix $A$ , and $d + 1$ distinct eigenvalues. Let $𝒜 = 𝒜 (Γ)$ denote the subalgebra of ${Mat}_{X} (ℂ)$ generated by $A$ . We refer to $𝒜$ as the adjacency algebra of $Γ$ . In this paper we investigate algebraic and combinatorial structure of $Γ$ 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 ${I, F_{1}, ..., F_{d}}$ ; (ii) for every vertex there exists identical distance-faithful intersection diagram of $Γ$ with $d + 1$ cells; (iii) the graph $Γ$ is quotient-polynomial; and (iv) if we pick $F \in {I, F_{1}, ..., F_{d}}$ then $F$ has $d + 1$ distinct eigenvalues if and only if $span {I, F_{1}, ..., F_{d}} = span {I, F, ..., F^{d}}$ . 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 $Γ$ is distance-regular or not and, more generally, which distance- $i$ matrices are polynomial in $A$ , giving also these polynomials.

Received: 2020-09-15
Revised: 2021-01-31
Accepted: 2021-06-02
Published online: 2022-01-04

DOI: 10.5802/alco.187

Classification: 05E30, 05C50
Keywords: Symmetric association scheme, adjacency algebra, quotient-polynomial graph, intersection diagram.

Author's affiliations:

Fiol, Miquel A. ¹; Penjić, Safet ²

¹ 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
² University of Primorska Andrej Marušič Institute Muzejski trg 2 6000 Koper, Slovenia

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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
AU  - Fiol, Miquel A.
AU  - Penjić, Safet
TI  - On symmetric association schemes and associated quotient-polynomial graphs
JO  - Algebraic Combinatorics
PY  - 2021
SP  - 947
EP  - 969
VL  - 4
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.187/
DO  - 10.5802/alco.187
LA  - en
ID  - ALCO_2021__4_6_947_0
ER  -

%0 Journal Article
%A Fiol, Miquel A.
%A Penjić, Safet
%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://alco.centre-mersenne.org/articles/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/

References
Cited by

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR

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

[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 | DOI | MR | Zbl

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

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

[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) | DOI | MR | Zbl

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

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

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

[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 | DOI | MR | Zbl

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

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

[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) | DOI | MR | Zbl

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

[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 | DOI | MR

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR

[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) | DOI | MR | Zbl

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

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

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

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

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

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

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

[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 | Zbl

[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 | DOI | MR | Zbl

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

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

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

Cited by Sources: