Travels, 11

The next morning, after a very good hotel breakfast, we were checked out and in the lobby, waiting (with Cheryl Praeger) to be picked up and driven to the next event, a workshop on the Road Closure Problem.

Here is some background for the mathematically inclined. Let G be a finite permutation group on a set Ω. We adjoin to G a transformation t of Ω which is not a permutation, and ask about the transformation monoid M generated by G and t. The general question is: what properties of G guarantee that M has a certain semigroup property for all choices of t of rank k? For simplicity, I assume that k ≤ n/2.

It is known that the regularity of M for all such choices is equivalent to the k–universal transversal property of G (for short, k–ut).: this is the property that, for any k-element subset A and any k-part partition P in Ω, there is an element of G which maps A to a transversal for P. This property also guarantees that M contains an idempotent (an element e satisfying e² = e.

Semigroup theorists are interested in the property of being idempotent-generated. Now if G is nontrivial, then M cannot be generated by its idempotents, since the only idempotent in G is the identity, and permutations cannot be generated by non-permutations. So the natural question is whether M \ G is idempotent-generated. We will say that G has the k–id if this is true for all choices of the map t of rank k.

From what we have said, it is clear that k-id implies k-ut. This is especially relevant for k > 2, where we have almost complete information about the groups having the k-ut property. However, for k = 2, things are rather different: 2-ut is equivalent to primitivity, while 2-id is equivalent to the Road Closure Property, which I now describe,

Given a permutation group G on Ω, an orbital graph for G is a graph whose vertex set is Ω and whose edge set is an orbit of G on 2-element subsets of Ω. An old result of Donald Higman asserts that, for degree greater than 2, primitivity ie equivalent to the connectedness of all orbital graphs for G. Now the (stronger) Road Closure Property is the assertion that no orbital graph can be disconnected by remoging the edges forming a proper block of imprimtiivity for G. (The name comes from the fact that, in such a group, even if the workmen come and dig up all the roads in a block of imprimitivity, it will still be possible to travel round the network.

The problem, then, is to examine primitive permutation groups, and describe as precisely as possible the primitive groups which fail the RCP.

There was another problem as well, with a rather different character, of which Wolfram Bentz was the curator. For k > 2, we have much more information about the groups we need to consider, but not a precise comnbinatoral equivalent of the k-id property.

We set off, ten of us in two cars, for the drive to Serpa, a town in the south-east of Portugal, where we would work on this problem for a week. We stopped for lunch in a traditional restaurant on the outsikirts of the town of Alcácer do Sal. Soon after that we turned off the main road from Lisbon to the Algarve and headed east.

At first this was a good four-lane highway. But after a fairly short time it degenerated to two lanes, and then we came to the first of a number of stops for roadworks; possibly a bad omen for a work on the Road Closure Property. We passed the town of Serpa with its castle on a hill, and drove out into the couuntryside amid the regimented rows of olive trees until we turned off onto a smaller road, and finally onto a track leading to our destination: the big house on the Maria de Guarda estate, owned by the family who clearly make a good living from olive oil (and incidentally are friends of João, in common it seems with almost everyone else in Portugal). The old house had been extended in 1908 and again in 2008 and had enough bedrooms for the entire party.

The day ended in low farce. Nothing is open in this corner of Alentejo at weekends, and to get food we to pile back into the cars and make a long drive to the town of Beja which had a Pizza Hut which was open (it was about to close for the night but a party of ten made it worth their while to stay open a little longer).

After that things went in a more uniform manner.

There was a swimming pool behind the house, and a lake nearby. The swimming pool was a bit mucky, but the cleaning robot improved it as the week went on; the lake was muddy and covered in green algae. But we divided into those who preferred the pool and the hard core who liked the lake. By the end of the week, a truce had been reached and people swam in both. Swimming was only possible in the early morning and late afternoon because of the heat (it went above 40 degrees quite often).

Breakfast, at 08:00, provided good cereal (which could be adorned with nuts and chopped fruit), scrambled eggs, bacon, mushrooms, smoked salmon, bread, ham, cheese, and fruit. Wolfram and Poyi had brought along a coffee machine which was very heavily used.

Then we got down to work, in small groups focussing on different aspects of the problem, interrupted by lunch, until about 19:00, when we met for the groups to report on progress. The room we used for this contained a small wagon, which served as a whiteboard easel.

Lunch and dinner were cooked meals with masses of excellent food, with beer and Alentejo wine available.

Thia routine was broken twice. On Tuesday evening we drove in to the town of Serpa for dinner in a traditional restaurant. We opted for a limited menu: dogfish soup, and then a couple of dishes (which I don’t now recall, perhaps octopus and black pork). Then on Sunday morning, João declared that we were going to Serpa for the conference excursion. It turned out to be very interesting. There is an old castle, a bit knocked about by the Spanish (we were quite close to the border), but with splendid views over the local countryside from the top. The castle also contained a small archaeological museum. But the highlight was another museum which we visited later, a huge private collection of clocks and watches. This included, along with watches ranging from Patek Philippe to cheap watches for the masses, a limited edition Beatles souvenir watch, a clock in the form of a dog whose two eyes rotated to tell the hours and minutes (so that at certain times of day the dog was quite crosseyed), and Swiss-style cuckoo clocks made in Portugal.

Mathematically, how did we do? I am not going to explain in detail now since it is necessary to wait until things are written up to make sure of them. But in general terms, we made a huge advance. Groups with the road closure property are primitive, and cannot be contained in a wreath product with product action. For affine groups, that is the complete story. But it was diagonal groups where we had the breakthrough. Without going into detail, the socle of a diagonal group is a product of (say) m copies of a non-abelian finite simple group; and there is a permutation group of degree m permuting the factors, which must have no non-trivial invariant relations: that is to say, either it is the trivial group on two points, or it is primitive. In other words, from a given primitive group we can build many different primitive groups on diagonal type. Now, to simplify slightly, the diagonal groups have the road closure property if and only if the primitive group used in the construction does. So we have enormously expanded the class of primitive groups failing the road closure property.

For almost simple groups, we made less progress; a possible advance in the first two days proved to be illusory. But we did achieve some forward motion.

On the k-id property for higher k, we made some progress, and set up things for further progress to come. But one incident was quite a shock to me. On the first day, Wolfram gave us a simple-looking problem whose solution would settle one of the classes of groups which were still open. I soon realised that this could be done using a result of mine from 50 years ago (proved in Eindhoven, on the same visit that gave rise to the root systems approach to graphs with least eigenvalue −2. I really felt my age then. But the next day Wolfram told us that there was a mistake in his translation of the problem, and my 50-yeaer-old result was of no use.

After we got back from the excursion to Serpa, we had lunch, packed everything up, and then piled into the cars for the trip to Évora for the next event.