Hall’s Marriage Theorem

Philip Hall was one of the greatest group theorists of the twentieth century. But it may well be that he is known to more people for a result which on the face of it is pure combinatorics, with nothing to do with group theory: Hall’s Marriage Theorem.

In the story form in which it is usually told, it goes like this. Let g1,…,gn be girls. Suppose that each girl gi has a list Bi of boys she would be prepared to marry. Then a necessary and sufficient condition for it to be possible that all the girls marry boys from their list is that, given any set of k girls, their lists contain at least k boys altogether.

Said more formally, if B1,…,Bn are finite sets, a system of distinct representatives or SDR for these sets consists of n elements b1,…,bn such that

  • they are representatives of the sets, that is, bi belongs to Bi for all i;
  • and they are distinct, that is, bi ≠ bj for i ≠ j.

Then Hall’s theorem says that a necessary and sufficient condition for the sets to have an SDR is that the union of any k of them has cardinality at least k.

A moment’s thought shows that the condition is necessary; if the lists of k girls don’t contain at least k boys, then these girls cannot be married to boys on their lists. The proof that the condition is sufficient, that is, guarantees that the marriage arrangement is possible, is more difficult, but several very different proofs are known.

My purpose here is not to expound the proof, but to explain why a group theorist should be interested in this.

Let G be a finite group and H a subgroup of G. As you will know if you have done group theory up to Lagrange’s theorem, the right cosets of H in G (the sets Hg = {hg:hH}) are pairwise non-overlapping and cover G. Moreover, each coset has the same number of elements as H, since the map from H to Hg taking h to hg for all hH is a bijection.

If g1,…gn are elements such that the right cosets Hg1,…Hgn are distinct and cover the whole of G, we call these elements right coset representatives.

Similar statements hold for the left cosets, the sets gH = {gh:hH}. And from Lagrange’s Theorem, it follows that the numbers of left and right cosets are equal.

But in fact there is a much more elementary proof that these numbers are equal, which works equally well if G, H, or the number of cosets is infinite. Can you find it?

What Hall was after was the following statement:

Let H be a subgroup of the finite group G, with n cosets. Then there are elements g1,…gn of G which are simultaneously right and left coset representatives.

To see how this follows from Hall’s marriage theorem, we argue like this. Let x1,…xn be right coset representatives, and y1,…yn be left coset representatives. For each i∈{1,…,n}, let Bi be the set of indices j for which the left coset yjH has non-empty intersection with the right coset Hxi.

Now we claim that these sets of indices satisfy Hall’s condition for the existence of an SDR.

Let I be any set of indices, and let J be the set of all j belonging to the union of the Bi for iI. This means that the union of the right cosets Hxi for iI is contained in the union of the left cosets yjH for jJ. Since all cosets have the same size, this entails I ≤ J, as required.

So, by Hall’s marriage theorem, there exists an SDR for the sets B1,…Bn, that is, n distinct elements bi where biBi. This means that the intersection of the right coset Hxi and the left coset ybiH is non-empty. Take an element gi in this intersection. Then g1,…gn are both left and right coset representatives for H in G.

This is not the end of the story. Marshall Hall Jr. (another great 20th century mathematician who gave us textbooks on both group theory and combinatorics) extended Hall’s marriage theorem to the case where we have an infinite number of finite sets (that is, an infinite number of girls, but each has only finitely many boys on her list).

Using this, it is easy to see that Philip Hall’s observation about simultaneous left and right coset representatives holds also when the group G is infinite, provided that the subgroup H is finite.

As far as I can recall (and I admit my memory might be wrong), I have never actually used this nice result for anything; but I have always felt that there should be an application of it. Any thoughts?

Posted in exposition | Tagged , , , , | 13 Comments

Au revoir, GRA

River Cam

Today (Wednesday 18 March) the Groups, Representations and Applicatons programme at the Isaac Newton Institute came to a premature end.

There are still some hopes that it can be revived later, but at the moment the only certainty is that it is closed now.

The director of the Institute, David Abrahams, drew our attention to the fact that while Isaac Newton was self-isolating, he did some very good research.

I have my grumbles about various things, especially the accommodation in the Weat Cambridge desert (as I hinted here), but now is not the time for that.

The third workshop was reduced to two and a half days, many of the talks presented remotely, and even for the live ones only ten of us allowed in the huge lecture room. (This despite the fact that most of us had been working together since January.)

