G2D2, 4: the second week

Kingfisher at CTGU

The lecturers of the first two minicourses now gave way for the second team.

Mike Boyle and Scott Schmieding told us about symbolic dynamics, in particular, subshifts and their automorphism groups. This was particularly valuable to me: I had dove into this subject without really knowing any of the background, so this was ideal for getting me up to speed. Collin Bleak, Jim Belk, Shayo Olukoya and I are developing an approach based on strongly synchronizing automata, so it was good to get a panoramic view of this particular landscape. Mike gave us an introduction, and Scott told us how algebraic K-theory (stable linear algebra over a ring) is relevant to the topic.

The other course was by Nobuaki Obata, on spectra of graphs, where the graphs are either infinite or large finite. He took a quantum probability approach to this topic. I gained quite a lot of insights from this. In particular, I learned that three things I knew about were essentially different views of the same thing. As a student, I had learned about creation, annihilation and conservation operators, and never really understood them. In applied analysis I learned about the three-term recurrence relations used for calculating orthogonal polynomials. And in the theory of distance-regular graphs, there is the tridiagonal array of intersection numbers pioneered by Norman Biggs.

Another insight came from a very nice talk by Alexander Mednykh, who is able to do impressive computations of the number of spanning trees in various graphs. This number is the order of a group, the Jacobian group of the graph, a kind of homology group. His methods worked particularly well in the case of circulant graphs or cyclic coverings of graphs. The Chebychev polynomials play an important role here, and I now better understand why.

These polynomials are usually defined by the rule that Tn(cos x) = cos nx. Well, of course, trigonometric functions have to do with circles, and so might appear in studying circulant graphs … But there is a much stronger connection. An alternative specification of the polynomials is Tn(½(x+x−1)) = ½(xn+x−n). Now if x represents the adjacency matrix of a directed cycle, then x+x−1 represents an undirected cycle or Cay(Cm,{1,−1}), and then xn+x−n represents Cay(Cm,{n,−n}). The proof of the identity is straightforward; the usual definition shows that it is valid for all points on the unit circle, and hence since both sides are polynomials it is true in general.

The name of Jaap Seidel was mentioned a few more times; Jack Koolen dedicated his talk to Jaap. But another pioneer of spectral graph theory, Alan Hoffman, also featured several times, in particular in a beautiful talk by Akihiro Munemasa on Hoffman’s limit theorem. He extended it to Hermitian adjacency matrices of digraphs, and was able to take advantage of subsequent developments, in particular the root system interpretation of graphs with least eigenvalue −2, to give the proof.

As anticipated, Mike Kagan talked about resistance distance and the resistance distance transform as a tool for graph isomorphism, and its relationship to association schemes and Jordan schemes. Mike’s approach, coming from physics, is a bit different from mine, so there was plenty for me to learn, and the talk sparked several interesting unsolved problems in my mind. I might talk about some of these, if we make any progress on them.

Shiping Liu gave a talk that sparked my interest. There is a definition of “spherical graphs”, which captures and generalises the hypercube graphs. He was interested in discrete analogues of Ricci curvature and Cheng’s maximal diameter theorem. But I was reminded of dual polar spaces, which are a different generalisation of hypercubes. Is there a notion of “q-spherical graphs” which would capture these beautiful objects?

After the conference was over, several participants went to Shanghai for the minisymposium on dynamical systems; Rosemary and I went back to Hangzhou, where it was her turn to give a short course, on relations among partitions, posing a number of open questions about beautiful designs and arrays of various kinds such as triple arrays and multistage Youden rectangles.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.