Book Review: “Algebraic Combinatorics” by Eiichi Bannai, Etsuko Bannai, Tatsuro Ito and Rie Tanaka

The book under review is a most welcome, completely revised, widely expanded, and updated version of the celebrated and most influential book Algebraic Combinatorics I; Association Schemes [⁠2⁠ E. Bannai and T. Ito, Algebraic combinatorics. I. The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA (1984) ] by Eiichi Bannai and Tatsuro Ito, published in 1984.

According to these authors, Algebraic Combinatorics is “the approach to combinatorics which was formulated in P. Delsarte’s monumental thesis [⁠3⁠ P. Delsarte, An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. 10, Ann Arbor (1973) ] in 1973, enabling us to look at a wide range of combinatorial problems from a unified viewpoint”. As stated immediately thereafter, “the origins of this approach can be found in the previous work on character theory of finite groups and permutation group theory by I. Schur, G. F. Frobenius, and W. Burnside as well as in that on experimental designs and association schemes by R. C. Bose”. This unified approach intertwines algebraic aspects of graph theory, coding theory, design theory, and finite geometries, with methods of Schur rings and of intersection matrices in permutation group theory. All this said, one may define Algebraic Combinatorics as “a group theory without groups”! To justify this statement and, possibly, give the reader a taste of the mathematics involved, we limit ourselves to present the definition of the central and unifying concept of the theory, namely of an association scheme, together with a couple of examples.

An association scheme is a pair $\mathfrak{X}=(X,\mathcal{R})$ where $X$ is a finite set and $\mathcal{R}=(R_j{)}_{j=0}^N$ is a partition of $X\times X$, where the sets $R_j$, called the associate classes, satisfy the following properties:

1. $R_0=\{(x,x):x\in X\}$ is the diagonal;

2. for each $j=1,2,\dots ,N$, there exists $1\le j^{\ast }\le N$ such that $R_{j^{\ast }}=\{(y,x)\in X\times X:(x,y)\in R_j\}$;

3. there exist nonnegative integers $p_{i,j}^k$, $i,j,k=0,1,\dots ,N$, called the parameters, such that $|\{z\in X:(x,z)\in R_i,(z,y)\in R_j\}|=p_{i,j}^k$ for all $(x,y)\in R_k$.

An association scheme $\mathfrak{X}$ is said to be commutative (resp. symmetric) provided that $p_{i,j}^k=p_{j,i}^k$ (resp. $R_j=R_{j^{\ast }}$) for all $0\le i,j,k\le N$. Note that symmetry implies commutativity. The matrices $A_j=(A_j(x,y){)}_{x,y\in X}$, $j=0,1,\dots ,N$, defined by setting

generate a subalgebra $\mathcal{A}\subseteq \mathrm{End}(\mathbb{C}[X])$, called the adjacency algebra (or Bose–Mesner algebra when it is commutative) associated with $\mathfrak{X}$.

Let us give a few examples. Let $G$ be a finite group. Then setting $R_g:=\{(x,y)\in G\times G:x^{-1}y=g\}$ for all $g\in G$ yields an association scheme whose associated adjacency algebra is isomorphic to the group algebra $\mathbb{C}[G]$ of $G$. Also, if $K\le G$ is a subgroup, then $G$ acts transitively on the coset space $X=G/K$ yielding an association scheme $\mathfrak{X}$ whose associated classes are the $G$-orbits on $X\times X$ and whose adjacency algebra is isomorphic to the subalgebra of bi-$K$-invariant functions in $\mathbb{C}[G]$; moreover, $\mathfrak{X}$ is commutative exactly if $(G,K)$ is a Gelfand pair (this is an important notion in Harmonic Analysis: it was used by Diaconis in his applications of Representation Theory to Probability and Statistics [⁠4⁠ P. Diaconis, Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes—Monograph Series 11, Institute of Mathematical Statistics, Hayward, CA (1988) ]). Finally, a finite regular undirected graph $\mathcal{G}=(X,E)$ with no loops is called distance-regular if there exist two sequences of constants, called the parameters, $(b_0,b_1,\dots ,b_N)$ and $(c_0,c_1,\dots ,c_N)$, where $N$ is the diameter of $\mathcal{G}$, such that, for any pair of vertices $x,y\in X$ with graph distance $d(x,y)=i$ one has

