Algebraic Graph Theory

8th Slovenian Conference on Graph Theory

Last week I was at the 8th Slovenian Conference on Graph Theory. This was the latest in what is commonly known as the ‘Bled conference’ but this year was in Kranjska Gora. This meant that the conference excursion was to Lake Bled. It was a very enjoyable conference with lots of interesting talks and it was good to catch up with lots of people. I was one of the plenary speakers and my talk was entitled ‘Bounding the number of automorphisms of a graph’. This surveyed the recent work on the Weiss conjecture and its generalisation the PSV conjecture. It also discussed my recent work with Luke Morgan on the PSV conjecture for semiprimitive groups with a nilpotent regular normal subgroup. More details can be found on my slides.

Symmetries of Graphs and Networks IV

Last week I was at the Symmetries of Graphs and Networks IV conference at Rogla in Slovenia. The conference webpage is here. At the same time was the annual PhD summer school in discrete maths. As usual it was a very enjoyable and well organised conference. It was good to catch up with some of the regulars and meet a few new people as well

I was one of the invited speakers and spoke about some of the work that I have been doing recently with Luke Morgan on graph-restrictive permutation groups. The slides are available here. The two relevant preprints are on the arxiv here and here.

A Las Vergnas Conjecture

I’m in France at the moment, having spent the last week at a workshop on matroid computation at Henry Crapo’s house in the tiny village of La Vacquerie et Saint Martin de Castries, but now I’ve moved on to Paris for a week.

I had been intending to drop in to see Michel Las Vergnas, but it seems that I somehow missed the sad news that he died in January. Although I only met him once, a few years go in Barcelona, we had frequently communicated about an exasperating conjecture of his.

A quick bit of background: start with the vertex-edge incidence matrix of the graph, such that the column corresponding to the edge ${e=vw}$ has exactly two non-zero entries, both equal to one, in rows ${v}$ and ${w}$ . Viewed as a matrix over ${GF(2)}$ , the row space and null space of this matrix are called the cocycle space ${C}$ and the cycle space ${C^\perp}$ of the graph. The non-zero vectors in ${C}$ , called the cocycles, are the (characteristic vectors of the) cut-sets of the graph, while the non-zero vectors in ${C^\perp}$ , called the cycles, are the subgraphs in which every vertex has even degree. (Notice that this notion of cycle is considerably broader than the usual graph-theoretic notion.) A set of edges that is simultaneously a cycle and a cocycle is called a bicycle, and the bicycle space is the vector space ${C \cap C^\perp}$ . (A coding theorist would call this the hull of the linear code ${C}$ .)

If ${T(x,y)}$ is the Tutte polynomial of the graph, then it is well known that

$\displaystyle T(-1,-1) = \pm \ 2^{d(C\cap C^\perp)}$

where ${d(C\cap C^\perp)}$ is the dimension of the bicycle space.

