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.
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.
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.
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.
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.
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.