Graph Theory and Interactions

Durham

In the second half of July, a LMS/EPSRC Durham Symposium was held on Graph Theory and Interactions.

This was the 99th in the series, which began with a symposium on Global Riemanniam Geometry, organised by Michael Atiyah, in 1974. In fact, Jozef Dodziuk from CUNY, who was at the recent meeting, had also been at this first meeting, and proved it by showing a page from the schedule of talks. The first one I attended was number 10, Homological and Combinatorial Methods in Group Theory, organised by Terry Wall, at which I learned a lot about Bass–Serre theory.

Interactions predominated at the meeting, but there were speakers who told us relatively “pure” graph theory, such as Allan Lo who was part of the team who have proved impressive results on 1-factorisation and Hamiltonian decomposition of regular graphs of large degree (including a proof of the Chetwynd–Hilton conjecture for “large” n) and Kristina Vuskovic (who gave us a bundle of results on structural graph theory related to the Truemper configurations), more attention was paid to how graph theory and other areas relate.

(Incidentally, Anthony Hilton started a new hare by asking whether, when 3 divides n, the complete 3-uniform hypergraphs with two parallel classes removed has a 1-factorisation. A nice question: the answer is almost certainly yes, but finding techniques to tackle it may not be easy.)

Chief among these areas was the geometry of manifolds. Daniel Lenz told us about “Dirichlet pairs”, which unify the construction of Laplacians (and their consequences such as random walks) on manifolds and graphs. Manifolds are well-behaved, but graphs are not (his graphs have finite but unbounded vertex degrees), and so it is necessary to “tame” them by replacing the graph metric with an “intrinsic” metric. Several other talks were related to this theme.

Laplacian eigenvalues occurred in other talks, appearing in connection with optimal design theory among other things, but Willem Haemers stuck resolutely to “ordinary” adjacency matrix eigenvalues most of the time. He gave us new evidence that have persuaded him that, despite earlier results pointing the other way, it is actually the case that almost all graphs are characterised by their spectrum. His second talk was about “energy” of a graph, the sum of the absolute values of the eigenvalues (and he briefly mentioned a problem here for the Seidel eigenvalues). Bojan Mohar also used ordinary eigenvalues in his talk about the median eigenvalue, motivated by Hückel theory in chemistry.

Other interactions were with rigidity of frameworks, network coding, spreading of rumours, and property testing.

Rolf Niedermeyer managed to break down my prejudice against parametrized complexity to some extent. He took three graph problems: vertex cover, clique size, and chromatic number. All are NP-hard, but anyone who has had to solve them in practice (as I have, in connection with synchronization) knows that there is more to it than that, In Rolf’s view, parametrized complexity gives a finer scale for judging such problems. “Vertex cover at most k” has complexity a function of k times a polynomial of fixed degree (actually linear) in n (the number of vertices); “clique number at most k” has complexity a polynomial in n whose degree is a function of k; while “chromatic number at most k” does not even fall into this class, since it is NP-hard even for k = 3.

The liveliness of the conference was evident in the problem sessions. One session was scheduled, and ran for more than an hour with plenty of problems still not presented, so we agreed to put on another. The only time we could find was after dinner one night; a good crowd turned up and we went on for a further three quarters of an hour. At least one problem was solved in the second session: one participant asked about the order of the kernel of a graph Laplacian modulo a prime; another participant was able to explain to him about the chip-firing game, which answers his question negatively.

I already found a couple of things at the conference to write about here, see the last couple of posts.

We had a good social programme as well: a visit to the Lindisfarne Gospels exhibition; a trip to Alnwick Castle (where I met the chap below); and lots of wine and cheese.

Alnwick Castle

Advertisements

About Peter Cameron

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

One Response to Graph Theory and Interactions

  1. Gordon Royle says:

    I was thinking how nice it would be to have seen some of these talks (particularly Willem H on energy) and hoping to find some slides online, but discovered that – even better – there are videos of almost all of the talks!

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s