for all $i=0,1,\dots ,N$. Setting $R_i:=\{(x,y)\in X\times X:d(x,y)=i\}$, for $i=0,1,\dots ,N$, yields a symmetric association scheme. The corresponding Bose–Mesner algebra is singly-generated by $A_1$; in fact, for every $i=0,1,\dots ,N$ there exists a polynomial $p_i\in \mathbb{R}[t]$ of degree $i$ such that $A_i=p_i(A_1)$. This is a prototype of a so-called P-polynomial scheme.

The history of this monograph is, briefly, as follows. The original project of “Algebraic Combinatorics” as the first comprehensive and foundational treatment of the theory, consisted of two parts: the first one [⁠2⁠ E. Bannai and T. Ito, Algebraic combinatorics. I. The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA (1984) ], on “Association Schemes” – lecture notes based on graduate courses given by Eiichi Bannai during his professorship at The Ohio State University (1978–1982) and arranged in collaboration with Tatsuro Ito – included: (1) Representations of finite groups, (2) Association schemes, and (3) Distance-regular graphs, and P- and Q-polynomial association schemes. A second part, on “Delsarte Theory, Codes and Designs”, should have been published a couple of years later, but – “as the developments seemed not sufficient to complete a book and, at the same time, the range of mathematical objects they were interested in had expanded too widely to be handled” – it has never come to light. However, in 1999 the first two named authors published (in Japanese) Algebraic Combinatorics on Spheres [⁠1⁠ E. Bannai and E. Bannai, Algebraic Combinatorics on Spheres (Japanese). Springer, Tokyo (1999) ] which was not translated into English, as the original plan to write the sequel to [⁠2⁠ E. Bannai and T. Ito, Algebraic combinatorics. I. The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA (1984) ] was still alive.

The present book under review is the English translation, with the cooperation of Rie Tanaka – herself a mathematician working on association schemes – of the book Introduction to Algebraic Combinatorics by the first three named authors, published in Japanese in 2016. As we have mentioned at the beginning, it is not a sequel to [⁠2⁠ E. Bannai and T. Ito, Algebraic combinatorics. I. The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA (1984) ] but, rather, a completely revised, widely expanded, and updated version of it, serving – this is the clear intent of the authors – as a “preparation for a second part to be hopefully accomplished by the younger generations of algebraic combinatorialists” coming from the flourishing school the authors have initiated in the US, in Japan, and in China during their life carriers (according to the Mathematics Genealogy Project, just Eiichi Bannai has 31 students and 60 descendants).

The contents of the book, according to its subdivision into chapters, are as follows:

1. Classical design theory and classical coding theory (including an introduction to graph theory);

2. Association schemes, Bose–Mesner algebras, and Terwilliger algebras;

3. Codes and designs in association schemes (Delsarte theory on association schemes);

4. Codes and designs in association schemes (continued);

5. Algebraic combinatorics on spheres and general remarks on algebraic combinatorics;

6. P- and Q-polynomial schemes.

The writing is very elegant, both in the style of the authors and in the graphic design of De Gruyter, the exposition is crystal clear – the proofs are carefully detailed, and plenty of worked-out examples, often described by beautiful pictures, friendly turn the reader familiar with the concepts gradually introduced – reflecting at the same time the deepest and masterful knowledge of the subject by the authors as well as their long didactic experience. For this reason, the book may be used as an excellent text for advanced undergraduate and graduate courses on Algebraic Combinatorics, and, at the same time, may also serve as a most precious reference for the more advanced and mature mathematician. The authors clearly enjoyed writing it: I am sure that all readers will enjoy reading it as well.

Eiichi Bannai, Etsuko Bannai, Tatsuro Ito and Rie Tanaka, Algebraic Combinatorics. De Gruyter Series in Discrete Mathematics and Applications 5, De Gruyter, 2021, 444 pages, Hardback ISBN 978-3-1106-2763-3, eBook ISBN 978-3-1106-3025-1

Tullio Ceccherini-Silberstein is a professor of mathematical analysis at the University of Sannio (Italy). His interests lie within harmonic and functional analysis, geometric and combinatorial group theory, dynamical systems and ergodic theory, and theoretical computer science. tullio.cs@sbai.uniroma1.it

References

1. E. Bannai and E. Bannai, Algebraic Combinatorics on Spheres (Japanese). Springer, Tokyo (1999)
2. E. Bannai and T. Ito, Algebraic combinatorics. I. The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA (1984)
3. P. Delsarte, An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. 10, Ann Arbor (1973)
4. P. Diaconis, Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes—Monograph Series 11, Institute of Mathematical Statistics, Hayward, CA (1988)