Speaker: Krystal Guo, Thursdays 11:00am EST; starting May 13.
News
Lectures are over, working group(s) organize July 8.
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 working groups on these topics.
Resources: pdfs
- Resources for working groups.
- Open Problems.
- Homework.
- 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
Contact
For further information, contact Chris Godsil.