From permutation groups to model theory

I cannot resist a conference with a title like this! But in this case, there is another very important reason to attend.

In the mid-1970s, when I began being interested in infinite permutation groups (I had been a strictly finite person before that point), I soon came to realise that I would need to know some model theory. As I have told elsewhere on this blog (for example, here, here and here), I learned it by volunteering to give the second-year lectures on logic in Oxford. I was also helped by Graham Higman’s advanced class on the Ryll-Nardzewski theorem (also proved at the same time by Engeler and by Svenonius), which says (in one formulation) that a countable first-order structure is determined up to uniqueness by the first-order sentences it satisfies together with the condition of countability if and only if its automorphism group is what is now called oligomorphic. In other words, in this situation at least, (first-order) axiomatisability is equivalent to a very high degree of symmetry. This is one of my very favourite theorems in mathematics.

Soon afterwards, Dugald Macpherson (whose undergraduate degree in Oxford was in Mathematics and Philosophy – he had been my student at Merton College) began his DPhil under my supervision. As with many of my students, he taught me much more than he learned from me; he contributed more than anyone else to the study of oligomorphic permutation groups, and has subsequently done much more in model theory and permutation groups, including work on o-minimality and on simplicity of automorphism groups.

Now Dugald is 60, and the occasion is being celebrated by a conference at the International Centre for Mathematical Sciences in Edinburgh, from 17 to 21 September this year. I will certainly be there. It looks like a super conference; many of the things I talk about here will be discussed at the meeting. The invited speakers are Peter Cameron (St Andrews), Zoé Chatzidakis (ENS, Paris), Gregory Cherlin (Rutgers), Richard Elwes (Leeds), David Evans (Imperial College), Ehud Hrushovski (Oxford), Martin Liebeck (Imperial College), Dugald Macpherson (Leeds), Angus Macintyre (QMUL), Peter Neumann (Oxford), Jaroslav Nešetřil (Charles Uni., Prague), Anand Pillay (Notre Dame), Cheryl Praeger (Uni. West. Australia), Charlie Steinhorn (Vassar), Pierre Simon (Berkeley), Slawomir Solecki (Cornell), Katrin Tent (Münster), Simon Thomas (Rutgers), John Truss (Leeds).

The web page for the conference is at http://www.icms.org.uk/permutationgroups.php. Space is limited, and registration closes on 8 June (or maybe 9 June), so apply now! There is a registration form available from the web page.

See you there!

Advertisements
Posted in events, history | Tagged , , , | Leave a comment

RA position in St Andrews

We are looking for a postdoctoral research assistant on the project “Bi-synchronizing automata, outer automorphism groups of Higman–Thompson groups, and automorphisms of the shift”. The Principal Investigator is Collin Bleak; I am the co-I.

The project involves an interesting mix of algebra, analysis and combinatorics: the description mentions “infinite groups of homeomorphisms […] automorphism groups of shift spaces, automata groups, the extended family of R. Thompson groups, enumerative combinatorics, and/or GAP coding”.

If you think this might be for you, details are at https://www.vacancies.st-andrews.ac.uk/.

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

The Royal Society of Edinburgh

RSE

I have been to the Royal Society of Edinburgh twice in the last two weeks, for different reasons.

Yesterday it was for my induction as a Fellow, along with forty-odd others. One of the things that we were told was that the RSE is trying to diversify its membership, and it is no longer true that all the new Fellows are 70-year-old male professors; but there are still a few of us, doing what we do best.

We were encouraged to spread the word about the RSE and the good things it does, so here is my small contribution.

The RSE was founded by royal charter from George III in 1783. It differs from many national academies in the diversity of interests of its Fellows: it is not just a scientific society like the Royal Society of London, although it is true that academics in the science subjects predominate. Academics in the humanities and social sciences, public figures, business people, authors and artists all figure. Indeed, probably the best-known President ever was Sir Walter Scott, whose towering monument you pass on the way to the RSE premises from Waverley Station in Edinburgh.

Among its other functions, the RSE gives entirely non-partisan advice on matters of national interest to the Scottish government.

Before the induction ceremony we were given a tour of the building, whose chief treasures are large portraits of famous people, mostly former presidents. Here are a few of them: Michael Atiyah, Thomas Brisbane, David Brewster, P. G. Tait, and D’Arcy Thompson. (Which of these was not RSE President?)

