Scottish Combinatorics Meeting 2018

Last week saw the fourth annual Scottish Combinatorial Meeting in Edinburgh, in the Informatics Forum at the University of Edinburgh. The building was new to me, but easy enough to find, and having a terrace with a fine view of Arthur’s Seat.

There was a rich mix of interesting talks; as usual I can’t discuss everything, so apologies to those I have left out.

There were a pair of talks on graphs on surfaces, delta-matroids, and their Tutte polynomials, by Iain Moffatt and Steve Noble; not exactly a double act, but there was a lot of synergy between the two (including Steve using some of Iain’s pictures in his slides). The first time I heard Iain talk about this, it was all done via Hopf algebras; this time, he was kinder to his audience and explained everything in elementary terms. He began with a gentle introduction to the Tutte polynomial of a graph, discussing the deletion-contraction algorithm, why the polynomial is well-defined (not obvious if you do it this way), and even making it clear why the number of nowhere-zero A flows on a directed graph is independent both of the directions but also on the structure of the abelian group A (the dependence is only via its order). He then explained that this works in much more general situations as long as you can say what deletion and contraction are and what loops and bridges are (recent work of Dupont, Fink and Moci – but knowing one of these authors I suspect that Hopf algebras are lurking below the surface). Then he got on to the example of graphs on surfaces, explaining why there are four different Tutte polynomials of these (when you delete a bridge you may create a non-simply-connected face, and when you contract a loop you may create a pinch point; each of these can be dealt with in two ways). Three of these (covering essentially all cases) are in the literature, but Iain showed clearly where these come from.

Then Steve told us a little about matroids, defined in terms of their bases (these are spanning trees if the matroid comes from a connected graph). This led him fairly painlessly to delta-matroids, which are associated with ribbon graphs (these are graphs whose vertices are discs and whose edges are ribbons which may be twisted), where the bases are quasi-trees (connected ribbon subgraphs whose boundary has just one component). He described a “local duality” (dualise one edge at a time), which connects with the Penrose polynomial. Rich fare, but too rich to explain in detail here.

The Tutte polynomial, in the guise of the partition function of a statistical physics model, appeared also in Will Perkins’ talk. He and his co-authors have been studying the kissing number of spheres, in particular its asymptotic behaviour in high dimensions. It grows exponentially, but the lower and upper bounds differ by an exponential factor, and progress has been very slow. What they had achieved, by techniques from statistical physics, was an improvement by a factor of d (the dimension) in the lower bound. The topic is closely related to coding theory, with sphere packing and Gilbert–Varshamov; since I had given an impromptu revision lecture on coding theory the day before, the two students who were there were hopefully able to make some connections.

Radu Curticapean talked about complexity issues related to counting small subgraphs of a given graph. If the subgraphs have k vertices, then brute force search takes time c(k)n^k. Assuming a now-popular hypothesis in computer science (the Exponential Time Hypothesis, which is considerably stronger than P ≠ NP) they are able to give lower bounds. To explain these, he described graph motifs, functions which are linear combinations of the subgraph numbers for various small graphs. Indeed, he explained that numbers of subgraphs, numbers of induced subgraphs, and numbers of homomorphisms form three different bases for the space of graph motifs, and the last of these is the best, since the exponent of n in the complexity of finding a motif is the size of the largest small graph occurring in the expression for the motif in the homomorphism basis.

Colva Roney-Dougal, just back from the antipodes, talked about the generating graph of a group (whose vertices are group elements, two vertices joined if they generate the group). Of course this is trivial if the group cannot be generated by two elements; but fortunately, we know that all the finite simple groups can be generated by two elements, so they give us a good supply of interesting graphs. One interesting conjecture concerns the spread of a group, the largest k such that, given any k non-identity elements y₁, …, y_k, there exists x such that x and y_i generate the group for i = 1,…,k. Thus, spread 1 means that the identity is the only isolated vertex, and spread 2 means that the graph (restricted to the non-identity elements) has diameter 2. Well, it is conjectured that spread 1 and spread 2 are equivalent!

Of the contributed talks, I will mention just two: St Andrews MSc student Carl-Fredrik Nyberg Brodda gave a nice survey of graph pebbling; and I was able to report that the paper containing the theorem I talked about (equitable partitions of Latin square graphs) was accepted for publication (the email with the news arrived on the morning of my talk; I read it on the train, courtesy of ScotRail wi-fi).

So thanks to Mary Cryan and her team for an excellent meeting.