British Mathematical Colloquium, days 3 and 4

The day began with the plenary talk by Paul Seymour, whom I’ve known for longer than almost anyone else at the meeting.

He explained that there are many different “ordering” relations on graphs; the two he considers most important are the minor and induced subgraph orders. Roughly speaking, he worked on the minor ordering in the second millennium and the induced subgraph ordering in the third.

An induced subgraph of a graph is obtained by throwing away some vertices and the edges incident with them; you are not allowed to throw away an edge within the set of vertices you are keeping. Paul began with the general problem: given a graph H, can you determine the structure of graphs G containing no induced copy of H?

The first issue is what you mean by “structure” here. Paul thinks of it as a construction for such graphs. But even this needs explaining. You can construct all triangle-free graphs by taking a set of vertices and adding edges, taking care never to create a triangle. But clearly this is a hopeless construction and tells you nothing about triangle-free graphs!

The answer is known in embarrassingly few cases:

• A graph with no induced path of length 1 is a null graph.
• A graph with no induced path of length 2 is a disjoint union of complete graphs.
• Graphs with no induced path of length 3 form a well-understood class – for such a graph G, either G or its complement is disconnected, so it is clear how they can be built inductively from smaller graphs by taking disjoint unions with all or no edges between. (These graphs have many names, including cographs or N-free graphs.)
• A sequence of seven papers of Paul, with Maria Chudnowsky, determines the structure of claw-free graphs, those containing no K_1,3; there are many interesting examples.

And that’s it! Not even for a 4-cycle is the answer known. There is a structure theory for bull-free graphs modulo the structure of triangle-free graphs and their complements, which again is not easy. (The bull has a triangular face, with horns or pendant edges at two of its three vertices.)

If we are content with less than a complete description, there are various conjectures you can try: does a forbidden subgraph force the existence of a “large” complete or null subgraph? For arbitrary graphs on n vertices we can’t do better than log n (Ramsey’s theorem together with the probabilistic method); can we achieve n^c (“polynomial”), or even cn (linear): Can we find two large sets with all or no possible edges between them?

Another question asks for χ-boundedness, the property that the chromatic number χ(G) is bounded by a function of the clique number ω(G). The perfect graph theorem, proved by Paul and collaborators, proves the conjecture of Berge by showing that if G contains no odd hole (induced odd cycle) or odd antihole (induced complement of an odd cycle) then G has equal clique and chromatic numbers. He went on to discuss some new and powerful results he and others have proved, where we forbid just some holes.

There was a lot more but that will do for now.