So I will just mention one talk, a beautiful talk (as usual) by Tim Burness, on the length and depth of a group. The length of a group is the length of the longest chain of subgroups in the group, and has various applications (the question of determining the length of the symmetric group was raised by Babai and is fairly distantly connected with graph isomorphism). I believe I was the first person to find the beautiful formula

l(Sn) = ⌈3n/2⌉−b(n)−1

for the length of the symmetric group Sn, where b(n) is the number of ones in the base 2 expansion of n. This result depends on the classification of finite simple groups, but only rather weakly; I seem to remember that, at the time (early 1980s), I observed that using Babai’s “elementary” bound for the order of a primitive permutation group, the formula can be proved for all n greater than about 1000.

The depth of a group is the length of the shortest unrefinable chain of subgroups. There are some very appealing arguments concerning depth; for example, the proof that there is an absolute bound for the depth of Sn uses the proof by Helfgott of the ternary Goldbach conjecture. However, what I didn’t see was any application of depth comparable to the several applications of length. (If the depths of symmetric groups are bounded, it is not a very good measure of their size, methinks.)

Anyway, tomorrow we head back to Scotland and go to ground. There were several projects I had hoped to get finished here, and we have at least pushed them on a bit; also the two things from my February trips that I talked about earlier.

Posted in doing mathematics, symmetric group | Leave a comment

Research trips in February

I don’t know how things have got so busy. I had two interesting trips in February; I worked hard, and some interesting mathematics resulted; but I don’t seem to have found the time to describe it. So here goes. This is, by a long way, not all that I managed to do, just a little sample from each trip.

Firenze

I was meant to be in Firenze, working with Carlo Casolo and Francesco Matucci, from 10 to 14 February. Unfortunately Storm Ciara had other ideas, and my flight out was cancelled; I had to re-book on a flight the next day. So our work on the first day was briefer than intended.

We were working on integrals of groups. We call the group H an integral of the group G if the derived subgroup of H is isomorphic to G. When João Araújo and Francesco invited me to work on this topic, my first thought was that it was a linguistic joke, or possibly just light relief from the hard stuff. But we recruited Carlo to the team, and published a 30-page paper in the Israel Journal of Mathematics, which I described here.

So this visit was to work on the follow-up. It was not entirely clear what this should be: other topics in “inverse group theory”, or further results on integrals? It turned out to be the latter. Here is one of the results, a three-part theorem to which we all contributed, but Carlo was certainly in the driving seat. The context is the question: if G belongs to a certain class of groups, and G has an integral, does it have an integral in that class? This is what we did, for the class of profinite groups.

  • Let G be a profinite group which has an integral H such that G has finite index in H. Then G has a profinite integral.
  • Let G be a finitely generated profinite group which has an integral. Then G has a profinite integral.
  • There is a profinite group which has an integral but has no profinite integral.

So things can be very interesting!

I had never been to Firenze before, but we were so busy that I onlly got to see the Duomo at night. But above is a picture of it; I have a new camera which is better in low light than my old one.

Mire de Aire

Two weeks later I was off to Portugal. The intention had been to work on the Road Closure Conjecture with João and Pablo Spiga. But the coronavirus had other ideas, and Pablo wasn’t able to make it. So João and I thought about complete mappings instead. These are usually defined on quasigroups (they are essentially the same thing as transversals of Latin squares), and especially groups; but I was now in semigroup land, so what about complete mappings of semigroups?

I should mention that the post linked above concerns the Hall–Paige conjecture, now proved (using the Classification of Finite Simple Groups): a finite group has a complete mapping if and only if either it has odd order or its Sylow 2-subgroups are cyclic.

