Algebraic combinatorics. I: Association schemes.

*(English)*Zbl 0555.05019
Mathematics Lecture Note Series. Menlo Park, California etc.: The Benjamin/Cummings Publishing Company, Inc. Advanced Book Program. XXIV, 425 p. (1984).

The main theme of the book is the abstract theory of general association schemes, its relations to group theory, and the state of the classification problem for (P and Q)-polynomial association schemes of large diameter. In the last 15 years, this has become a very active and exciting research topic. In the authors’ words: ”The purpose of these lecture notes is to give a systematic account of Algebraic Combinatorics. Here we mean by Algebraic Combinatorics the approach to combinatorics which was formulated in Delsarte’s monumental thesis.... One important source is found in group theory, in particular in the work of Issai Schur.... However, since this area is progressing faster than we expected, we are afraid that we will have to update these lecture notes as soon as they are published.”

The main title ”Algebraic Combinatorics” is somewhat misleading: this can be seen e.g. from the fact that the contents is almost disjoint with that of N. L. Biggs [Algebraic graph theory (1974; Zbl 0284.05101)]. In particular, a lot of important recent research on locally 2-transitive graphs (among others by Cameron, Gardiner, Goldschmidt, Weiss) does not fit into the authors’ view of algebraic combinatorics. However, in the topics treated, the book is very detailed.

The book starts in Chapter I (Representations of finite groups) with an elementary introduction to ordinary group representation theory; as the authors write, the treatment is almost a translation of Chapter 6 of the Japanese book by K. Asano and H. Nagao [Group Theory (1965)]. The intention of the chapter is to provide a group theoretic background which gives some intuition for concepts introduced later for association schemes; e.g., the character table of a finite group appears later as the eigenmatrix of a corresponding association scheme.

The main topic is introduced in Chapter II (Association schemes). The basic theory of association schemes is established in Sections 2.1-2.6 (covering centralizer rings, adjacency algebras, nonexistence conditions, duality, and Schur rings) and 2.9 (imprimitivity); the remaining sections treat more peripheral topics (McKay’s observation, Norton algebras, noncommutative duality, Hecke algebras and spherical functions).

Chapter III (Distance regular graphs and (P and Q)-polynomial association schemes) is much more specialized. It contains a number of successful steps in the direction of the authors’ aim to classify the most structured class of association schemes, those with the P-polynomial and Q-polynomial property. These properties, dual to each other, were introduced by Delsarte; they are shared by the Hamming schemes, the Johnson schemes, and a number of other highly geometric schemes related to classical groups and certain simple groups of Lie type. It is very likely that most or even all (P and Q)-polynomial schemes of diameter \(d>6\) are known, and the problem of characterizing them is perhaps the most challenging problem in the theory of association schemes. P- polynomial association schemes are equivalent with distance regular graphs, i.e. graphs where the number of vertices at distance i from a vertex x and at distance j from a vertex y depends only in i, j and the distance of x and y.

(However, this book says very little about distance regular graphs of small diameter. Also, as the authors mention in the introduction, they leave the geometry of distance regular graphs to a book which is being prepared by A. Brouwer, A. Cohen and the reviewer.) Specifically, the third chapter gives in Section 3.1-3.7 basic properties of distance regular graphs, nonexistence theorems for Moore graphs and generalized polygons, the case of two P-polynomial structures, explicit parameters for (P and Q)-polynomial schemes, a (for \(d>6\) probably complete) list of families of (P and Q)-polynomial schemes, and a proof that (P and Q)- polynomial schemes of diameter \(d\geq 34\) and valency \(k\geq 2\) have integral eigenvalues. (Note: in Theorem 6.4, \(\chi\) must be assumed imprimitive).

The final Section 3.8 outlines the work remaining to be done in order to complete the classification and surveys the partial results available. Several of the problems mentioned in Section 3.8 have been solved in the meantime; this shows the timeliness of the book. The speed of development forced the authors into a hurry to publish the book. Unfortunately it often resulted in a rather preliminary style; e.g. the statement of the main theorem III.5.1 takes 12 pages (!), and many formulae are rather messy. In the authors’ words: ”We decided to hurry the publication in the hope that we could help those who are trying to start their own research in this area, as there seems no comprehensive treatment available on this topic at the present time other than original papers scattered in various journals and publications. We admit a lot of material is left in these lecture notes to be polished and improved both mathematically and in exposition. To help and to stimulate further research in this area are the only possible raison d’être of these lecture notes... We plan to update and improve these lecture notes to make their final version a more solid book form in some near future.”

