## Introduction

I am a professor in Combinatorics and Optimization in the Math Faculty at the University of Waterloo. The main purpose of these pages is to provide information about research in which I am involved, with my students and postdocs.

## CO 471/671: Semidefinite Optimization

## Algebraic Graph Theory Seminar

This semester it is being held Tuesdays at 3:30 pm in MC 6484.

## My Research

### Covers

Roughly speaking, we construct a *cover* of a graph with index r by replacing
each vertex by a coclique of size r and each edge by a matching with r edges.
I am interested in covers of complete graphs and complete bipartite graphs
that are distance regular and antipodal.

### Homomorphisms and Colorings

A *graph homomorphism* is a map from the vertices of one graph
to another, such that adjacent vertices map to adjacent vertices.
Any graph isomorphism is a graph homomorphism. A proper coloring with
m colors is the same thing as a homomorphism to the complete graph on
n vertices. A graph is a *core* if it does not admit a homomorphism
to a proper subgraph.

### EKR Theorems

The simplest version of the Erdos-Ko-Rado theorem asserts that we have a family F of subsets of size k from a set of size v such that any two k-subsets have at least one point in common, and F is as large as possible, then it consists of all k-subsets that contain a given point from the underlying set. A surprising number of analogs of this theorem are known now - to give just one example, it still holds if we replace the underlying set by a vector space of dimension d over a finite field, and use subspaces of dimension k in place of subsets of size k.

Mike Newman and I developed a new approach to this theorem, using eigenvalues and eigenvectors. We obtained new proofs of known results and new results. Karen Meagher and I continued with this program, in part motivated by the desire to to obtain an analog of the EKR theorem for certain graphs based on set partitions. One outcome was our book - see the links.

### Complex Lines

The *angle* between two lines in d-dimensional complex space is
determined by the absolute value of the inner product of unit vectors that span
the lines. Work in quantum physics has lead to two questions related to
the geometry of sets of complex lines.

It can be shown that if the angle between any two lines is the same, then we can have at most d^2 lines. The problem is to decide if this number can always be attained. No example where equality holds is known if d>19??. The corresponding problem in real space has been studied more, and is related to the theory of strongly regular graphs.

### Graph Spectra

What useful relations are there between the properties of a graph and algebraic properties of the various adjacency matrices? I have been interested in this question for all of my professional life. My view of this is presented in my book "Algebraic Combinatorics", published in 1993. More recently I have found that some interesting problems in quantum computing translate into questions about graph spectra, and useful information can be obtained as a result. (For more, see my papers on arXiv/quant-ph.)

There are also interesting open problems with no connection to physics. For example, we would like to know if almost all graphs are characterized by the spectrum and the spectrum of the complement.

## Brief CV

I graduated from the University of Melbourne in 1969 with a degree in Biochemistry. After working for four years as a biochemist, I returned to the University of Melbourne and completed my Ph. D ("Graphs with Regular Groups") in 1979, under the supervision of Derek Holton. I spent nine months of my study towards my Ph.D. in the Mathematics Department at Syracuse University. (My time in Melbourne was spent in a large office shared with Brendan McKay. We had this office largely to ourselves, because our interminable conversations about graph theory drove all other legal tenants away. Brendan has taken revenge.)

From 1980 to 1981 I was employed as Vertragsassistent in the Institut fuer Angewandte Mathematik at the Montanunversitaet Leoben (in Austria). From there I moved to the Mathematics Department at Simon Fraser University. In 1987 I came to the Department of Combinatorics and Optimization, at the University of Waterloo, where I am still lodged.

In 1992, Ian Goulden, David Jackson and I started the Journal of Algebraic Combinatorics. I am on the editorial board of a number of other journals, including Australasian J. Combinatorics and Electronic J. Combinatorics.

I have written two books and have almost finished a third. For more about these, see the links on this page.