Peter Cameron is an Emeritus Professor of Mathematics in the School of Mathematical Sciences at Queen Mary, University of London. He is also a half-time Professor of Mathematics and Statistics at the University of St Andrews. Peter writes a popular blog about things he “feel(s) strongly enough about” and he recently posted an entry about his observations at the 2016 London Combinatorics Colloquia, hosted by the Departments of Mathematics at Queen Mary, University of London and the London School of Economics and Political Science. This blog post is reproduced below, with his kind permission.

The tenth London Combinatorics Colloquia took place over the last two days. (As was pointed out, this is not the same as the tenth anniversary!) A dozen really excellent talks, and I cannot do justice to them all, so I will describe a few in detail and the rest more briefly.

The Queen Mary day was opened by Béla Bollobás. His topic was random geometric graphs, but he started off with a nice summary of the facts about percolation on the square lattice in the plane. It turns out that the critical probability for bond percolation on the square lattice with 1-independent probabilities (that is, the value of edge-probability at which the probability of an infinite component switches from 0 to 1, if sets of edges which are vertex-disjoint are independent) is not greater than 0.8639. This played a role in what came later.

The main result consisted in the “k nearest” model: the vertices are chosen from a Poisson process with intensity 1 on the unit square (or the plane), and each vertex is joined to its k nearest neighbours. Various thresholds for interesting properties appeared. One of the main results asserted that the threshold for percolation in the plane is k ≤ 11. The novelty is that this is a mathematical theorem, not a physicist’s “theorem”; but it is only established with “near-certainty” (at least 1−10⁻¹⁵⁰).

The reason is that the proof involves evaluating a high-dimensional integral to see whether the value is greater than 0.8639. Of course the integral cannot be evaluated exactly, so Monte Carlo methods are used. They indicate that the required inequality holds, but of course there is some wiggle room for scepticism.

Naturally, this provoked a lot of discussion!

Two things delighted me. One was that four of the six talks were board talks. The other was that three of them involved symmetry, and used at least something about groups. One of these was by Yifei Zhao, who considered Cayley graphs, and showed that two conditions for quasirandomness (the discrepancy condition and the eigenvalue condition) are equivalent for Cayley graphs for any finite group. This had previously been established for abelian groups by Kohayakawa, Rödl and Schacht in 2003 using harmonic analysis, so the new proof uses “non-abelian harmonic analysis”. The complete independence of the group was striking. Another talk using symmetry was by David Conlon, who defined two operations on functions on a graph; roughly speaking, if either of these turns out to be a norm, then the graph satisfies Sidorenko’s conjecture. David (with Joonkyung Lee) has added greatly to the very small stock of known examples. He showed us why the bipartite graph derived from two parabolic subgroups of a finite reflection group always satisfies the conditions.

The third talk invoking symmetry, one which interested me most closely, was by Imre Leader, on combinatorial games. [There are some things wrong with this write-up, which I have tried to correct in the comments below.] Such a game is defined by a set (usually finite) called the “board”, wich a collection of subsets called “lines”; players alternate in choosing an element of the board, and in normal play the player who first gets a line is the winner. Imre showed us the classical “strategy-stealing” argument showing that the game cannot be a second-player win. (If the second player had a winning strategy, the first player can make a first move anywhere and then follow the winning strategy: the extra element doesn’t hurt, and if the strategy says to choose it, then the player chooses another element arbitrarily.)

Imre was concerned with the misère version, where the first player to complete a line loses. You might expect that the first player cannot win this game, but this is not so. Take any board on which the second player wins, and add an extra cell on no lines. The first player takes this first and then steals the second player’s strategy.

To avoid the obvious asymmetry, follow Isbell (whose work I have described here in the past) and assume that the game has a group of automorphisms acting transitively on the positions of the board. Even with this condition, it is still possible for the first player to win; but if the automorphism group contains a fixed-point-free involution, there is a second player win (the second player uses the involution to “mirror” the first player’s moves). This brings us to Isbell’s territory, as I explain in a minute.

First, there is a game on a board of odd composite size: divide the board into a bins of size b, and let the lines be the sets containing a majority of cells in a majority of bins. For example, if n = 9, there are 3 bins of size 3, and the lines are all 4-sets containing two cells from each of two bins. Finding a winning strategy for the first player is an interesting exercise.

Odd primes are harder, and it is not known whether there are such games with first-player win on boards of prime size greater than 13.

