Old Codgers 2016

Yesterday, a beautiful sunny autumn day, I spent at the Old Codger’s Combinatorics Colloquium in Reading, where the campus with its lake and its many mature trees were looking glorious.

Tree at University of Reading

There is some controversy about the position of the apostrophe in the title. Before the s, it suggests that there is only one old codger involved, presumably the organiser Anthony Hilton, even though several regular attendees (myself included) could be so described; after the s, it suggests that everyone involved is an old codger, which was not the case, as several young people attended. In my slides, I fudged the issue by leaving the apostrophe out.

The talks were full of interest. First Terry Griggs told us about pentagonal geometries, joint work with Klara Stokes. He reminded us that a generalized n-gon is an incidence structure of points and lines whose bipartite incidence graph (or Levi graph) has diameter n and girth 2n, according to the definition of Jacques Tits; the Feit–Higman theorem tells us that no finite generalized pentagon exists (apart from the ordinary pentagon). So how should we define a pentagonal geometry? The idea of Ball, Bamberg, Devillers and Stokes was to observe that, in a pentagon, the points not collinear with a given point p comprise a line, the “opposite” of p; they take this (and the condition that two points lie on at most one line) to define a pentagonal geometry. The added regularity condition that any line has k points and any point lies on r lines is assumed. Terry took us through a number of properties and constructions of these objects, with links to Moore graphs, projective planes, and orthogonal Latin squares, among other things.

Then Steve Noble gave us a clear introduction to delta-matroids, the gadgets which fill the blank in his title “Graphs are to matroids as embedded graphs are to ???”. They are motivated by an abstraction of embedded graphs called ribbon graphs, where the vertices are discs and the edges are ribbons. Delta-matroids admit a richer collection of operations than do ordinary matroids (which occur as a special case). The last part of the talk was devoted to the enumeration of delta-matroids. It is not hard to see that the number dn of delta-matroids on n points is bigger than the square root of the number 22n of families of subsets, so that log log dn is at least n−1; the difference is a decreasing function of n which might tend to zero.

After lunch, two Johnsons (Matthew and Robert) spoke. Matthew considered the notions of Kempe chain in a properly vertex-coloured graph (a connected component of a 2-coloured subgraph) and a Kempe change (interchanging the colours in a Kempe chain). These notions were invented by Kempe in his failed proof of the four-colour theorem, and made precise by Heawood who salvaged the proof of the five-colour theorem from Kempe’s work. Bojan Mohar conjectured that, for k ≥ 3, if G is a k-regular graph which is not complete, then any proper k-colouring of G can be transformed into any other by a sequence of Kempe changes. This was refuted by Jan van den Heuvel, who pointed out that it is false for the triangular prism. Matthew and his collaborators have shown that the triangular prism is the only exception. He gave us an outline of the proof, and left us with two problems, one of which seems extremely natural: what is the best upper bound for the number of Kempe changes required?

Robert told us about a nice result he and his student Nick Day have proved. There is an easy argument that shows that a complete graph on 2k vertices cannot be covered by k bipartite graphs; so any edge-colouring of this graph with k colours contains a monochromatic odd cycle. Erdős and Graham asked about the smallest such cycle that could be guaranteed; they forgot to ask, and left to Chung, the question of whether the length of such a cycle is bounded. They have shown that it is not. Robert gave us the elegant proof. As a by-product of the argument, they have found new lower bounds for the Ramsey number for odd cycles, refuting a conjecture of Bondy and Erdős.

Then, after the tea break, David Conlon gave a beautiful board talk about quasirandomness in graphs. It has been known for a while that, for dense graphs, several “quasirandomness” conditions are equivalent: the three he talked about were the condition that the number of edges between two disjoint subsets is close to the expected number, that the non-principal eigenvalues of the adjacency matrix are bounded, and (surprisingly) that the number of 4-cycles is close to the expected number. He discussed two themes. First, what happens for sparse graphs? The equivalence of the first two conditions fails, but David and his student Zhao have succeeded in giving substitute results in some cases, including Cayley graphs. Then he talked about his work with Jacob Fox and Benny Sudakov on replacing the 4-cycle in the third condition by other graphs. This is closely related to the famous Sidorenko conjecture. If we replace a 4-cycle by a 3-cycle, the result is false, but can be restored by assuming the triangles are nicely distributed (any large induced subgraph has about the right number). This result of Simonovits and Sós used the Regularity Lemma, and so gave tower bounds for the inequalities involved; these have been reduced to polynomial, and the right answer could be linear.

I concluded the meeting by talking about three problems that I would like to see solved: cliques in graphs in the Johnson scheme, derangements and Latin squares, and sum-free sets. The slides are in the usual place.

After an enjoyable dinner at the Forbury restaurant, we headed home.

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.