RSE Presidents

Brisbane gave his name to the city where I was an undergraduate for four years (educated in a system based on the Scottish system). According to our guide, he took the job as Governor of New South Wales because he was an astronomer and was interested in viewing the Southern stars. But he was not the worst governor of New South Wales, although there are probably fewer things named after him than either his predecessor Lachlan Macquarie or his successor Ralph Darling. (Incidentally, in Australia he is Thomas Brisbane but the RSE calls him Makdougall Brisbane.)

My previous visit two weeks ago was for a lecture on the new Queensferry Crossing, given by Naeem Hussain, the global leader of bridge design at Arup, who had designed it. It was a good lecture, inspiring and humorous by turns. He told us that he first came to the UK in 1964, went for a holiday in Scotland, saw the then-new Forth Road Bridge, and thought to himself, “I wish I could have designed that bridge”. So, fifty years later, he got his chance. Designing a third bridge to stand beside the two iconic bridges already there was an aesthetic as well as an engineering challenge, as he acknowledged; the new bridge, like the one on the other side (the nineteenth-century Forth Bridge) has three cantilever points, while the one in the middle is suspended from two points. Moreover, although politicians boast that the bridge towers are the highest such in the UK, Naeem would rather stress how low they are. (He made them as low as the engineering would allow, and used slim pillars rather than the more common A, H or diamond shapes, so as not to overwhelm visually the other two bridges.)

This was preceded by a trip to the Visitor Centre where we had a view of the three bridges, some models of the new one, and talks by the person who commissioned it, the engineer who built it, and a university professor who gave a very entertaining talk putting it into context. (Did you know that, when the Forth Road Bridge was designed, the only motorway in the UK was the Preston By-pass?)

Here are the bridges, taken last year from the Fife side, near Aberdour.

Three bridges

On that occasion, I was able to take a good look at the grant of arms to the RSE. The heraldic description includes the phrases

Per fess wavy Sable and Argent the scientific sign “D.N.A. Helix” fessways enhanced Gules and Azure

and

A celestial crown Or showing five mullets Argent

Do you know what “mullets” are in this context? (You might be able to cheat by looking at Wikipedia.)

Posted in events, history | Tagged , , | 1 Comment

London Combinatorics Colloquia

London

The second speaker at this year’s Queen Mary colloquium, János Pach, said at the start of his talk that he first came to Britain as a backpacker some years ago; at that time he never imagined that by now there would be enough combinatorialists here to fill the quite large Peston Lecture Theatre in the Graduate Centre.

He was kind enough to mention me as one of the people who had helped bring this about, but (quite rightly) attributed a lot of credit to Paul Erdős and Bill Tutte. He told Bruce Schechter’s story about how Erdős had changed the course of Western civilisation, which bears repeating, I think. Erdős, seeing which way the wind was blowing, left Hungary in 1934. His first stop was Cambridge, where he posed the problem of tiling a square with finitely many pairwise non-congruent squares. (There is some suggestion that Erdős thought that it would turn out to be impossible.) Four bright undergraduates, Brooks, Smith, Stone and Tutte, took up the challenge, and found an elegant method that led them to the existence of such a decomposition. This success inspired Tutte to change from chemistry to mathematics. At this he made enough of an impression that he was recruited for Bletchley Park, where he broke the Lorenz Sägefisch cipher used for strategic communications by the German high command, which according to some historians may have shortened the war by a couple of years.

Since I have started with János Pach’s talk, I will say more about it. His abstract on the website and in the conference book said, simply,

This will be the bestest talk ever.

An insert gave a much more detailed abstract. In his talk, he disclaimed all responsibility for the short abstract, but said it would probably be the best part of the talk, and that things would be downhill from here on. Not so, in fact; for me, his talk was the best of the day, even if it ran over time a bit. He was talking about the analogous problem for tiling an equilateral triangle with pairwise non-congruent equilateral triangles. He and Gabor Tardos have proved that there is no such tiling, by a remarkable proof, which begins with some elementary geometry, and then wheels in random walks and martingales!

