Introduction
I am a retired 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.
Algebraic Graph Theory. Our group's webpage. We run a weekly seminar in algebraic graph theory, more about this here.
Other talks
- Notes and slides for a talk "Quantum Colouring and Derangements".
- slides for talk "Problems on Continuous Quantum Walks".
My Research
Quantum Walks
[to be updated]
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 distance-regular antipodal covers of complete graphs and complete bipartite graphs.
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.
And now there are quantum analogs of colouring, automorphims, homomorphisms, cocliques,...
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 four books. For more about these, see the links on this page.