Symmetries of combinatorial structures.

Question

Studying the automorphism groups of graphs/finite geometries/designs has been quite useful and important for both group theory and combinatorics. I know of the following books which cover the ideas involved in the role of group theory in combinatorics and vice-versa:

1. Algebraic Graph Theory by Godsil and Royle.
2. Permutation Groups and Combinatorial Structures by Normal L. Biggs, A.T. White.
3. Topics in Algebraic Graph Theory by Wilson, Cameron and Beineke.

Are there any other such books or survey articles which you would recommend? Especially for structures other than graphs like point-line geometries and combinatorial-designs.

Answer 1

Which combinatorial structures different from graphs are interesting for symmetry investigations? Probably all of them. The next ones that come to my mind are:

• Association schemes
• Combinatorial designs
• Block codes
• Finite geometries
• Lattices
• Matroids
• etc.

There are many connections between the different areas. For example, linear codes are the same as multisets in finite Desarguesian projective geometries, so many coding-results have a straightforward translation to geometry and vice versa.

It is worth mentioning that truly exceptional objects typically have incarnations in more than one area. For example, the Golay Code, the Witt design and the Leech lattice are in some sense the same object, all having the Mathieu group $M_{24}$ as group of symmetries.

I will give a few references which have not been mentioned before (i.e. in the question or in the answer of Boris Novikov).

Symmetries of combinatorial structures are naturally described as group actions. This aspect is discussed in the following book without overly emphasizing any particular combinatorial structure:

A. Kerber: Applied Finite Group Actions. 2nd. ed. Springer, 1999. ISBN: 3-540-65941-2.

In some sense, group actions are the same as permutation groups. A great reference on permutation groups is

J. D. Dixon; B. Mortimer: Permutation Groups. Graduate Texts in Mathematics 163. Springer, 1996. ISBN 0-387-94599-7.

The theory of association schemes can be seen as a generalization of group theory. Thus, it is a meta-theory to many aspects of symmetries on combinatorial structures. The classical source on association schemes is the thesis of Philip Delsarte:

P. Delsarte: An algebraic approach to the association schemes of coding theory. Philips Research Reports 10, 1973. Scan.

For its historic roots, the most prominent application of association schemes is to coding theory. This aspect is discussed in the survey article

P. Delsarte; V. I. Levenshtein: Association schemes and coding theory, IEEE Transactions on Information Theory 44[6] (1998), 2477-2504. Link.

and in Chapter 21 in the classic book on coding theory

F. J. MacWilliams; N. J. A. Sloane: The Theory of Error-Correcting Codes. North-Holland, 1977. ISBN 0-444-85009-0.

Another good source, not only on association schemes (Chapter 12), is the book

C. Godsil: Algebraic Combinatorics. Chapman & Hall, 1993. ISBN 0-412-04131-6.

For state-of-the-art computational classification methods in coding and design theory, see

P. Kaski; P. Östergård: Classification Algorithms for Codes and Designs. Springer, 2006. ISBN 3-540-28990-9.

Answer 2

E.Bannai, T.Ito, Algebraic combinatorics I: Association schemes. Benjamin/Cummings Publishing Co., 1984.

R.L.Graham, M.Grötschel, L.Lovász, Handbook of combinatorics (vol. 1). Elsevier, 1995 .

H.Lüneburg, Tools and fundamental constructions of combinatorial mathematics. BI-Wiss.-Verl., 1989.

Answer 3

"The bible" of algebraic graph theory is essential: Distance-Regular Graphs by Brouwer, Cohen and Neumaier.

Another favorite of mine is Permutation Groups by Peter Cameron.