Carsten Thomassen spoke first, and told us about several new results on flows on graphs, where the flow values are restricted to a subset F of an abelian group A. (Incidentally, Carsten used G for a graph and Γ for a group; I had to change Γ to A in my notes so as not to confuse myself.) As well as the set of non-zero elements of a finite abelian group, he considered cases such as the set of third (or fifth) roots of unity in the complex plane, or the unit sphere in 2- or 3-dimensional Euclidean space.

After lunch, we had a Ramsey theory talk from Paul Russell. He began by showing us that, if the natural numbers are finitely coloured, there is an infinite subset such that all sums of two distinct elements have the same colour. Can you make the same statement for all subsets? No, he showed us ingenious constructions which refute this. These can be extended to the integers, the rationals, and finite or countable dimensional vector spaces over the rationals; but in very large vector spaces, the constructions don’t work, and the assertion holds.

Katherine Staden talked about the induced version of Turán’s theorem, maximising the number of induced subgraphs of a graph which are isomorphic to your favourite graph F. (This corresponds to the complement of Turán’s theorem as usually stated.) The induced condition makes the problem much harder; the answer is not even known for the four-vertex path. She considered the case where F is complete partite (that is, there is a partition of the vertex set so that F has all edges between parts and none within parts). In this case, the extremal graphs are partite, and there are uniqueness and stability results, proved by turning the question into an algebraic optimisation problem.

Agelos Georgakopoulos (who had to pull out at short notice last year because of the birth of his baby) talked about some nice results on the analyticity of the percolation probability function above the critical point. The tools are old theorems of Weierstrass together with some combinatorics (inclusion-exclusion, estimates for the partition function). He began with a growth model for the mafia, having the remarkable property that there is a finite limit graph which occurs almost surely as a limit component.

Finally, Nikhil Bansal spoke on the discrepancy problem: you have a family of subsets of a set, and you want to 2-colour the set so that each subset is as balanced as possible. There was a fairly recent breakthrough on this problem by Banaszczyk; Nikhil and his collaborators have found a simpler proof together with an algorithmic version which efficiently finds a colouring doing as well as the theory promises.

The weather is always beautiful for the London colloquia; this indeed goes back to the days when its predecessor used to be in Reading. It rained overnight but by morning the weather was fine again, a little cooler and a little clearer than the day before.

The second day, at LSE, featured an innovation: a poster competition, with a lot of entrants, which was judged by a subset of the speakers, and the prizewinners announced at the reception at the end of the day.

The first talk, by Perlis Sousi, was on random walks on dynamic percolation. People have considered random walks on the component containing the identity of graphs such as lattices (this component is infinite if the percolation probability is above the critical value). The new feature was letting edges change their status, independently of what it was before but with the same probability of being open; to make the question interesting, we assume that these changes are on a slower timescale than the movement of the random walker. (I wonder what would happen if you let the edges change faster but assumed some positive correlation between the new and old state of the edge.)

Patrice Ossona de Mendez has been working with Jarik Nešetřil and many others (incuding one of our hosts, Jan van den Heuvel) on sparsity in graph theory for some years now. They have developed two concepts of sparsity, called “bounded expansion” and “nowhere dense”, which turn out to be stable in the sense that a huge variety of alternative definitions come up with the same thing. He talked about five questions, concerning graph colouring, Hasse diagrams of posets, VC-dimension of families induced on subsets by vertex neighbourhoods, category theory, and first-order definability. Then he defined some new concepts called “structurally X”, where X is one of the two types of sparse graph; such graphs can be quite dense but many results about them (including complexity) work similarly to the sparse case. As usual with Patrice, it was an elegant talk, but there was rather a lot of material to take in.

After lunch, Sofia Lindqvist gave an assured performance on her result with Ben Green on monochromatic solutions to x+y = z2 in the natural numbers. They have found a phenomenon which to my knowledge has not been observed before: the answer is that they must exist for two colours, but can be avoided for three or more.

Maria Axenovich talked about induced arboricity. The arboricity of a graph is the least number of forests needed to cover all the edges of the graph. This is a well-understood parameter, and a theorem of Nash-Williams gives a formula for it. For induced arboricity, you require the subgraphs to be induced forests, which makes things far more complicated.