David Conlon’s advertised title was “How to build a hypergraph expander”, and he did indeed show us this in the second part of his talk. But his real subject was “The unreasonable effectiveness of mixing algebra and probability”. The first half of his talk mainly concerned the function ex(n,H), the maximum number of edges in a graph G on n vertices not containing H as a (not necessarily induced) subgraph. The Erdős–Stone theorem gives as an upper bound a fraction (1−1/(χ(H))+\epsilon) of all edges of K_n, and Turán graphs show this is tight. The problem occurs when χ(H) = 2, that is, H is bipartite, when the theorem only gives a fraction o(1), that is, o(n² edges. There is some evidence that the correct asymptotics should be around cn^2−1/s, where s is the smaller bipartite block of H. This is known to hold in a few cases, including K_2,2 and K_3,3, where algebraic constructions over finite fields realise the lower bound. The probabilistic method straightforwardly gives about n^{1−1/s−1/t}. David and coauthors have improved this by a method involving choosing “random algebraic varieties”.

For hypergraph expanders, even the best definition is not known: spectral, combinatorial, rapid mixing of some random walk, topological (Gromov), coboundary, …? David has constructions involving rapid mixing of a random walk on pairs on the neighbourhoods of vertices in a Cayley graph in an elementary abelian 2-group. As he remarked, received wisdom is that abelian groups are bad for rapid mixing, but the commutative property was essential in his argument.

Last before lunch was a beautiful talk by Simon Smith on infinite permutation groups. He assumed some topological knowledge (he liked his groups to be totally disconnected and locally compact (tdlc): the study of locally compact groups reduces to two cases, Lie groups and tdlc groups). His permutation groups were transitive and subdegree-finite (this means that a point stabiliser has all its orbits finite – automorphism groups of locally finite connected graphs are examples). There is a close connection: a closed subdegree-finite group is tdlc, and a tdlc group has a nantural action as a subdegree-finite permutation group.

An important construction for finite permutation groups is the wreath product in its product action. Simon has another construction which he calls the box product. If X and Y are the domains of G and H, take a collection of copies of X, with complete graphs on each; and glue them together, any two meeting in one point and the copies through any point indexed by Y. Then there is a way to make a group act on this graph, so that the stabiliser of a lobe (copy of X) has G acting, while the stabiliser of a point has H acting on the lobes through that point. This is the box product. He has a theorem for when the box product is primitive, mirroring what happens for wreath product, and an O’Nan–Scott type theorem for primitive subdegree-finite groups.

After lunch and the (brief) business meeting of the Colloquium, I returned to the algebra workshop to hear Brent Everitt talking about three different ways to attach (co)homology to a hyperplane arrangement (a finite set of hyperplanes in a vector space). Note that the hyperplanes and their intersections have the structure of a lattice. The first method is simply to remove the hyperplanes and consider what’s left. Over the real numbers, this falls into many pieces, but over the complex numbers it is connected, and the Orlik–Solomon theorem gives its cohomology over the integers: there is no torsion, and the Betti numbers are expressible in terms of the Möbius function of the lattice.

The second method is to form the chain complex of the lattice (with top and bottom elements removed), the simplicial complex whose simplices are the chains. This is homotopy-equivalent to a bunch of spheres; the Goresky–MacPherson th eorem connects its reduced homology to the previous case.

The third solution puts a sheaf of R-modules on the lattice, and take its simplicial cohomology with local coefficients. There is a canonical sheaf: each element of the lattice is a subspace; just use that subspace.

I ducked out and went to the history stream to hear Rosemary Bailey talk about Latin squares. Much of it was familiar to me, but there were some eye-openers, including the use in an experiment on diets and slaughtering times for sheep, reported in France in 1770, a possible proof (now lost) of the non-existence of orthogonal Latin squares of order 6 by Clausen in 1842, and a row between Fisher and Neyman about whether using a Latin square in an experiment gives biased results (with a shocking recent tailpiece).

I missed the London Mathematical Society meeting because I had a visitor; then there was a wine reception followed by a very nice dinner. I wish I had felt well enough to enjoy it more; but at least I could eat it, which is a sign of progress!

The last morning had just two morning talks and one plenary.

The first morning talk I went to was by Vicky Gould, who gave us a crash course in semigroup theory followed by the biorder on the idempotents of a semigroup and the “free idempotent-generated semigroup” generated by a biordered set. This is a fairly recent topic where the arguments are not straightforward. It is a free object whose generators correspond to the idempotents, and relations ef = g if the product of e and f is g in the original semigroup (or, abstractly, if e and f are comparable in one of the orders). Nice results but I won’t attempt to confuse you with a proper account.

Second, Daniel Král’ talked about graphons and their analogues for permutations, permutons. A sequence (G_n) of, say, graphs is said to converge if the probability that a random set of size |H| in G_n induces a copy of H converges for all graphs H. So what does the sequence converge to? This is more difficult, and was the problem solved by Borgs, Chayes, and Lovász by inventing graphons. It appeared that graphons often correspond to solutions to extremal graph problems which are either unique, or can be made so by adding extra relations. But Dan and his coauthors have shown that this is very far from being the case; he showed us pictures of some enormously complicated graphons refuting the obvious conjectures.

After coffee we had the final talk of the conference, a plenary on “Products of random matrices” by Marcelo Viana. Furstenberg and Kesten showed that certain limits always exist; these turned out to be the extremal Lyapunov exponents. Marcelo and collaborators showed that these numbers depend continuously on the input. This can be widely generalised, to distributions on the group GL(d), and to things called linear cocycles. In the first case it is not enough that the distribuions are close in the weak* topology, but also that their (compact) supports are close in the Hausdorff topology; he showed us examples to demonstrate this. Most of the results have generalisations in some form. It was very clear, but again my brain was full.