Chris Godsil

Affiliation: University of Waterloo, Ontario, Canada

Title: Laplacian States

Abstract: It is customary to assume that the initial state of a continuous quantum walk on a graph $X$ is a vertex. However the Laplacian matrix of a graph with vertex set $V(X)$ is positive semidefinite, and can be scaled to produce a density matrix, and so provides an initial state for a walk on $X$. Qiuting Chen and I have studied thisset up, and this talk will present some of what we have learned, and some of the lot that we don’t know.

You can watch the talk here, and you can access the slides here1, here2 and here3.

This talk was given on January17th, 2021




Title: Tails and Chains

Abstract: Physicists are interested in “graphs with tails”; these are constructed by choosing a graph $X$ and a subset $C$ of its vertices, then attaching a path of length $n$ to each vertex in $C$. We ask what is the spectrum of such graph? What happen if $n$ increases? We will see that the answer reduces to questions about the matrix

$$M(\zeta) := (\zeta_\zeta^{-1})I – A -\zeta D$$
where $D$ is the diagonal $01$-matrix with $D_{i,i}=1$ if $i\in C$. (For physicists, the block of $M(\zeta)^{-1}$ indexed by the entries of $C$ determines the so-called scattering matrix of a quantum system, but we won’t go there.)
A path is built by chaining copies of $K_2$ together. We consider what happen if we use some other graph in place of $K_2$.

You can watch the talk here.

This talk was given on September 13th, 2021




Title: The Matching Polynomial

Abstract: A $k$-matching in a graph is a matching of size $k$, and $p(X,k)$ denotes the number of $k$-matchings in $X$. The matching polynomial of a graph is a form of generating function for the sequence $(p(X,k))_{k\ge0}$.

It is closely related to the characteristic polynomial of a graph. I will discuss some of the many interesting properties of this polynomial and some of the related open problems.

You can watch the talk here and the slides can be viewed here: slides1, slides2, slides3, slides4

This talk was given on January 25th, 2021




Title: Continuous Quantum Walks on Graphs

Abstract: A quantum walk is a (rather imperfect analog) of a random walk on a graph. They can be viewed as gadgets that might play a role in quantum computers, and have been used to produce algorithms that outperform corresponding classical procedures. Physical questions about these walks lead to problems in spectral graph theory, and they also provide interesting new graph invariants. In my talk I will present some of the background, and some of the open problems of interest.

You can watch the talk here and the slides are available here.

This talk was given on July 27th, 2020