Algebraic Combinatorics PDF

Preface

There axe people who feel that a combinatorial result should be given a “purely combinatorial” proof, but I am not one of them. For me the most interesting parts of combinatorics have always been those overlapping other areas of mathematics. This book is an introduction to some of the interactions between algebra and combinatorics. The first half is devoted to the characteristic and matchings polynomials of a graph, and the second to polynomial spaces. However anyone who looks at the table of contents will realise that many other topics have found their way in, and so I expand on this summary.

The characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. The matchings polynomial of a graph G with n vertices is

∑^[n/2] ( - 1 )^k p(G,k)x n-2k, k=0

where p(G, k) is the number of fc-matchings in G, i.e., the number of subgraphs of G formed from k vertex-disjoint edges. These definitions suggest that the characteristic polynomial is an algebraic object and the matchings polynomial a combinatorial one. Despite this, these two polynomials are closely related and therefore they have been treated together. In developing their theory we obtain as a by-product a number of results about orthogonal polynomials. The number of perfect matchings in the complement of a graph can be expressed as an integral involving the matchings polynomial. This motivates the study of moment sequences, by which we mean sequences of combinatorial interest which can be represented as the sequence of moments of some measure.

To be brief, if not cryptic, a polynomial space is obtained by associating an inner product space of “polynomials” to a combinatorial structure. The combinatorial structure might be the set of all fc-subsets of a set of t; elements, the symmetric group on n letters or, if the reader will be generous, the unit sphere in R ". Given this set-up it is possible to derive bounds on the sizes of “codes” and “designs” in the structure. The derivations are very simple and apply to a wide range of structures. The resulting bounds are often classical—the simplest and best known is Fisher’s inequality from design theory.

Polynomial spaces are perhaps impossibly general. We distinguish one important family which corresponds, when the underlying set is finite, to Qpolynomial association schemes. The latter have a well-developed theory, thanks chiefly to work of Delsarte. Our approach enables us to rederive and extend much of this work. In summary, the theory of polynomial spaces provides an axiomatisation of many of the applications of linear algebra to combinatorics, along with a natural way of extending the theory of Qpolynomial association schemes to the case where the underlying set is infinite.

From this discussion it is clear that to make sense of polynomial spaces, some feeling for association schemes is required. Hence I have included a reasonably thorough introduction to this topic. To motivate this in turn, I have also included chapters on strongly regular and distance-regular graphs. Orthogonal polynomials arise naturally in connection with polynomial spaces and distance-regular graphs, and thus form a connecting link between the two parts of this book.

My aim has been to write a book which would be accessible to beginning graduate students. I believe it could serve as a text for a number of different courses in combinatorics at this level, and I also hope that it will prove interesting to browse in. The prerequisites for successful digestion of the material offered are:

Linear algebra: Familiarity with the basics is taken for granted. The spectral decomposition of a Hermitian matrix is used more than once. The theory is presented in Chapter 2. Positive semi-definite matrices appear. A brief summary of the relevant material is included in the appendix.

Combinatorics: The basic language of graph theory is used without preamble, e.g., spanning trees, bipartite graphs and chromatic number. Once again some of this is included in the appendix. Generating functions and formal power series are used extensively in the first half of the book, and so there is a chapter devoted to them.

Group theory: The symmetric group creeps in occasionally, along with automorphism groups of graphs. The orthogonal group is mentioned by name at least once. Ignorance: By which I mean the ability to ignore the odd paragraph devoted to unfamiliar material, in the trust that it will all be fine at the end.

I have not been able to draw up a dependence diagram for the chapters which would not be misleading. This is because there are few chains of argument extending across chapter boundaries, but many cases where the material in one chapter motivates another. (For example it should be possible to get through the chapter on association schemes without reading the preceding chapter on distance-regular graphs. However these graphs provide one of the most important classes of association schemes.)

By way of compensation for the lack of this traditional diagram, I include some suggestions for possible courses.

(1) The matchings polynomial and moment sequences:

1-3, 4.1-2, 4.4, 5.1-2, 5.6, 6, 7, 8.1-3, 9.

(2) The characteristic polynomial:

1.1, 2, 3, 4.1-4, 5.1-4, 5.6, 6, 8.

(3) Strongly regular graphs, distance-regular graphs and association schemes:

2, 5.1-2, 8, 10-13.

(4) Equitable partitions and codes in distance-regular graphs:

2, 5.1-2, 5.6, 8.1-2, 11, 12.

(5) Polynomial spaces:

2, 8.1-2, 10, 12.1-4, 13.1, 13.6, 14-16.

In making these suggestions I have made no serious attempt to consider the time it would take to cover the material indicated. On the basis of my own experience, I think it would be possible to cover at most three pages per hour of lectures. On the other hand, it would be easy enough to pare down the suggestions just made. For example, Chapter 3 covers formal power series and generating functions and depending on the backgrounds of one’s victims, this might, not be essential in (1) and (2).

I have been helped by advice and comments from Ed Bender, Andries Brouwer, Dom de Caen, Michael Doob, Mark Ellingham, Tony Gardiner, Bill Martin, Brendan McKay, Gillian Nonay, Jack Koolen, Gordon Royle, J. J. Seidel and Akos Seress. Dom in particular has made heroic efforts to protect me from my own stupidity. I am very grateful for all this assistance. I would also like to thank John Kimmel and Jim Geronimo of Chapman and Hall for their part in the production of this book.

Author: Chris Godsil