In spite of these drawbacks this is an interesting and nourishing book for anyone interested in association schemes. There are a lot of formulated research problems, and the more than 400 references also make it a useful guide to the literature on the subject.

The main title ”Algebraic Combinatorics” is somewhat misleading: this can be seen e.g. from the fact that the contents is almost disjoint with that of N. L. Biggs [Algebraic graph theory (1974; Zbl 0284.05101)]. In particular, a lot of important recent research on locally 2-transitive graphs (among others by Cameron, Gardiner, Goldschmidt, Weiss) does not fit into the authors’ view of algebraic combinatorics. However, in the topics treated, the book is very detailed.

The book starts in Chapter I (Representations of finite groups) with an elementary introduction to ordinary group representation theory; as the authors write, the treatment is almost a translation of Chapter 6 of the Japanese book by K. Asano and H. Nagao [Group Theory (1965)]. The intention of the chapter is to provide a group theoretic background which gives some intuition for concepts introduced later for association schemes; e.g., the character table of a finite group appears later as the eigenmatrix of a corresponding association scheme.

The main topic is introduced in Chapter II (Association schemes). The basic theory of association schemes is established in Sections 2.1-2.6 (covering centralizer rings, adjacency algebras, nonexistence conditions, duality, and Schur rings) and 2.9 (imprimitivity); the remaining sections treat more peripheral topics (McKay’s observation, Norton algebras, noncommutative duality, Hecke algebras and spherical functions).

Chapter III (Distance regular graphs and (P and Q)-polynomial association schemes) is much more specialized. It contains a number of successful steps in the direction of the authors’ aim to classify the most structured class of association schemes, those with the P-polynomial and Q-polynomial property. These properties, dual to each other, were introduced by Delsarte; they are shared by the Hamming schemes, the Johnson schemes, and a number of other highly geometric schemes related to classical groups and certain simple groups of Lie type. It is very likely that most or even all (P and Q)-polynomial schemes of diameter \(d>6\) are known, and the problem of characterizing them is perhaps the most challenging problem in the theory of association schemes. P- polynomial association schemes are equivalent with distance regular graphs, i.e. graphs where the number of vertices at distance i from a vertex x and at distance j from a vertex y depends only in i, j and the distance of x and y.

(However, this book says very little about distance regular graphs of small diameter. Also, as the authors mention in the introduction, they leave the geometry of distance regular graphs to a book which is being prepared by A. Brouwer, A. Cohen and the reviewer.) Specifically, the third chapter gives in Section 3.1-3.7 basic properties of distance regular graphs, nonexistence theorems for Moore graphs and generalized polygons, the case of two P-polynomial structures, explicit parameters for (P and Q)-polynomial schemes, a (for \(d>6\) probably complete) list of families of (P and Q)-polynomial schemes, and a proof that (P and Q)- polynomial schemes of diameter \(d\geq 34\) and valency \(k\geq 2\) have integral eigenvalues. (Note: in Theorem 6.4, \(\chi\) must be assumed imprimitive).

The final Section 3.8 outlines the work remaining to be done in order to complete the classification and surveys the partial results available. Several of the problems mentioned in Section 3.8 have been solved in the meantime; this shows the timeliness of the book. The speed of development forced the authors into a hurry to publish the book. Unfortunately it often resulted in a rather preliminary style; e.g. the statement of the main theorem III.5.1 takes 12 pages (!), and many formulae are rather messy. In the authors’ words: ”We decided to hurry the publication in the hope that we could help those who are trying to start their own research in this area, as there seems no comprehensive treatment available on this topic at the present time other than original papers scattered in various journals and publications. We admit a lot of material is left in these lecture notes to be polished and improved both mathematically and in exposition. To help and to stimulate further research in this area are the only possible raison d’être of these lecture notes... We plan to update and improve these lecture notes to make their final version a more solid book form in some near future.”

In spite of these drawbacks this is an interesting and nourishing book for anyone interested in association schemes. There are a lot of formulated research problems, and the more than 400 references also make it a useful guide to the literature on the subject.

Reviewer: A.Neumaier

##### MSC:

05B30 | Other designs, configurations |

05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |

20B25 | Finite automorphism groups of algebraic, geometric, or combinatorial structures |

33C55 | Spherical harmonics |

51E99 | Finite geometry and special incidence structures |

05B25 | Combinatorial aspects of finite geometries |

20C15 | Ordinary representations and characters |

33C45 | Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) |