8th Cracow Conference on Graph Theory

How do two people share a cake? As everyone knows, one cuts and the other chooses. This does not assume that the two people value the cake in the same ways: maybe one loves cherries, and the other hates icing.

In more mathematical terms, each person has a measure on the cake; without loss, the total measure is 1. The procedure satisfies two fairness conditions:

  • Proportionality: each person gets at least half of the cake, according to her valuation.
  • Envy-freeness: neither person prefers the other’s piece of cake to her own.

It is fairly well known that there is an extension which allows n people to share a cake fairly (satisfying the above criteria).

Why am I discussing this in the account of a graph theory conference? Because my choice of the most interesting talk at the conference was Zbigniew Lonc’s talk on this topic.

There are many real-life situations which don’t look like cake-cutting. For example, in a divorce case, maybe a house and a car have to be shared, and half a house or a third of a car are not much use. So it is reasonable to consider a discrete version of the problem, where there are m indivisible goods to be shared among n agents, each of whom has a valuation on each of the goods. This turns the problem into discrete mathematics.

In this case, easy examples show that we cannot satisfy the fairness criteria above. How can they be relaxed? One way is the maximin condition. Each agent considers all partitions of the set of goods into n parts and notes the value of the least valuable part. The maximum of this over all partitions is the best that this agent could expect to get in a “fair division”. An allocation of goods to agents is said to be a maximin share if each agent gets at least this maximin value. A maximin share may not exist (though failures seem to be fairly rare), but it is not even known that the existence of a maximin share is in NP.

But now let us add a further complication, which brings the problem into the realm of graph theory. Suppose that the set of goods is the vertex set of a graph, and we require that the share of each agent should be connected. (Suppose that the agents are farmers and the goods are plots of land; each farmer should get a contiguous set of plots.) We can easily extend the maximin share principle to this case (consider only partitions into connected parts). But can it be done? This question has only been answered for rather special graphs and small numbers of agents.

I wanted to ask a question, but couldn’t formulate it quickly enough. Suppose that, instead of insisting on connected parts, we imagine that each agent puts a value on connectedness (perhaps a decreasing function of the number of parts, or an increasing function on the degree of connectedness). How does the problem change? In a divorce case, the parties would not be happy with a division which gave the television to one and the remote to the other, but they could probably live with it.

The conference was in Rytro, a village more than two hours from Krakow in the mountains, with swimming pool, etc., and a ski lift next door. Brief comments on some of the other talks follow.

There were several talks on the distinguishing index of a graph, the least number of colours required to colour the edges so as to kill all automorphisms. I hope it wasn’t the case that they invited me on the strength of my survey paper with Robert Bailey on similar things (I didn’t realise that I should worry about this until too late, since my talk was the first of the conference.) This number is very small, even if you allow the automorphisms the possibility of permuting the colour classes rather than fixing them.

There were also a number of talks on “facial total colourings” of graphs embedded in surfaces, like the more usual colourings except that edges are only required to have different colours if they are consecutive in a face. There are variants where edges at most k steps apart must get different colours, or where you colour incidences rather than vertices and edges.

Sandi Klavžar talked about the “strong geodetic number” of a graph, a new topic where you ask for a set of vertices and a choice of shortest paths between all pairs in the set so that every vertex of the graph is covered. All published papers on this are 2018 or later. I asked at the end what happens if you want to bound the load on any vertex (the number of paths passing through it), which seems a reasonable condition for a network. He said that is the next thing they are going to look at.

Nikolay Abrosimov gave a talk which was not graph theory, but which I enjoyed. He was talking about the volume of a polyhedron in hyperbolic space, in terms of its side lengths. Once a popular topic (both Lobachevsky and Thurston considered it), but perhaps a bit unfashionable now. Anyway, he had completely solved the problem for symmetric antiprisms.

