Speaker: Krystal Guo, Thursdays 11:00am EST; starting May 13.
Content and Outline
It is conjectured that the proportion of graphs on n vertices which are determined by their spectrum goes to 1, as n goes to infinity. To complement these conjectures, mathematicians have proposed many matrices associated with graphs whose spectra are conjectured to be complete graph invariants. More recently, physicists have at times proposed algorithms for graph isomorphism, with the hope that these could be implemented on a quantum computer, and run faster than current algorithms on classical computers. The challenge, in all these cases, for graph theorists is to produce graphs on which these algorithms fail.
The proposed algorithms associate a matrix with each graph, and the idea is that the spectrum of this matrix will determine the graph. In practice it doesn't, but identifying the counterexamples and proving that they defeat the proposed algorithm is not easy.
The goal of these lectures is to introduce some of graphs we use (triply regular graphs, Hadamard graphs, point graphs of generalized quadrangles) and to study the relevant algebraic machinery (coherent algebras, Terwilliger algebras, the Weisfeiler-Leman algebras).
Our intention is that the latter part of the course will turn into a working group on these topics.
Tentative Lecture Plan
- Lecture 2:
- Very special graphs; strongly regular graphs, generalized quadrangles, Hadamard graph, distance regular graphs.
- Lecture 3:
- Matrix algebras continued; Weisfeiler-Leman algorithm, extension of matrix algebras, weak and strong isomorphism.
- Lecture 4:
- Triply regular graphs I ; automorphism groups of graphs, distance transitive graphs, triply transitive graphs.
- Lecture 5:
- Triply regular graphs II: strongly regular triply regular graphs. Spherical t-designs, vanishing Krein, etc.
- Lecture 6:
- Triply regular graphs III: Terwilliger algebras.
- arxiv.org/abs/1511.01962 Godsil, Guo, Myklebust. "Quantum Walks on Generalized Quadrangles."
- Algebraic Aspects of Multi-Particle Quantum Walks. (Jamie Smith's Ph. D. thesis.)
- Triply-regular graphs. Old notes of Krystal's.
Recordings and slides of Lectures
For further information, contact Chris Godsil.