A complete mapping on a multiplicative structure S is a bijection f from S to itself such that the map g given by g(x) = x·f(x) is also a bijection. (At least for groups, g is called an orthomorphism. João had already convinced himself that the critical case for the theory consists of Rees matrix semigroups together with their variants with a zero element.

I’m not going to give a definition here. Suffice to say that such a semigroup is defined by a group G and a rectangular matrix P with entries from G, which can be assumed to be normalised (that is, all entries in the first row and column are the identity of G).

With a combination of computer experiment and hand calculation we came up with a conjecture:

A Rees matrix semigroup defined by a group G and normalised matrix P has a complete mapping if and only if one of the following holds:

  • the group G has a complete mapping;
  • the number of entries in P is even;
  • some entry in P is a non-square.

We were able to show that the disjunction of the three conditions is necessary; the first two are sufficient, and the third is sufficient if the group has twice odd order.

I was planning to talk about this at the NBSAN meeting in Hull next Friday (20 March), but things are changing so fast that I am more than half expecting the meeting to be cancelled. If so, this is part of what you missed!

Again, we were busy all week, but I had one extra day, and João took me to Mira de Aire, the largest caves in Portugal, with one gallery 11 kilometres long (we didn’t get to see it all). We saw much more during the day, including a fossil of a Jurassic starfish:

Jurassic starfish

Posted in doing mathematics, exposition, geography | Tagged , , , , , | 3 Comments

Hadamard on impact

In his book on how mathematicians think, which I have discussed here, Hadamard devotes a chapter to inquiring how mathematicians choose the topic to work on. He starts with Claparède’s view that there are two kinds of invention: one is given a goal, and looks for a means to reach it; the other discovers a fact and then imagines what it might be useful for.

He is of the opinion that many scientists, especially mathematicians, use the second method. Some of his examples are very relevant to the vexed question of impact. Here are a few.

About 2400 years ago, the Greek mathematicians investigated the properties of ellipses; “they did not think and could not think of any possible use” for their discoveries. But, if they had not done so, Kepler could not have formulated the laws of planetary motion, and Newton could not have formulated the law of universal gravitation.

Balloons, in the early days, tended to be filled with light but flammable gas such as hydrogen. Now we have light non-flammable gas. “This progress has been possible for two reasons: in the first place, because one has succeeded in knowing which substances exist in the atmosphere of the Sun and which do not; secondly, because research was started, by Lord Rayleigh and Ramsay among others, to determine the density of nitrogen” to four significant figures rather than three. (An unknown element was identified in the Sun’s atmosphere by spectroscopy, and was named helium. Meanwhile, chemists doing accurate measurements found a discrepancy between the density of nitrogen produced by chemical reaction and nitrogen obtained by removing the other known constituents of air; they discovered by careful analysis the inert gases, the lightest of which was identified with the element found in the Sun’s atmosphere.)

Elie Cartan’s work on group theory in 1913 was applied fifteen years later to the theory of the electron.

Bernoulli invented “calculus of variations”, but Volterra and others did the job more wholeheartedly, producing a calculus in which functions took the place of numbers and “functionals” operated on them. This seemed an aesthetic but impractial construction, until it turned out to play a fundamental role in quantum mechanics.

One of Hadamard’s own results (on determinants) was later fundamental in Fredholm’s work.

He also mentions in passing the descovery of imaginary numbers, which he attributes to Cardan, the Renaissance doctor, mathematician, and generally extraordinary character who gave the world the solution to the cubic.

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

GRA workshop 2

This workshop was on “Computational and algorithmic aspects” (of groups, representations and applications, presumably). In my opinion, this was the week when the programme really took off.

There were many good talks, so as ever I shall just select a few. First, two contrasting styles to actually use the computer to solve problems.

Richard Parker gave a talk on “10 years of meataxe development”, the Meataxe being Richard’s program for decomposing modules. He described it as “a rant”; he works very close to the metal in an attempt to squeeze more speed out of the hardware. He said (and this echoed comments at our Big Data symposium a few years ago) that data movement is more expensive than actually doing the work. (So, of the three Rs, arithmetic is cheap and quick, while reading and writing are much slower and more expensive.) He claimed that programmers mostly ignore modern hardware design. Typically there are three levels of cache with very differing speeds well above RAM access, and if you don’t use them you are taking a factor of hundreds longer than you need. But things are not made easier by the lack of user-friendly assemblers for today’s very complex chips. His wish list was a scheduler, a more friendly assembler, and a solution to the synchronization problem.

At the other end was Nicolas Thiéry. He has a new PhD student, who is going to work on representation theory of semigroups. The software he needs is scattered over many different systems (GAP, Magma, Singular, many others); with some effort he can call everything he needs from Sage, but it is considerably harder than it should be because of differing formats. This is a software engineering problem.

But there was much more to Nicolas’ talk. He was much more concerned to give us insight and motivation than to write down detailed definitions. What is the difference between groups and semigroups? He explained, rather briefly, the J-classes of a semigroup, and how these might be structured round a group. Why do you want to do representation theory of semigroups? Group theory has been applied to the analysis of Markov chains by Diaconis and others; but in this imperfect world, things mightn’t be reversible, and semigroups are like groups where the operations can’t always be reversed. (His picture of a group is a perfect circle.) His example was the Tsetlin library, rephrased in more homely terms: you pull the shirt you want out of the pile, and when it is washed it is put back on top.

I took away the impression that moving from groups to semigroups is not unlike moving from ordinary to modular representation theory of finite groups: things are no longer completely reducible, and you have to deal with the radical.

There was a surprising amount of algebraic geometry; some of it I found very interesting. I’ll mention two. Mohammed Barakat talked about “Chevalley’s Theorem on constructible images made constructive”. In a topological space, a set is locally closed if it is the intersection of an open set and a closed set, and is constructible if it is a finite union of locally closed sets. Chevalley’s theorem says that the image of a rational map of affine varieties is constructible (in the Zariski topology). If this sounds hard, his simple example made it clear. We take the map between two-dimensional affine spaces taking the point (x,y) to x,xy). The image of this map is the whole plane with the Y-axis removed and the origin put back, obviously a constructible set. He has a new proof of this which produces a kind of canonical decomposition into locally closed sets, and which can be implemented on a computer, not just over a field but over rings like the integers too. There were several nice applications.