Akira Sato gave a most enjoyable talk. He was considering two famous results about existence of Hamiltonian cycles, by Ore and by Moon and Moser for bipartite graphs. Can you deduce Ore from Moon and Moser? No, there is a gap of one in the required inequalities. But perhaps you can find all examples attaining the Moon–Moser bound, and find a workaround for these. This can be done, and a lot of interesting arguments have to be deployed to do it.

Marthe Bonamy, the last plenary speaker, gave a thought-provoking talk. It was a pity that many people had already left. It was a graph colouring problem in which the traditionally easiest graphs are the hardest, while a lot of traditionally hard graphs are very easy.

She imagines that each node has unlimited computing power but can only communicate with its neighbours, so has a very local view of the graph. Clearly a path of length n is going to take at least n steps to agree a colouring. But given any graph, if you add a vertex joined to every other vertex, this vertex will see the whole graph in a small finite number of time steps, and can then use its unlimited computing power to find a proper colouring, and then order the others to use it. One of the difficulties (clear even in the path case) is conflict resolution; she talked about this but I am not sure I followed it.

The conference excursion was to the top of Przehyba, an 1175-metre mountain which involved a hike of more than 20 kilometres. With a party of 27 walkers and a guide, of course we didn’t go very fast, and there was plenty of time to view the many different kinds of fungi that grew near the park. By contrast, apart from flies and wasps, there was very little wildlife to be seen: two butterflies, a small passerine bird I couldn’t identify, and a pigeon, and on the way down a pair of crows and a dead mole. From the lunch stop at the restaurant on top of the mountain (a feature we don’t have in Scotland!), we could see the much higher Tatra Mountains in the distance.

Tatras

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

Groups, geometries and representations

Here, more than a week late, are comments on the conference formally titled “Groups, Geometries and Representations, Oxford 2018”, actually a birthday conference for Dan Segal and Aner Shalev.

I stayed in Balliol College’s new Jowett Walk Building, just around the corner from Holywell Manor, the Balliol – St Anne’s graduate centre where I stayed as a graduate student nearly 50 years ago. So I was able to walk through the University Parks to the Mathematical Institute as I did back then, although the Institute itself has moved to a new site where the Radcliffe Infirmary once stood.

As usual, I can only highlight a few talks. On the firt morning, Bob Guralnick told us about the discovery of some huge first cohomology groups of finite groups which led to the demise of Tim Wall’s conjecture (that the number of maximal subgroups of a finite group did not exceed the order of the group). Actually my reading of the write-up of this suggests that Wall’s conjecture is very nearly true, and the number of maximal subgroups of a group of order n may be bounded by n1+ε for some small ε.

Martin Bridson started his talk with a little gem. Consider the three groups with presentations as follows:

  • G2 = ⟨a,b:ba=a2b
  • G3 = ⟨a,b,c:ba=a2b,cb=b2c,ac=c2a
  • G4 = ⟨a,b,c,d:ba=a2b,cb=b2c,dc=c2d,ad=d2a

Then he said, one of these groups is infinite with infinitely many finite quotients; one is infinite with no non-trivial finite quotients, and one is trivial. He took a vote on which is which, which was indecisive; this reinforced his point that a presentation is a very bad way to convey information about a group.