It is easy to see that a graph with maximum degree Δ can be coloured with Δ+1 colours (a sequential algorithm does this since there is always a colour available). Choosing a random colouring is different, and a Markov chain based on recolouring a vertex if possible requires at least Δ+2 colours (and it is conjectured that this is enough for the Markov chain, or “Glauber dynamics” as it is known, to be rapidly mixing. However, the best we knew until recently was a result of Vigoda that (11/6)Δ is enough for rapid mixing. Michelle Delcourt and her team have shaved a bit off this constant. Within a week of their result being announced, another team announced that with a different method they had shaved a bit more off.

The final talk, the Norman Biggs lecture, was given by Alexander Sidorenko, who pulled a remarkable rabbit out of a hat. He talked about two apparently unrelated areas: first, the largest Sidon set (containing no solutions of x+y = z+w), or set containing no subset summing to zero, or containing no arithmetic progression, in certain finite abelian groups. Last year there was an amazing breakthrough on the “no 3-AP problem” in abelian groups of exponent 3. The other problem was the “codegree Turán problem” for hypergraphs. He showed how results on the first type of problem can give substantially improved bounds for the second.

Posted in events | Tagged , , , , , , , | Leave a comment

Two a day

In the distant past, issues of a journal would appear every two or three months, and publication date was no more precisely defined than this; you would only know that your paper had appeared when you received the journal (if you had subscribed) or your reprints (if you have ordered any).

Now each paper has a date of its on-line publication. These dates are not a lot of use for establishing priority, since the arXiv already does this, but are necessary for filling in data on institutional repositories.

This week, I had two papers published on the same day, something I don’t think has happened to me before. One, with R. A. Bailey and Tomas Nilson, was in the Australasian Journal of Combinatorics, where publication means that it comes with volume, issue and page numbers (this is a diamond open access journal which only publishes on-line). The other, with Bertalan Bodor and Csaba Szabó, was in Algebra Universalis, and is now “first on-line” for an indefinite period.

I have discussed them here and here.

By coincidence, both are in memorial volumes, for Anne Street and Tamás Schmidt respectively.

Posted in publishing | Tagged , , , | 3 Comments

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.

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)nk. 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 y1, …, yk, there exists x such that x and yi 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.

Posted in events, exposition | Tagged , , , , , , , | Leave a comment

Kourovka Notebook, 19th edition

The latest edition (the 19th) of the Kourovka Notebook has just been released. It now has its own website, https://kourovka-notebook.org/.

The Kourovka Notebook has been going for more than 50 years, longer than my life as a mathematician. It is a problem book for group theory and related areas, and now contains somewhere around a thousand problems, 111 of them new in this edition. The first edition appeared in 1965, and the KN did a remarkable job of encouraging communication across the Iron Curtain in those tense times. There are about 20 problems from that first edition still unsolved, and the first two to be attributed (rather than just labelled “Well known problem”) are by Mal’cev and Magnus. The last two questions ask whether the identical relations of a polycyclic group, or of a matrix group in characteristic zero, have a finite basis. This was a time of great activity in the area of varieties and identical relations of groups, coming shortly after the Oates–Powell Theorem demonstrated that the identical relations of a finite group have a finite basis. This topic is still of interest; the last problem in this year’s crop asks whether there is an infinite group, all of whose proper subgroups are cyclic of prime order p (a Tarski monster), which satisfies no identical relations except for xp = 1 and its consequences.

I was fortunate enough to become a contributor fairly early in my career: two of my problems from the ninth edition survive, including one which I think it would be timely to return to. Suppose that G is a finite primitive permutation group of rank r, and suppose that the maximum rank of any transitive constituent of a point stabiliser is s. Is it true that either r is bounded by a function of s, or the stabiliser of a point has rank s (and so acts regularly on one of its orbits)? (This formulation is slightly updated.)

The first part of the book (up to page 152) is the list of unsolved problems (or problems which have been solved since the last update a few years ago). Then there is an archive of solved problems, giving references to the solutions (in English if possible). Finally there is an author index of contributors.

The Kourovka Notebook, which as I said was such an important communication tool between group theorists right from the start, is clearly going from strength to strength. Any group theorist, and many people in related parts of algebra, logic and discrete mathematics, will find plenty of challenging problems here.

Posted in doing mathematics, history, open problems | Tagged , , | 1 Comment