BCC at Birmingham, days 4 and 5

Thursday saw my favourite of the plenary talks. Iain Moffatt told us about ribbon graphs and delta-matroids. Ribbon graphs are essentially the same as graphs drawn on surfaces (we just fatten up each vertex to a disc and each edge to a ribbon), while delta-matroids stand in the same relation to them as matroids do to ordinary graphs. But there was a lot more to the story. You can form the dual of a planar graph, by putting a vertex in each face and an edge crossing each edge of the original graph. Iain invited us to consider dualising with respect to just some of the edges. In the ribbon graph world this is possible, and the name given to the operation (a twist) gives away the idea: ribbons can be given a twist, as in the construction of a Möbius band. There was much more, for example a connection with linear algebra: delta-matroids are represented by symmetric or skew-symmetric matrices, where we look at all the principal submatrices and ask whether they are non-singular. Everything fits together nicely: the operations of twist on ribbon graphs, symmetric exchange (the relevant version of the exchange axiom) for delta-matroids, and pivot for matrices all correspond exactly.

We had the last two talks in the Designs and Latin Squares mini-symposium, with Sergey Goryainov talking about constructions of Neumaier graphs, and Michael Kinyon talking about some latin-square-like objects related to set-theoretical Yang–Baxter such as racks, quandles, and the newly-named rumples.

On Thursday night we had the conference dinner. Our mini-symposium participants and like-minded people had been put together on a table, and we had a very congenial meal. Indeed, participants remarked on the generally high standard of the food at the conference; I found that usually we were so well fed at breakfast, coffee break, lunch and tea break that no dinner was necessary.

The publishers who had had book tables at the meeting (Cambridge University Press and Springer) had donated some of their unsold books to the British Combinatorial Committee (a gesture for which we are very grateful!). On Thursday we sold them off to participants at reduced prices. On Friday in the coffee break, Andrew Treglown and I did a double act as auctioneers and got rid of the remaining unsold books at even further reduced prices. Some people walked away with great bargains.

The last talk was by Gabor Tardos, on ordered versions of Turán theory: our graphs have total orders on the vertex set, and we ask about the maximum number of edges of a vertex-ordered graph G on n vertices which does not contain a given vertex-ordered graph H as a subgraph. As in classical Turán theory, the answer is asymptotically a fraction (1−1/m) of the number of edges in the complete graph, for some parameter m. Classically, m is one less than the chromatic number of H; in the vertex-ordered case, it is one less than the minimum number of parts in a partition of the vertex set of H into edge-free intervals, so a sort of ordered version of chromatic number. Although many puzzles remain, at least this type of chromatic number is easier in some ways than the usual; for example, it is linear-time computable.

My take on this, for what it is worth, is that we are looking at structures with two relations, a graph and a total order; as a graph we take subgraphs (we are allowed to throw away edges), but as an order we must take the induced substructure. This could be generalised to structures with two sets of relations, where substructures may throw away instances of relations in the first set but must be induced substructures of the second set. This includes, for example, permutation patterns, where there are two total orders and we take induced substructures of both.

In the edge-ordered case, again m+1 is a sort of “chromatic number” but there is an element of Ramsey theory in this case; it may be larger than the number of vertices of H, and may even be infinite (this happens if arbitrarily large complete graphs can be ordered so as to contain no copy of H, so that the maximum number of edges is the number in the complete graph on n vertices.

In summary, a great conference, very well organised; I look forward to seeing many of the participants at the next BCC, in Durham on 5–9 July 2021.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events 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.