The situation is very different for boards of even size 2m. An Isbell family is a family of sets of size m, invariant under a transitive group, and containing one of each complementary pair of sets. An Isbell family exists if and only if there is a transitive group containing a fixed-point-free involution. Isbell investigated these in a game-theoretic context in the 1950s and 1960s, and conjectured that, if the 2-part of n is large enough relative to the odd part, then any transitive group of degree n contains a fixed-point-free involution; so no Isbell family can exist. Fifty years on, the conjecture is still open. Nevertheless, Imre and his team (Robert Johnson and Mark Walters) have been able to prove that a first-player-win game exists for all even numbers except powers of 2.

The other two talks were just as remarkable. Karim Adiprasito talked about the proof of Rota’s conjecture for arbitrary matroids (the coefficients of the characteristic polynomial are log-concave). The proof is phrased in the language of algebraic geometry , but Karim assured us that it is really just combinatorics dressed up. One feature was a technique for deforming one matroid into another (but the objects through which we pass on the way are not themselves matroids). Andrew Granville told us about the sieve method in analytic number theory, and about analogies between the decompositions of natural numbers into primes, polynomials over finite fields into irreducible factors, and permutations into cycles.

The day had been wet, and my lunchtime taken up with a committee meeting, so that I was a bit late for Imre Leader’s talk. But the next day at LSE I was off duty.

Two talks stood out for me. The first was by Benny Sudakov, on equiangular lines (a topic which probably got me my postdoc at Merton College – the committee were suitably amazed that someone could talk familiarly about 23 dimensions), and in which the driving force was my good friend Jaap Seidel. How many lines can there be through the origin ind-dimensional Euclidean space, any two making the same angle? There is an upper bound d(d+1)/2, which is attained for d = 2, 3, 7, and 23, and as far as we know for no other values (though there is a quadratic lower bound in general). Benny had no more to add to this. But Seidel and others also looked at the case where the angle between the lines is fixed in advance. Here they have improved the old results considerably: they showed an upper bound of 2d−2 if the angle is the arc cosine of 1/3, and 1.93d in any other case. They suspect that much more is true, and the bound is (1+o(1))d unless the angle is the arc cosine of the reciprocal of an odd number.

There was much more too, involving sets of lines with more than a single allowed angle, or sets of unit vectors with all inner products either equal to a positive number α or at most a negative value β. Strangely, allowing all these negative values doesn’t change things very much.

The proof was a lovely blend of linear algebra, geometry, and graph theory.

The other talk I really liked was by Nati Linial on “higher-dimensional permutations”. His notion was different from the one I discussed at last year’s Permutation Patterns conference, but it is one I have given some thought to. A d-dimensional permutation is a (d+1)-dimensional array of 0s and 1s, n along each side, such that each 1-dimensional “line” (in any coordinate direction) contains a single 1. For d = 1, this is just a permutation matrix; for d = 2, it is equivalent to a Latin square. In these two cases, estimates for the number are known, asymptotic in the logarithm; Nati and his team have given upper bounds of the right form in general, but the lower bounds are unknown: for Latin squares these depend on the van der Waerden permanent conjecture, which doesn’t work in higher dimensions.

Nati is interested in many aspects of the theory of these things, but there was no time to tell us everything, so he concentrated on enumeration and on discrepancy and expander properties. These involve looking at the size of “empty boxes”, in the zero-one formulation above. Cayley tables of groups are not good for this purpose, but (as with many other problems) it is conjectured that almost all Latin squares are good.

Other talks were by Daniela Kühn, packing low-degree graphs; Monique Laurent, a very nice talk on connections between semidefinite programming and topological graph invariants such as those of Colin de Verdière; James Maynard, who told us about his proof that infinitely many primes omit the digit 7 (or any other digit you like); and Alan Frieze, on on-line versions of purchasing edges of the complete graph (with random prices) so as to build some type of structure (a tree, a triangle, a Hamiltonian cycle, etc.)

At lunchtime, the weather was beautiful, and I sat in Lincoln’s Inn Fields eating my lunch and looking at (and smelling) a lilac tree in full blossom. After the last talk, we went up to the top of the New Academic Building at LSE, with a fine view of the City, with the ugly clutter of tall buildings which is the legacy of the last two Mayors, Ken and Boris.

• This post was originally published on Peter Cameron’s Blog