Tobias Rossman took us on an absolute roller-coaster ride connecting group theory, combinatorics, graph theory, and algebraic geometry. To cut to the chase, given a finite graph Γ, he defines a group scheme GΓ where you have a generator for each vertex, two generators commute if the vertices are non-adjacent (I am not certain I have this right), and commutators are central (so the group is nilpotent of class at most 2). The object of interest is the number of conjugacy classes of this group, over some given field or ring. This has a zeta-function with an Euler product, and the factors are bivariate rational functions of p and p-s. For some special graphs (a subclass of the cographs or N-free graphs), these are simple combinations of translates of the Riemann zeta function. The proof covers a huge amount of ground (as proofs in this area tend to do, in my experience).

Joanna Fawcett and Melissa Lee gave us an update on the base size 2 project: which primitive groups have a base of size 2, or perhaps easier, which ones don’t? (The base size is the minimal number of points whose pointwise stabiliser is the identity.) There is a nice graph, the Saxl graph, associated with groups of base size 2: very simply, the edges are the bases. This is conjectured to have nice properties resembling those of the generating graph of a finite simple group.

Madeleine Whybrow talked about dihedral axial algebras. It would take a while to explain this, but let’s say that the Griess algebra for the Monster is the motiviating example of an axial algebra, though others arise in Jordan algebras. There are now quite simple axioms for axial algebras, though it has taken a while to reach this point, and (the point of the talk) good computational tools to explore them. “Dihedral” just means “two generators”. One can put in values for various numbers that occur in the multiplication table of the idempotents. What has emerged is that the values that occur in the Griess algebra (1, 1/4 and 1/32), which seemed rather artificial at first, really are the sweet spot.

Finally, a lovely talk by Eilidh McKemmie on invariable generation. A group is invariably generated by a set of elements if you can replace any of them by arbitrary conjugates and still have a generating set. It is a result due to Pemantle, Peres and Rivin in one direction and Eberhard, Ford and Green in the other, that four random elements invariably generate the symmetric group Sn with probability bounded away from zero, but three random elements do not. Eilidh has proved that exactly the same holds in classical groups. (There is a slight complication here: classical groups have two parameters, and we may take them to infinity in either order or together, but I will skip over this.)

All rather exciting and exhausting!

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

Prophecy

Once we had a country and thought it so fair
If you look through the mirror you still find it there
But now our great country is broken and torn
And all of its promise and liberties worn

Procol Harum, “An Old English Dream”

In 2003 Procol Harum released their 11th album, The Well’s On Fire. That name, with hindsight, has a prophetic ring to it. I didn’t listen to this until several years later, at which time it was clear to me that two songs on the album, “The Blink of an Eye” and “Wall Street Blues”, could be read as foreseeing the global financial crisis of 2008.

Meanwhile I hadn’t noticed the prophetic nature of the verse from the opening track, quoted above.

Posted in Uncategorized | Leave a comment

Birthday card

Birthday card

This year’s birthday card sets the scene for the year that follows. Apologies if you find me unusually full of grumbles this year.

Posted in Uncategorized | Leave a comment