Yesterday, Peter Sarnak gave the London Mathematical Society’s 2020 Hardy Lecture (remotely). He talked about gaps in the spectra of connected cubic graphs. It was a talk properly described as a tour de force, applying to the problem ideas from algebraic geometry (Weil’s proof of the Riemann conjecture for curves over finite fields), probability (Benjamini–Schramm measure), and fractal geometry (the Julia set of a real quadratic), among many other things.
I won’t attempt to describe more than the first few ideas in the talk. I think it was filmed, and a video will no doubt appear at some point; I do urge you to watch it.
Let X be the set of all finite connected cubic graphs (graphs of valency 3). We are interested in spectral questions; the spectrum of a member of X is the set (or multiset) of eigenvalues of its adjacency matrix. Since the graphs are regular, the adjacency spectrum is a simple transform of the Laplacian spectrum. It is well known that the eigenvalues of such a graph are all real, and lie in the interval [−3,3]; the value 3 is always a simple eigenvalue, and −3 is an eigenvalue if and only if the graph is bipartite.
A subinterval I of [−3,3] is a gap if there exist arbitrarily large graphs in X with no eigenvalues in this interval; it is maximal if there is no strictly larger interval which is a gap.
The first gap is (2√2,3), due to Alon and Boppana; the maximality of this gap depends on the existence of Ramanujan graphs, shown in the 1980s by Margulis and by Lubotzky, Phillips and Sarnak. As the name suggests, the construction of such graphs uses a substantial amount of number theory related to work of Ramanujan. The speaker told us that he had been rash enough to state that the construction would not be possible without number theory; but he was proved wrong (and taught to be more cautious) when a group of physicists found a construction using Lee–Yang theory in statistical mechanics.
I was so impressed with the Lubotzky–Phillips–Sarnak paper when it came out that I gave a seminar talk to the pure mathematicians at Queen Mary expounding it.
Then Peter Sarnak mentioned two other potential gaps, interest in which had come from real applications: gaps at −3, important in the theory of waveguides; and gaps at 0, important in the Hückel theory of fullerenes (molecules made of carbon atoms forming polyhedra with only pentagonal and hexagonal faces, like the football (which chemists call the buckyball). I will just repeat some of what he said about the first of these two.
He and Alicia Kollár (and others) have shown the remarkable result that [−3,−2) is a maximal gap. He associates the name of Alan Hoffman with this gap. The name is entirely appropriate. Hoffman did a lot of work on graphs with least eigenvalue −2, but in the end it was Jean-Marie Goethals, Jaap Seidel, Ernie Shult and I who proved the theorem he had been trying to prove, giving a virtually complete description of such graphs. I have described our result here; Peter Sarnak was kind enough to describe the paper as “beautiful”, and I don’t mind shining in reflected glory for a moment.
So here is the path from our theorem to the gap described above; the details were not given in the lecture.
We showed that, with finitely many exceptions (all realised in the exceptional root system E8), all connected graphs with smallest eigenvalue −2 (or greater) are what Hoffman called generalised line graphs. Fortunately I don’t have to tell you what these are, since it is an easy exercise to show that if a generalised line graph is regular, then it is either a line graph or a cocktail party (n couples attend a cocktail party, and each person talks to everyone except his/her partner). Moreover, if a line graph is regular, then it is the line graph of either a regular graph or a semiregular bipartite graph.
The cocktail party graph has valency 2n−2, which is even; so is not possible in our situation. The line graph of a regular graph of valency k has valency 2k−2, which is also even. The line graph of a semiregular bipartite graph with valencies k and l has valency k+l−2. So in our situation we only have to consider line graphs of semiregular bipartite graphs where the valencies in the two bipartite blocks are 2 and 3.
Now such a graph is obtained from a smaller graph Y in X (namely, the induced subgraph of the distance-2 graph on the set of vertices of valency 3) by inserting a vertex in each edge. So its line graph is built from Y by replacing each vertex of Y by a triangle, or sewing in triangles.
We conclude that, with finitely many exceptions, any graph in X with no eigenvalues in [−3,−2) is obtained from a graph in X by sewing in triangles. Moreover, such graphs are line graphs of graphs with more edges than vertices, and so really do have −2 as an eigenvalue; so the gap is maximal.
from Peter Cameron's Blog https://ift.tt/38b7jNZ
Peter Cameron
Post a Comment