Among many other things, Las Vergnas was interested in a variety of evaluations of the Tutte polynomial along the diagonal where ${y=x}$ , and so he considered the polynomial ${D(x) = T(x,x)}$ and (for reasons unknown to me) its derivates ${D'}$ , ${D''}$ , ${D'''}$ , etc. all evaluated at the point ${x=-1}$ . While he could not find an interpretation for ${D'(-1)}$ , ${D''(-1)}$ , ${\ldots}$ he noticed that the sequence of values generated appeared to be divisible by unexpectedly high powers of ${2}$ , with each differentiation reducing the exponent of ${2}$ by at most one. So he made the following conjecture:

If ${G}$ is a graph with bicycle dimension ${d}$ , and ${D(x) = T(x,x)}$ is its diagonal Tutte polynomial, then ${2^{d-k} \mid D^{(k)}(-1)}$ for all ${k < d}$ .

For example, for the graph ${K_6}$ , we have

$\displaystyle D(x) = x^{10}+5 x^9+15 x^8+41 x^7+88 x^6+172 x^5+300 x^4+390 x^3+236 x^2+48 x$

and so ${D(-1) = -16}$ , ${D'(-1) = 80}$ , ${D''(-1) = -220}$ , ${D'''(-1) = 270}$ , which are indeed divisible by ${16}$ , ${8}$ , ${4}$ and ${2}$ respectively.

However a quick computer search revealed that as it stands, the conjecture is false — the graph ${K_8}$ is a counterexample. But I was slightly intrigued by now, so I searched a bit harder and noticed that no matter how hard I tried, I could not find any planar graphs that did not have the property of the conjecture. So I emailed Michel and we revised the conjecture to

If ${G}$ is a planar graph with bicycle dimension ${d}$ , and ${D(x) = T(x,x)}$ is its diagonal Tutte polynomial, then ${2^{d-k} \mid D^{(k)}(-1)}$ for all ${k < d}$ .

And that’s basically where it stands. Although it is not a particularly important statement in itself, if it is true, then surely there must be some more combinatorial information to be wrung from the Tutte polynomial if only we knew how to look at it in the right way!

In fact, I think that planar graphs is not the precisely correct class to be working with, but rather some class that includes planar graphs; something perhaps like $\Delta Y$ graphs.

Vacation research scholarship II

Over the summer break, John and I each supervised a 2nd year undergraduate student in a research project, and the previous post summarised Michael Martis’ project. I supervised Melissa Lee, who learned about the energy of graphs and this is what she did

Hello everyone! My name is Melissa Lee and I’m about to start my third year of Chemical Engineering and Pure Mathematics at UWA. Over these summer holidays, I’ve been given the opportunity to take on a six week research project with Professor Gordon Royle. The area that I have researched is the energy of graphs, with a particular focus on extremal cases. It’s been a new and exciting time for me, being my first experience of research and also my first taste of graph theory.

The idea of the energy of a graph was first introduced by Serbian mathematician Ivan Gutman at a conference in Austria in 1978. Its origins lie in chemistry, where it is defined as “the total $\pi$ electron energy of a conjugated hydrocarbon as calculated with the Hückel Molecular Orbital method”. The concept didn’t receive much attention from mathematicians for many years. However, sometime around the turn of the century, mathematicians realised its value and since then, increasing numbers of papers have been published each year about the energy of graphs.

Continue reading “Vacation research scholarship II”

3rd SYGN Workshop

Last week I was at the 3rd Symmetries of Graphs and Networks Worskhop and PhD Summer School in Discrete Mathematics at Rogla, Slovenia. The SYGN meeting has been held every two years with the first being at Banff in 2008 and this was the second one held at Rogla. The summer school part continues on the tradition started last year.

Once again the Slovenians did a great job at organising it and it was a very enjoyable conference. I was invited to give a minicourse as part of the summer school on The Polycirculant Conjecture. I have touched on this previously. Boštjan Kuzman kindly took latex notes of my lectures and these are available at the conference webpage together with the slides from the other courses and talks from the workshop. The other courses were on Graph enumeration by Stephan Wagner and Finite geometries by György Kiss.

Four talks that I found particularly interesting were:

Roman Nedela’s survey on regular maps. This gave a great overview of the area and I learned a lot about what the main problems in the area are.
Jozef Siran’s survey on the degree-diameter problem.
Joy Morris’s talk on the structure of circulant graphs.
Steve Wilson’s talk on Tales from the census. This is his census with Primož Potočnik on 4-valent edge-transitive graphs.

When does Delsarte’s bound hold?

Philippe Delsarte (An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., 10:vi+97, 1973) generalised the “MacWilliams transform” of coding theory to the theory of association schemes, and there have been numerous powerful applications of this object, particulary in finding the maximum size of a clique in some particular kinds of graphs. These graphs are regular and they are in fact a union of graphs from some association scheme. Let $\omega(\Gamma)$ be the maximum size of a clique of a graph $\Gamma$ .

Theorem (Delsarte): If $\Gamma$ is the graph of an association scheme with valency $k$ , and if $\lambda$ is a negative eigenvalue of $\Gamma$ , then

$\omega(\Gamma)\le 1-k/\lambda$ .

I will give a proof I’ve seen in one of Chris Godsil’s notes as it bypasses the usual theory on inner distribution vectors and the MacWilliams transform. Continue reading “When does Delsarte’s bound hold?”

The Merino-Welsh Conjecture

The Merino-Welsh conjecture is an intriguing conjecture relating three graphical parameters, namely the numbers of spanning trees, acyclic orientations and totally cyclic orientations of a graph.

First recall the definitions of these terms: an orientation of a graph is an assignment of directions to the edges of the graph (thus there are $2^m$ orientations for an $m$ -edge graph), and an orientation is called acyclic if the resulting directed graph contains no directed cycle and, at the opposite extreme, totally cyclic if every directed edge is contained in a directed cycle. A spanning tree is a connected subgraph containing every vertex of the graph, but containing no cycles; it is easy to see that a spanning tree of an $n$ -vertex graph has $(n-1)$ edges. We denote these three quantities $\tau(G)$ for trees, $\alpha(G)$ for acyclic orientations and $\alpha^*(G)$ for totally cyclic orientations. Then we have the conjecture, due to serial conjecturer Dominic Welsh, and his former student Criel Merino.

Conjecture (Merino, Welsh) If $G$ is a multigraph with no bridges or loops, then $\tau(G) \le \max(\alpha(G),\alpha^*(G))$ .

There are various stronger versions of this conjecture, such as having $\tau(G)$ less than the arithmetic or geometric mean of the other two parameters, but all seem equally difficult and equally unsolved.

Speaking very loosely, if the graph is somewhat sparse, with relatively few edges given the number of vertices, then acyclic orientations are favoured and so $\alpha(G)$ tends to dominate the number of spanning trees, while if the graph is dense, then the number of totally cyclic orientations tends to dominate. The best partial results on the conjecture are essentially about graphs at one end of the spectrum or the other, where one or other of the parameters dominates so much that relatively coarse, though ingenious, approximations are sufficient to demonstrate this fact. So, the following results are known, due to Carsten Thomassen:

If the bridgeless multigraph $G$ has at least $4n-4$ edges, then $\tau(G) < \alpha^*(G)$ .
If $G$ is a graph (not multigraph) with at most $16n/15$ edges, then $\tau(G) < \alpha(G)$ .

Obviously there is a huge gap between these bounds. It is conceivable however that there is a range of low densities where $\alpha(G)$ dominates $\tau$ (i.e. regardless of the structure of $G$ ) and a range of higher densities where $\alpha^*(G)$ dominates $\tau$ , and that these two ranges overlap. In fact, Thomassen asked whether $m = 2n-2$ edges could possibly be the dividing point, so that any multigraph with at most $2n-2$ edges has $\alpha(G) < \tau(G)$ and any multigraph with at least $2n-2$ edges has $\tau(G) < \alpha^*(G)$ . Unfortunately this is not true, as there are graphs with exactly $2n-2$ edges that have more spanning trees than acyclic orientations.

In some sense, although it may work, this approach seems rather unsatisfactory — the conjecture concerns the interplay of two dual parameters whereas the known results essentially focus on just one of the two. This follows because all three parameters are actually evaluations of the Tutte polynomial of the graph at various points. In fact, if $T$ is the Tutte polynomial of $G$ , then:

$\tau(G) = T(1,1)$
$\alpha(G) = T(2,0)$
$\alpha^*(G) = T(0,2)$

So if $G$ is planar, then it has the same number of spanning trees as its planar dual, but the numbers of acyclic and totally cyclic orientations swap round. Of course, we don’t need to restrict ourselves to planar graphs – the Tutte polynomial is defined for any matroid, graphic or otherwise, and so the conjecture can be made just as $T(1,1) \le \max(T(2,0),T(0,2))$ without any reference to the interpretations of these evaluations. So really, rather than crude approximations based on edge or element densities, it would be much more satisfying if there were some structural reason for the truth of the conjecture that exploited this duality – perhaps some way of defining a map from spanning trees to orientations that could be massaged into a suitable injective map.

As well as evaluating the Tutte polynomial at specific points to get numbers, we can get a variety of 1-variable polynomials from it by partially specifying the values, and lots of common graph and matroid polynomials (chromatic, flow, reliability etc) arise in this way. So we could define $f(z) = T(1+z,1-z)$ and consider the behaviour of this single-variable polynomial for $z \in [-1,1]$ . In particular, it is quite possible that $f(z)$ is convex throughout its domain, except for the case where $G$ is a tree with every edge doubled, in which case $f(z)$ is actually constant. Conde and Merino said that this would make a “rather more daring strengthening of the conjecture” which I have paraphrased to incorporate matroids:

Conjecture (Conde-Merino, but for graphs only) If $M$ is a matroid with no loops or co-loops with Tutte polynomial $T$ , then $T(1-z,1+z)$ is convex on the range $z \in [-1,1]$ unless $M$ is a direct sum of pairs of parallel elements.

Cubic vertex-transitive graphs

A graph is called vertex-transitive if for every pair of vertices there is an automorphism of the graph that maps the first to the second. I discussed such graphs and other symmetry classes of graphs in two earlier posts. (I see that I had promised a third in that series but that has yet to eventuate.)

A cubic graph is a graph for which every vertex has valency three, that is, every vertex has exactly three neighbours. Cubic graphs have been extensively investigated with many graph properties first investigated in the cubic case. For example, s-arc-transitive graphs were first investigated in the cubic case in the seminal work of William Tutte in two papers in 1947 and 1959.

An arc of a graph is an ordered pair of adjacent vertices and we say that a graph is called arc-transitive if the automorphism group of the graph acts transitively on the set of arcs. The most famous example is the Petersen graph. Arc-transitive graphs are also called symmetric graphs. Ronald Foster began compiling a list of symmetric cubic graphs in 1932 and this is now known as the Foster census. Marston Conder and Peter Dobcsanyi extended the census so that it was complete for graphs with at most 768 vertices and Marston has extended it further to include all graphs with at most 2048 vertices. The graphs are available on Marston’s website.

For vertex-transitive cubic graphs there is data collated by Gordon and Brendan McKay that is complete for all graphs with up to 94 vertices as well as all graphs with n vertices for many values of n at most 258. Recently, Primoz Potocnik, Pablo Spiga and Gabriel Verret have comprehensively smashed this upper bound by compiling a list of all vertex-transitive cubic graphs with at most 1280 vertices. This continues the excellent work in graph symmetry that they have been doing in recent years. They have set up a webpage containing the data and a preprint is on the arxiv explaining their methods. I am sure it will be a valuable resource for investigating graphs and testing conjectures. They have already checked that apart from the four known exceptions they each have a Hamiltonian cycle.

As part of their work they have also compiled a list of all arc-transitive graphs of valency 4 on at most 640 vertices. That is also available on their webpage. Primoz is also undertaking a project with Steve Wilson aiming to list all edge-transitive valency 4 graphs on up to 512 vertices. The data so far is available here.

A mysterious generalised odd graph

In connection with some work I’m currently doing with Alice Devillers and Simeon Ball, we have come across an interesting subproblem: is there a distance regular graph with intersection array $\{7, 6, 6;1, 1, 2\}$ ? It seems that no such graph is known nor proved to not exist. So some background first …

Continue reading “A mysterious generalised odd graph”

Chromatic Roots I

On Friday, I gave a talk (chromaticpolynomials) to the “Junior Mathematics Seminar” in our department; this is a seminar attended and organized by the students, with staff only allowed as speakers.

I chose to speak about one of my favourite topics, namely the chromatic roots of graphs, for three reasons: firstly, it is a very accessible topic for undergraduates, secondly, I have spoken about it frequently and so have many diagrams and plots already prepared, and thirdly, because Alan Sokal and I (along with other collaborators) are having another push at trying to make some progress with some of the outstanding conjectures.

One of the questions is how to tighten the bounds on chromatic roots as a function of the maximum degree $\Delta(G)$ of a graph $G$ . It had long been conjectured, by Norman Biggs and his collaborators, that chromatic roots of graphs should be bounded by some function $f(\Delta(G))$ of the maximum degree. This was eventually proved by Alan (http://arxiv.org/abs/cond-mat/9904146) but the bound he proved — that chromatic roots have modulus no more than about $8\Delta(G)$ — is almost certainly nowhere near tight.

I have a very strong conjecture on which I have made no progress in 20 years — my early computations on chromatic roots made me believe the following.

Conjecture: The chromatic root of largest modulus among all $r$ -regular graphs is a chromatic root of the complete bipartite graph $K_{r,r}$ (with the sole exception of the complete graph $K_4$ for $r=3$ .

(Unpublished work by Sokal and Jesus Salas show that this would give a bound of approximately $1.6\Delta(G)$ .)

In other words, I believe that the largest chromatic root belongs to one of the smallest possible graphs! Despite many years of attempting to disprove this, and millions of chromatic polynomials computed and their roots extracted, I’ve never managed to find a single counterexample.

There are many other attractive conjectures regarding the bounds on chromatic roots, but I’ll leave them for future posts.