I happened to know the answer. G2 clearly has many finite quotients, since all we need is a group with an element conjugate to its square. (In fact this is the Baumslag–Solitar group. I recognised G4 as a group used by Graham Higman exactly because it is infinite with no non-trivial finite quotients (a pleasant exercise), and I had once used it for a similar purpose. Therefore G3 must be trivial. (Is this a proof of that fact??)

He went on to speak about what information the set of finite quotients of a group (in other words, its profinite completion) tells about the group (assuming it to be residually finite, unlike Higman’s group, which is not distinguished from the trivial group by its finite quotients).

On the second day, John Thompson talked about projective planes. He had some difficulty in writing on the board, but he spoke completely clearly. He presented us with an outrageous conjecture, designed to challenge us to solve the extremely difficult problem of finding the set of orders of finite projective planes. His conjecture was that this set is equal to the set of orders of direct powers of finite simple groups, both abelian (which gives the familiar prime powers) and non-abelian (so the first test case would be 60). In the title of the talk he mentioned the Hall–Paige conjecture; he ran out of time to tell us about this conjecture and its proof, but did so in answer to a question.

On Wednesday, Alex Lubotzky started his talk by saying, “I should thank the organisers for inviting me. But I found out later from Martin Liebeck that I was an organiser.” Indeed, organisation was very low-key. There was no paper version of the programme or abstracts, or even paper to write on; and registration consisted of participants sorting through a random heap of name badges on a table to find their own. (I am sufficiently old-fashined that I like having at least a printed programme. Indeed, when Martin asked me to chair a session, I said that my fee was a hard copy of the programme.)

Alex proceeded to give a beautiful talk, one of the highlights of the conference. He used the phrase “Finite to infinite”. This reminded me of an evening in a restaurant in Budapest, where Laci Babai and I planned a conference with the title “Group Theory: Finite to Infinite”; it was held in a hotel near Pisa, where there was much discussion of profinite groups, and where we shared the hotel with a football team (I don’t now recall which one) whose manager was constantly on the phone trading players and doing other deals.

There was much in Alex’s talk, but here is just one thing, which I had heard about but not internalised before. This is the notion of a sofic group, one which can be approximated by finite symmetric groups with normalised Hamming distance. (This means that there are near-homomorphisms from G to these groups, where the images of any non-identity element don’t get arbitrarily close to the identity.) Of course, every finite group can be embedded into a finite symmetric group; but infinite groups are much wilder. Nevertheless, it is currently open whether every group is sofic. If so, this would be an extraordinary statement of the power of the innocent-looking group axioms; so, if I had to bet, I would put money on the existence of non-sofic groups. But it appears to be a very hard question.

I can’t fail to mention Goulnara Arzhantseva’s construction of expander graphs where the diameter to girth ratio is bounded, from high-dimensional linear groups.

Nor can I fail to mention Persi Diaconis, was doing random walks on the irreducible characters of finite or compact groups, in a way which recalled the McKay correspondence. You pick a fixed irreducible χ; if you are currently at a character φ, you tensor φ with χ, decompose the result into irreducibles, and pick an irreducible with probability proportional to the product of its degree and its multiplicity. Many familiar and unfamiliar random walks arise. For example, for SU(2), you get the usual random walk on the integers conditioned on never going negative. He also developed a modular version of the same thing.

Cheryl Praeger talked about finding combinatorial structures whose automorphism groups are maximal subgroups of finite symmetric groups. For intransitive groups, you take a subset; for imprimitive groups, a partition (a set of subsets, pairwise disjoint and covering all points); for primitive non-basic groups, a Cartesian structure (which, as Laci Kovács pointed out, can be regarded as a set of partitions satisfying appropriate conditions). For affine groups, you take the affine space. What about diagonal groups with more than two factors? Cheryl described these as collections of Cartesian structures. It seems to me, at least for three factors, that they can be described as Latin squares, essentially the Cayley tables of the factors. (Most naturally, the diagonal group preserves the set of triples whose product is the identity.) This story is not yet finished.

Katrin Tent showed us the construction of infinite “non-split” sharply 2-transitive groups, at least for characteristic 0 or 2. For finite odd characteristic, the problem is more difficult. But she claims that the methods they have used to handle this case may actually lead to substantial advances on the Burnside problem, at least for odd exponent. Again, the story is not finished.

Colva Roney Dougal (the latest of my former students to be made a Professor) opened the proceedings on Friday with a talk entitled “Random subgroups of finite symmetric groups”. The main thrust is the new results she and Gareth Tracey have almost finished on this problem where you choose from the uniform distribution on subgroups, but she began with a beautiful summary on other methods such as random generation. Yet another not-quite-finished story; the precise result is not available yet and is eagerly awaited.

Colva also revealed that Friday happened to be Cheryl’s birthday.

The conference was concluded by a lovely talk from Ben Green. He had proved this theorem as a result of a question from Kufei Zhao, but he didn’t tell us about that. His result says that symmetric subsets of the unit sphere (that is, orbits of a finite group) in high dimensions are almost flat, in the sense that they lie on a thin slice through the centre of the sphere (precisely, there is a unit vector whose inner products with vectors in the symmetric set are in absolute value bounded by c/√(log d) in dimension d. He started by “cooking” his own theorem by pointing out that this is not as surprising as it seems. The vertices of the cube, for example, normalised to lie on the unit sphere, have all coordinates ±1/√d, and so are almost orthogonal to a unit basis vector.

The theorem itself used a quantified version of the theorem of Jordan, according to which a finite subgroup of the unitary group U(d) has an abelian subgroup bounded by a function of d. The quantification was due to Michael Collins (I believe Boris Weisfeiler also worked on this problem but his results were unpublished). Anyway, Collins’ result was not quite strong enough to use as a black box by Green, so he had to open the box and re-do some of the arguments. Not a straightforward task, and a number of ideas from probability theory also crept in.

Posted in events | Tagged , , , , , , | 2 Comments

and G is for …

I am in Oxford for the birthday conference for Dan Segal and Aner Shalev. I will write something about that when time permits.

This is just to report a discovery. There is now an official “Oxford Mathematical Alphabet”. I have lost count of the number of lectures I heard in Oxford which began “Let G be a group.” But not any more, it seems. In the Oxford mathematical alphabet, G is for … Growth Tensor.

Posted in Uncategorized | Tagged | 3 Comments

Q is for quantum?

The letter q has three, or maybe four, standard uses in mathematics.

It stands for “quantum”, and it is fashionable now to produce quantum versions of everything from chromatic number of a graph to the symmetric group.

Related to this, q occurs as a “deformation parameter” in quantised versions of standard algebraic structures. That is, there is an algebra depending on a parameter q, and as q tends to 1, the algebra becomes a “classical algebra”. There can be real advantages to doing this. It may be that the representation theory of the classical algebra is difficult, but that of the deformed algebra is easier, and we can get some information about the classical case by taking a limit.

It is also quite common to use q as a formal parameter in certain power series counting objects of interest. For example, consider the problem of counting lattice paths from the origin to the point (m,n), where m and n are non-negative integers. Each step in the path must be a unit step in either the easterly or the northerly direction. We have to take altogether m+n steps, of which m must be easterly and n northerly; these steps can be taken in any order, so the number of paths is the binomial coefficient, which I shall write as Bin(m+n,m). But now let us refine the count. Each such path, together with the X-axis and the line x = m, encloses a certain area A (between 0 and mn inclusive). Now if, instead of counting 1 for each path, we count qA to a path enclosing an area A, the sum we get is the Gaussian coefficient Gauss(m+n,m)q. This is calculated by replacing each integer k in the expression for the binomial coefficient by the “q-integer” qk−1. Since the number of factors in numerator and denominator is the same, an application of l’Hôpital’s rule shows that the Gaussian coefficient tends to the binomial as q→1.

Finally, the number of elements in a finite field (which is a prime power) is universally referred to as q. This is so ingrained that the finite fields community call their annual conferences Fq, a standard notation for a field of q elements.

Now something unexpected and wonderful holds. The binomial coefficient Binom(n,k) counts the number of k-element subsets of a set of size n; and the Gaussian coefficient Gauss(n,k)q counts the number of k-dimensional subspaces of an n-dimensional subspace over the field Fq.

There are many analogies and parallels between the combinatorics of subsets of a set and the combinatorics (or projective geometry) of subspaces of a vector space, especially over a finite field. This leads us to sometimes describe the former as “geometry over the field with one element”, as I have discussed on another occasion.

This long introduction finally brings me to my topic, a paper entitled “Defining the q-analogue of a matroid” by Relinde Jurrius and Ruud Pellikaan, which appeared in the Electronic Journal of Combinatorics last month.

Matroids are combinatorial structures which describe many kinds of “independence”: linear independence in a vector space; algebraic independence over a ground field in an algebraically closed field; forests in a graph; partial transversals of a set system; affine independence in an affine space; and so on. They were introduced by Whitney, and their theory was developed by Tutte, Rota, welsh, and many other mathematicians. Take a look at the Matroid Union blog to learn more.

Jurrius and Pellikaan are not producing a quantum version of matroid theory. Rather, as in the last case above, they are defining a structure over a field with q elements to be the analogue of a matroid in the usual sense over the “field with one element”. More precisely, they define a q-matroid to be a finite-dimensional vector space E over Fq, together with a rank function r from the set of subspaces of E, satisfying exactly the same conditions as for a matroid, namely, for all subspaces A and B of E,

  • 0 ≤ r(A) ≤ dim(A);
  • if A ⊆ B, then r(A) ≤ r(B);
  • r(A+B)+r(AB) ≤ r(A)+r(B).

Of course, matroids can be defined in many other ways: in terms of their independent sets, bases, circuits, and so on. Something a little unexpected emerges. For the analogue of independent sets, for example, we have a collection of subspaces called independent spaces, satisfying exact analogues of the independent-sets axiom for matroids, but with an extra axiom, which cannot be dispensed with. It states that if A,B are subspaces, and I,J are maximal independent subspaces of A,B respectively, then there is a maximal subspace of A+B which is contained in I+J.

About halfway through the paper comes the motivation for studying q-matroids. Just as ordinary (representable) matroids arise from (linear) codes, it turns out that q-matroids arise from “rank metric codes”, structures using the rank of the difference between matrices as a measure of how far apart they are.

Right at the end of the paper, they mention that the notion of a quantum matroid has been defined by Paul Terwilliger; it is closely related to that of q-matroid. There is also related work by Henry Crapo.

The paper contains many research topics. One of these concerns the Tutte polynomial. How should it be defined in such a way that Greene’s link between Tutte pollynomial of a matroid and weight enumerator of the corresponding linear code has an analogue for q-matroids and rank metric codes?

Posted in Uncategorized | Tagged , , , , | 2 Comments

Linstat 2018

Or, to give the full title, International Conference on Trends and Perspectives in Linear Statistical Inference, with Celebration of Tadeusz Caliński’s 90th Birthday.

Będlewo Castle

The conference was in Będlewo Castle, once a private residence for a noble family which had more than its share of scandal, now a mathematics conference centre something along the lines of Oberwolfach, with nearby woods for walking, and in a village with a stork’s nest (now inhabited by house martins) on top of the church tower.

I have been to several statistics conferences before, but this is the first time I have ever spoken at one. And more: I organised a session on Combinatorics with applications to experimental designs. I will say a little bit about this later; but here is my team.

Special session speakers

It was a very enjoyable conference (or would have been, had I not had so many urgent jobs hanging over my head, including two MSc dissertations to read which arrived while I was at the conference). On Tuesday there was a special session for Tadeusz Caliński’s 90th birthday. His career has been truly remarkable. He is responsible for the close links that have existed for more than 50 years between Polish statisticians and those in many other countries including the UK, France, Italy and the Netherlands. He managed to travel to France even after the declaration of martial law in Poland, because the collaboration had been agreed at high level between the French and Polish governments. (But a couple of years later he was refused permission to travel to Canada, ostensibly for some stupid reason which I do not recall, but actually because he was not a party member but, worse, a supporter of Solidarity.) Many friends he met in the 1960s on his early travels to the west are now dead, but many of those who are still alive had come to the conference to honour him, including Gavin Ross and Rob Verdooren. (But, on the other hand, there were many talented young people there.)

On Tuesday evening there was a concert of music by a string quartet, slightly marred by the fact that people were unsure about when each piece was finished. But the musicians did a good job, and we were regaled with stories about the composers.

On Wednesday there was a choice of excursions, to Kórnik Castle, or to walk in Wielkopolska National Park – I chose the latter. The park was very dry because of the unusual weather, and we were told that the lakes were somewhat polluted (indeed, we saw a machine whose purpose was to help oxygenate the lake water). After the walk they had put out an impressive spread of food for us, but we didn’t fall on it like locusts, since we knew that there would be a barbecue when we got back to Będlewo. The barbecue, as well as huge amounts of food, featured entertainment by a group of musicians in some kind of traditional dress playing violins and bagpipes.

Castle and frog

Thursday was the Conference dinner, and presentation of prizes to the young
researchers. A pianist entertained us during the dinner.

I will mention just two talks, which for me were the highlights of the meeting.

Friedrich Pukelsheim, from Augsburg, was a statistican, who wrote a book on optimal design. He switched fields, and is now a sociologist, or political scientist, who looks at electoral systems (with a mathematician’s eye).

Many legislatures have, in some form, a principle known as degressive proportionality: the higher the population of a region, the larger the ratio of electors to representatives. But the European parliament is unusual in having this as a formally stated law. Unfortunately, the last election failed to meet this requirement precisely. Friedrich was on a small committee of mathematicians charged with ensuring that the principle is complied with in future. The European parliament is also unusual in trusting mathematicians to do this job, though they don’t trust them enough to accept a formula for the allocation of seats to countries, so the process will have to be repeated for the following election. Friedrich gave us an analysis of the case of Catalonia, where the legal requirements are somewhat contradictory, and in any case are based on population figures from the 1970s. He has written a book, which he recommended as a present for our loved ones.

I have worked a bit on optimality criteria for block designsl the most commonly used of these can be expressed in terms of the Laplacian eigenvalues of the concurrence graph of the design. Thus, A- and D-optimality maximise the harmonic and geometric means of the nontrivial eigenvalues, while E-optimality maximises the smallest eigenvalue.

In a nice but fast-paced talk, young researcher Samuel Rosa used graphs in a different way. We are comparing n different treatments, with no blocking factors, and we have a collection of pairs of treatments whose comparisons we are most interested in. A classical case involves a comparison of just two treatments; we should allocate experimental units as equally as possible to the two treatments.

In the general case, the interesting comparisons form the edge set of a graph; our task is to allocate weights to the treatments, giving the proportion of experimental units which should be allocatedd to them, in an optimal way. (Here, unlike the former case, the graph is given in advance.) It turns out that, again, the optimal allocations are determined by the Laplacian matrix of the graph. If I got the details right, assuming that the Laplacian has rank n−1, then the D-optimal assignment is uniform; the A-optimal weights are proportional to the square roots of the vertex degrees; and the E-optimal weights are proportional to the vertex degrees.

Quite a few statisticians use Jordan algebras in their work. So I put my neck on the block and talked about the notion of Jordan schemes (a generalisation of association schemes). However, from some of the other speakers, I realised that there was a mismatch between the statisticians’ notion of Jordan algebra and mine. After a robust discussion with Roman Zmyślony, things became a bit clearer to me, and I offered to write up some notes on this. I will report when I have done the job.

I had a bit of trouble getting the Polish ogonek on the first e in Będlewo in my slides. The solution I finally used was a package optimised for Computer Modern and Times Roman, but even the package authors agrees it is not entirely satisfactory for other fonts.

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

The existential transversal property

One of the first things that João Araújo introduced me to when we started collaborating, after synchronization, was the universal transversal property: a permutation group G on the set {1,…,n} has the k-universal transversal property (k-ut for short) if, given any k-subset A and k-partition P of the domain, there is an element of G mapping A to a transversal to P. (Here I say “k-subset” for a subset with k elements, and “k-partition” for a partition with k parts.

This appealed to me because it resembles the classical notion of k-homogeneity (or k-set transitivity): G has this property if, given any two k-sets A and B, there is an element of G mapping the first to the second.

One of the first results on this was by Livingstone and Wagner in 1964. Their paper has three main theorems; the first says that, if k ≤ n/2, then a k-homogeneous group is (k−1)-homogeneous. The proof of this theorem is a short and elegant application of character theory, which can be rewritten as pure combinatorics. João and I were able to prove that, under the same restriction, a group with the k-ut property also has the (k−1)-ut property. Our proof, however, was much less short and elegant, involving some nontrivial group theory (including the Classification of Finite Simple Groups.)

It turns out that this is relevant to semigroup theory. Let t be a mapping of the domain which has rank k (image of size k). Semigroup theorists will not be surprised to learn that, if G has k-ut, then every such map is regular in ⟨G,t⟩ (that is, has a von Neumann inverse). But then our result implies that the same is true for all elements of smaller rank as well; that is, the entire semigroup ⟨G,t⟩ is regular.

In the paper we went on to classify the groups with k-ut (with some exceptions we were unable to decide) for 3 ≤ k ≤ n/2. (It turns out, happily, that the 2-ut property is exactly equivalent to primitivity, so we didn’t feel obliged to give a complete list.)

So what next? We went on to consider the k-existential transversal property, or k-et for short. This requires that there is a “witnessing” k-set A such that, for any k-partition P, there is an element of G mapping A to a transversal for P. This is substantially weaker than the k-ut property, but does have the consequence for semigroups that, if the image of t is a witnessing set for k-et, then t is regular in ⟨G,t⟩. The problems are considerably harder, and we had to recruit Wolfram Bentz to help us.

It turns out that one can say quite a bit. We suppose that G satisfies k-et, with k ≤ n/2, as before. We can deal completely with the case that G is intransitive: for k ≥ 3, it must fix a point and act (k−1)-homogeneously on the remaining points. So we can suppose that G is transitive. Here are some of our conclusions.

  • If k ≥ 8, then G must be the symmetric or alternating group. 8 is best possible here: the Mathieu group M24 has the 7-et property.
  • There are groups satisfying k-et but not (k−1)-et: indeed, just two of them, the groups 24:A8 and 24:A7, with degree 16, satisfy k-et for k = 1,2,3,4,6 but not for k = 5.
  • If k ≥ 4, then G is is primitive (for n ≥ 9); and it is 2-homogeneous, with just two exceptions: the Higman–Sims group and its automorphism group, acting on 100 points.

Now if G is k-et with witnessing set A, and also is (k−1)-ut, and t is a map with image A, then ⟨G,t⟩ is regular; since as we explained above the elements of rank k (whose images are of the form Ag for gG) are regular, and the (k−1)-ut property ensures that all maps of smaller rank in the semigroup are regular. But the condition of (k−1)-ut is not necessary for regularity; if it fails, then the semigroup may or may not be regular, and in most cases we can say which possibility occurs.

The methods we needed to develop to tackle this harder problem turn out to be useful in advancing further our knowledge of groups with the k-ut property, so we also had a glance at this, which included correcting a couple of small mistakes in the earlier paper.

The et paper has just appeared on the arXiv: 1808.06085.

What next? There is a dual form of k-et, where we specify a witnessing k-partition P, and ask that any k-set has an image under G which is a transversal for P. A job for another day.

Of course, the ultimate in this line would be a complete characterisation of the pairs (G,t) for which ⟨G,t⟩ is regular. This is not currently on our radar screen, though.

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

Anniversary

Today is the 50th anniversary of my arrival in Europe. I arrived in Southampton on the Shaw Savill Line ship “Southern Cross” on 21 August 1968, after a 36-day voyage from Sydney. I intended to stay three years or so to get my doctorate, but in the event I am still living here, having been given indefinite leave to remain in the United Kingdom in 1971.

Southern Cross

When I visit Autralia, it always feels like home. But I feel comfortable in Europe (though a bit less so now, since the rise of nationalism in many parts of the continent, something I don’t understand).

I suppose that in some sense I count as one of the “Windrush generation”.

Posted in history | Tagged , , , | 11 Comments