Richard and Edward

Did I detect just a small amount of provocation at NBSAN when Vicky Gould (from York) said to Rick Thomas (from Leicester), “You got our king”?

Of course, this refers to Richard III, whose bones (as you most likely know) were found under a car park in Leicester, near the battle of Bosworth where he was killed, and were recently reburied with great pomp in the cathedral in Leicester. The city of York had competed for the king’s bones, on the grounds that he was a Yorkist and that was his home town.

Quite by chance, the evening after the meeting I read on the web about the earlier English king Edward the Martyr. His story has something in common with Richard’s, as well as with other topical things such as “Wolf Hall” and “Game of Thrones”.

Edward was the eldest son of king Edgar the Peaceful, and was crowned king of England in 975 at the age of 13, and was murdered three years later. Subsequently, he was recognised as a saint in the Anglican, Roman Catholic, and Eastern Orthodox churches (maybe one of the few things these three organisations can agree on). Reading what little is known about his life, one gets little impression of saintliness. Moreover, he was not murdered by pagan Vikings, or even by the anti-clerical party in Wessex. Historians have several theories about why he was murdered, but maybe the favourite is that it was a power struggle between his supporters and those of his younger brother Ethelred (the Unready).

I knew very little about this period. I had of course heard of Ethelred the Unready (his appelative is mis-translated from the Old English word which actually means “ill-advised”). But I did note that, when I read the Wikipedia page, it noted that it was last edited on 1 April, so it might be as fictional as Game of Thrones.

Edward’s bones were not lost, but were actually kept in a bank vault for some time because of a legal battle over their ownership between the archaeologist who found them (who wanted them to go to the Russian Orthodox Church Outside Russia) and his brother (who wanted them returned to Shaftesbury Abbey where they had been found). The Russians were victorious, and Edward was reburied at Brookwood in Surrey, where there is now an Orthodox foundation including a small monastery and a parish church.

This happened in 1984, well within my lifetime, and yet I don’t recall hearing anything about it. So the reburial of someone revered as a saint in most of Christendom can pass unnoticed, while the reburial of someone who was perhaps a murderer and usurper is a national event. Why? Maybe Richard had the better writer for his life story …

I happened to be reading this on St George’s Day, and it struck me that St George’s connection with England is as tenuous as St Edward’s with Russia or Greece.

Brookwood is itself an interesting place. I have passed it on the train many times; it is at the junction of the line to Basingstoke and the south-west and the line to Aldershot. The cemetery there is one of the largest in Europe, with over 235000 inhabitants. It was created by the London Necropolis Company to offer an alternative to London’s overcrowded burial grounds. The company had their own station (London Necropolis) near Waterloo, and offered three classes of burial (as befitted a class-conscious society like Britain), though most of the burials were third-class. It also re-buried inhabitants of London graveyards whose rest had been disturbed by the building of London’s sewers and underground railways. The main divisions of the cemetery were Anglican and Nonconformist, each with their own station, but it also included several smaller divisions including Parsee (I thought that Parsees practiced air burial, but maybe there are not enough vultures in Surrey), Turkish, and American. The cemetery itself was the subject of a legal battle before ending up in the care of Woking council.

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

NBSAN in St Andrews

This week, during a spell of lovely spring weather and new blossom, the 20th meeting of the North British Semigroups and Applications Network was held in St Andrews, organised by Markus Pfeiffer.

Kinness Burn

It was good to see old friends such as Rick and Hilary Thomas, Vicky Gould, John Fountain, John Meldrum, and Mark Kambites.

I’ll just discuss here a few talks which for me were highlights.

First among these was Bob Gray’s opening talk of the meeting, entitled “Crystal monoids”. It was mostly about the plactic monoid, and fortunately (since that word is not in my dictionary – it is “plaxique” in French, but this is not clear either – a correspondent on MathOverflow derives it from Greek “plax”, plaque, which could perhaps be linked with “tableau”) he spent most of the talk telling us what this monoid is, taking us on his journey of “learning new things”. He gave us three completely different descriptions of it:

  • The first description was in terms of generators and relations. The plactic monoid Pn is generated by n elements, which are ordered (and which we can take to be 1,2,…,n), satisfying the Knuth relations: if x < y < z, then zxy = xzy and yzx = yxz; and if x < y, then xyx = xxy and xyy = yxy.
  • A description using the Robinson–Schensted–Knuth insertion rule for semi-standard tableaux (see below);
  • A description using Kashiwara’s notion of crystal graphs, crystal bases, and Kashiwara operators, which I won’t even attempt to describe here.

The next post in my series on the symmetric group was always intended to be about Young diagrams and tableaux and their connection to the representation theory of the symmetric group. I still intend to do this sometime, but it hasn’t been done yet. If it had, I could have referred you to it for the procedure of inserting an element into a tableau, except for one thing: there are several conventions about tableaux, and even Bob and his co-author Alan Cain couldn’t agree! Indeed, Ian Macdonald, in his great book on Symmetric functions and Hall polynomials, says, after explaining the British and French conventions for tableaux, that Francophone readers of his book should read it upside-down in a mirror!

Here is a brief account, in the form that Bob Gray used. A Young diagram is a collection of boxes aligned at the top and the left, so that row lengths are weakly decreasing going from top to bottom. A semi-standard tableau is obtained by putting numbers from the set {1,2,…,n} into the boxes so that rows are weakly increasing from left to right and columns are strictly increasing from top to bottom.

To insert a number x into a tableau: first, try to put it at the end of the first column. If it is strictly larger than the last entry in the first column, this is fine, and we can add the number in a new box and stop. Otherwise, we go up the column until we find the first number y which is not greater than x; x “bumps” y out of its box, and we then (recursively) insert y into the tableau consisting of the remaining columns.

(If you compare this with the version in my Combinatorics book, there are three differences: first, I insert elements into rows rather than columns; secondly, I assume that the numbers are all distinct, so that the tableaux are standard (rows and columns both strictly increasing); and third, I maintain a second tableau to record the boxes in order of creation. This gives rise to a bijection between permutations and pairs of standard tableaux of the same shape.)

Now there is an equivalence relation defined on words over the alphabet {1,2,…,n}: two words are equivalent if, when we successively insert them into the empty tableau, the results are equal. This equivalence relation turns out to be a congruence on the free monoid generated by the alphabet (the set of all words with the operation of concatenation), and so the quotient is a monoid. This is the plactic monoid.

One can recover a word from a tableau by reading it “Japanese fashion”: down each column, and columns from right to left. This word belongs to the congruence class corresponding to the tableau, and can be regarded as a “canonical representative” (though there are other possible choices for this).

The results of Cain, Gray and Malheiro (which he had little time to describe) are that the plactic monoid has a finite complete rewriting system and an automatic structure. He did explain these terms, but for me the most valuable thing was, as I said, the three descriptions of the monoid.

Later the first afternoon, Alan Cain spoke further about this work. They have done similar things for several other monoids.

The essential idea is to take any combinatorial structures with a notion of “insertion”. As well as semistandard tableaux (giving the plactic monoid), they have considered the hypoplactic monoids (from “quasi-ribbon tableaux”), the sylvester monoids (from binary search trees), and a couple of others. (Alan insisted on the lower-case letter here since sylvester does not commemorate the mathematician of that name but the association with trees. My dictionary doesn’t give it as a word but does list “sylvestrian” as the adjectival form.)

After the conference dinner in the newly-reopened Byre Theatre, I walked home along the Kinness Burn where I heard a thrush singing a magnificent song, and saw a couple of bats flying over the river in the twilight, while a crescent moon and Venus hung in the western sky.

The next day, the opening talk was by Paul Bell. He tried so hard to give us careful background explanations that he ran a bit short of time; but better that way, in my view. He was talking about decidability and complexity of problems about matrix semigroups. He gave us clear accounts of the undecidable problems which he and his coauthors have coded into matrix semigroups for the negative results.

One of these was the Post Correspondence Problem PCP(k). We are given k dominoes, aligned vertically. On the top and bottom halves of each domino are written words over the two-letter alphabet {a,b}. (There are an unlimited number of copies of each domino available.) The task is to choose a sequence of dominoes and put them in a row such that, when the words on the top parts of the dominoes are read and concatenated in order, and the same for the bottom parts, the results are equal. This problem is known to be decidable for k = 2, and undecidable for k = 5.

Another problem used in this way was Hilbert’s 10th (solvability of Diophantine equations). For NP-completeness he used the subset sum problem.

Matthew Taylor introduced us to the tropical semiring T, whose elements are the real numbers together with −∞; addition is the maximum function, and multiplication in T is addition in R. The assertion that the tropicalisation of schemes (from algebraic geometry) is quotients of free T-modules in finitely many variables (proved a couple of years ago by the Giansiracusa brothers), he embarked on the classification of 2-generated T-modules, involving lots of pictures of plane configurations involving horizontal, vertical and diagonal lines, as you might expect.

And why is it called “tropical”? Not, as I first thought, to contrast it with “polar geometry”; but in honour of one of the pioneers, the Brazilian mathematician Imre Simon, though there seems to be some disagreement about who actually coined the term (and in any case São Paulo, where he worked, is barely tropical, lying 23 1/2 degrees south of the equator).

A very nice conference, crossing many boundaries, and with some excellent expositions.

I concluded the conference with a talk entitled “Finding where you are”, involving two aspects of synchronization for automata, both of which I have discussed here before. (Perhaps appropriate: we were in the third lecture room that had been used for the meeting.) My slides are in the usual place.

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

The Borders

Twelve years ago, I spent a very enjoyable four days on St Cuthbert’s Way, a long-distance walk crossing the border between England and Scotland.

The walk officially goes from Melrose (where Cuthbert was prior of the abbey) to Holy Island (where he was bishop of Northumbria). In fact the causeway to Holy Island is only passable at low tide, which dictated that we had to do the walk in the reverse direction, leaving Holy Island not by the causeway but by the Pilgrims’ Way across the sand (marked by tall poles). The border is crossed near Kirk Yetholm, about the halfway point of the route, which is also the northern terminus of the Pennine Way.

St Cuthbert lived in the 7th century, but most of the architectural remains date from half a millennium or more later. But Melrose is even older; it was the Roman town of Trimontium, and if you see the three peaks of the Eildon Hills lined up above the town, you understand where the name came from. (The name Melrose is British, as are many Scottish placenames, especially in the Borders.) The hills form a barrier which the path has to cross, but it uses a pass between the eastern and middle summit and so avoids quite a climb.

Incidentally, Trimontium is one of a very few Roman place-names which are known for Britain. It was such a remote outpost of empire that not much detail was recorded.

The town of Melrose is on the river Tweed, just east of Galashiels and Tweedbank. In September, it is planned that Scotland’s newest railway, the Borders Railway (actually a rebuild of 30 miles of the 100 mile Waverley Line from Edinburgh to Carlisle, closed in 1969) will open, from Edinburgh to Tweedbank. This will make this lovely walking country more accessible.

The line will pass through Newcraighall, which currently is the terminus of the Fife Circle(!). Presumably turning the trains there saves the need to park them in the rather cramped Edinburgh Waverley station. I have no idea whether they plan that Fife Circle trains will continue to Tweedbank. But the Fife Circle doesn’t come very far north, so either way will involve a change.

I was looking up the Waverley Line on Wikipedia yesterday. Their account of the modern rebuilding is a must-read. The things that went wrong are not on the scale of the infamous Edinburgh Tram, but the list of delays and cost increases suggests that once the original decision had been taken (by 114 votes to 1 in the Scottish parliament), nobody bothered to keep a watch on what was going on.

Politics alert: If the SNP can screw up a simple job like this so badly, can they really be trusted to run a country?

Posted in history, maybe politics, geography | Tagged , , , , | Leave a comment

Breaking boundaries

Breaking boundaries

As well as the PCC, last week I was at a conference at the University of Sussex entitled Breaking Boundaries between Analysis, Geometry and Topology. With a title like that, how could I resist?

There were some lovely and wide-ranging talks. Here is a whistle-stop tour.

David Edmunds made some “Remarks on Approximation Numbers”. These numbers, for maps on Banach spaces, turned out to be a kind of generalisation of eigenvalues in the positive self-adjoint case, so interesting even if I don’t expect to have an immediate use for them myself. He remarked at one point that nuclear operators are sometimes called “operators of trace class”, even though they may not actually have a trace!

David Applebaum talked about “Generalised spherical functions on groups and symmetric spaces”. This was a blend of harmonic analysis and probability theory, bringing in, among other things, the Lévy–Khintchine formula for the Fourier transform of an infinitely divisible element (one which has a convolution nth root for any n with the Harish-Chandra formula. Lévy–Khintchine works on Euclidean space, and can be extended to locally compact abelian groups, but to go further to non-abelian groups and symmetric spaces you have a much harder job, and they ended up with a formulation involving infinite matrices, but still in the spirit of the original!

Dale Rolfsen gave two talks, on the theme of generalised torsion in groups. A group has generalised torsion if the product of some n conjugates of a non-identity element is equal to the identity (this reduces to ordinary torsion if the conjugating elements are all the identity). It is known that “biorderable” (having an order invariant under both left and right translation) implies “locally indicable”, which implies “left-orderable” (a left-translation-invariant order). In addition, “biorderable” implies “no generalised torsion”. In the first talk he concentrated on knot groups: if all the roots of the Alexander polynomial of a knot are real and positive, then the knot group is biorderable; but the Alexander polynomial does not detect generalised torsion. The second talk was about generalised torsion in homeomorphism groups of manifolds (especially cubes) which fix the boundary pointwise, and involved some ingenious constructions moving cubes around.

Michiel van den Berg talked about heat flow in Riemannian manifolds. You start with a region Ω at unit temperature, with either the rest of the manifold at zero temperature, or the boundary of Ω fixed at zero temperature; you are interested in how much heat remains in Ω at arbitrary later time, and in particular its asymptotics.

Neils Jacob talked about “Symbol and geometry related to Lévy processes”. From a function of two variables, you can define a pseudo-differential operator (where the second variable is “replaced” by differentiation) by means of the Fourier transform. The talk took me back to the course on partial differential equations I took as a final-year undergraduate, with lots of stuff about the geometry of wavefronts and characteristic manifolds. I regret to say that I didn’t understand much back then, and didn’t really get much further this time!

Roger Fenn presented us with a challenge. Take Gauss’ encoding of a knot, and turn it into a nice drawing of the knot; not a job just for computers since aesthetic considerations are involved.

I also gave two talks, one about the ADE affair (which I have discussed at length on this blog, beginning here), and the other about recent work with Collin Bleak on the outer automorphism groups of the Higman–Thompson groups, in which we have to count foldings of de Bruijn graphs, which I also posted about recently here. The slides are in the usual place.

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

Postgraduate Combinatorial Conference 2015

This week I was at the Postgraduate Combinatorial Conference, which was held in Queen Mary, University of London.

It was one of the liveliest PCCs I have been to, with about 35 delegates from all over England, Scotland, and further afield (Reykjavik, Wien). Several of my St Andrews students from last year were there, all doing well. I didn’t attend many of the student talks – I regard them as the students’ affairs and I don’t want to sit in the back looking intimidating – but I had talks about mathematics (and other things) with quite a few delegates.

I did go to Julia Wolf’s talk, in which she predicted that Sidorenko’s conjecture (stating, roughly, that for any bipartite graph H, the number of copies of H in a large graph G is at least as great as in the random graph with the same edge density as G) will be resolved soon, one way or the other.

The weather was lovely – I did go for a walk in the park at one point – and the College catering had done a superb job, with good lunches and dinners and cakes at coffee time.

I gave a talk (you can find the slides in the usual place), and put in a couple of plugs: for Jack Edmonds’ lectures, and for my talk at the Permutation Patterns conference, both taking place in June.

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

Generating singular maps

Last week, Max Gadouleau and Alonso Castillo-Ramirez visited St Andrews. With James Mitchell, we worked on a problem about generating the semigroup of singular maps on a set (the full transformation semigroup minus the symmetric group). As usual in this situation, I want to write about the background, just to make sure I understand it!

Introduction

Let Singn be the semigroup of singular maps on the set {1,…n}. The first thing to note is that maps of rank n−1 cannot be generated by maps of smaller rank; so a generating set for the whole semigroup must yield all the maps of maximum rank. But it is not hard to see that the maps of rank n−1 do indeed generate the whole semigroup. So, if we are looking for a minimal generating set, we can concentrate on these.

The situation is still too complicated, so we will concentrate on idempotents of rank n−1 (that is, maps f satisfying f2 = f. Such a map only moves one point, say a; everything else (including the image of a) is fixed. So, if the image of a is b, we can write the map as ab (a directed arc from a to b).

Now think about how these maps compose. If we compose a sequence

a1a2→…→ak,

from left to right, then all the elements in the sequence pile up on ak. Interesting, but not what we want if we are trying to generate maps of rank n−1.

In fact, if we insist on producing maps of maximum rank, then after the first move we have in effect a sliding block puzzle. Apply the transformation ab. This leaves a “hole” in position a, into which we can now move another element; the tail of its arrow will then be the hole, and so on. Thus, we compose the arrows in the reverse of the natural order.

Tournaments and idempotent generators

A tournament is a directed graph in which, between any two vertices, there is an arc in one direction (only). Think of this graph as recording the result of a tournament in which any two teams play once, and an arrow ab indicates that a beats b.

A tournament is strongly connected (or just strong) if there is a directed path between any two of its points.

I will use two facts about tournaments, which I will explain at the end. In what follows, only the first of these is used; but the second is useful in similar arguments.

  • Any tournament has a Hamiltonian path (a path including all vertices).
  • A strongly connected tournament has a Hamiltonian cycle (a cycle including all vertices).

The theorem (I am not sure who proved it) is the following.

Theorem: A set of rank n−1 idempotents is a minimal generating set for Singn if and only if the corresponding arcs form a strongly connected tournament.

What follows is not a detailed proof, but an explanation of this theorem. I will only describe one direction, that the arcs of a strongly connected tournament do give a minimal generating set.

As explained earlier, our task is to show that we can generate any map of rank n−1. This is an easy sliding-block puzzle if we can show that we can generate all of the idempotents. For example, to swap a and b, move a into the hole, b into the hole left by a, and then a from the original hole to the position vacated by b.

So, if ab is in our set, we have to be able to generate ba.

For this, take a directed path from b to a (this exists, by strong connectedness), and compose its elements (in the “wrong order”, as explained). The result is a map of rank n−1 which has the correct kernel and image but may not be an idempotent. But some power of it will indeed be an idempotent, so we are done!

This also explains why, in a minimal generating set, we don’t need arcs in both directions between two points. Why do we need a tournament rather than a digraph with fewer edges? If we compose a sequence of maps of rank n−1 and the result still has rank n−1, then its kernel is equal to the kernel of the first map in the sequence. So each possible kernel must be present among the generators. The kernel of a rank n−1 map is a partition with one part of size 2 and the rest singletons; so every 2-set must occur as a kernel, that is, every pair must carry an arc in one direction at least.

Now, to generate an arbitrary map f, we can use the following strategy. First, we produce a map with the right kernel classes. Take each kernel class. It induces a sub-tournament, which by one of our earlier facts contains a Hamiltonian path. Pushing forward along this path, we pile up all the elements on a single one. Once we have done this for all kernel classes (this requires nr steps, where r is the rank), we simply have to move these piles of counters to their correct final positions.

I haven’t even got to the point where we started our work; but I think I understand the background a bit better now!

Two facts about tournaments

1. Let T be any tournament, and take a path in T of maximum length, say v1→…→vk. If there is a vertex w not on this path, there are three possibilities:

  • wv1. Then we get a longer path by adding w at the beginning.
  • vkw. Then we get a longer path by adding w at the end.
  • If neither of these hold, let i be minimal such that wvi. Then i > 1, and so vi−1w; so we may replace the arc vi−1vi by a diversion via w.

2. Let T be a strongly connected tournament, and take a cycle C in T of maximum length. If there is a point w not on the cycle, there are two possibilities:

  • There are arcs in both directions between w and C. Somewhere, an arc from C to w is followed by an arc from w to the next point. Then we may extend C with a detour.
  • This never happens. Then every point outside C either dominates or is dominated by C. If there were an arc from a point dominated by C to a point dominating C, we could find a longer cycle. Otherwise, the strong connectedness is contradicted. I leave the details as an exercise.

Here is a nice application of the second fact.

Proposition: Given a minimal generating set of idempotents for Singn as described above, any rank 1 map can be written as a product of n−1 generators (and no fewer).

At least n−1 generators are required, since each one reduces the rank by at most 1. To achieve this, choose a Hamiltonian cycle in the tournament. Starting one step after the position of the image of the required map, move around the cycle until this position is reached.

Posted in exposition | Tagged , , , , | 2 Comments

Jack Edmonds: the London gigs

Jack Edmonds is a larger-than-life figure in the world of combinatorial optimization and polyhedral combinatorics. If you are a student, you really should grasp this chance to meet him!

with Jack Edmonds

More than fifty years ago, Jack was perhaps the first person to make a clear distinction of “easy” (polynomial time) and “hard” problems, and “easily certifiable” answers, now formalised as P and NP. The concepts of P, NP, and co-NP together with discussion and conjectures are clear in Jack’s papers from the mid-1960s, including the conjecture that there is no polynomial time algorithm for the travelling salesman problem (TSP).

In the early 1970s, Stephen Cook, Leonid Levin, and Richard Karp, showed that various familiar NP problems, including the TSP, are as hard as any NP problem, that is, “NP-complete”. Since then, using the assumption of the non-easiness of TSP, that is, NP ≠ P, and trying to prove or disprove it, have become a staple of the fields of combinatorial optimization and computational complexity.

Jack is known for many other important results such as the “blossom algorithm” for maximum matching, the matroid intersection theorem, “the greedy algorithm”, theory of polymatroids and submodularity (f(AB)+f(AB) ≤ f(A)+f(B)), and much more. He is still creative, with recent work on Euler complexes and Nash equilibria among other things, and he loves to perform.

So I am delighted to have had a small part in setting up two short courses by Jack in London in June, aimed at students:

  • At Queen Mary, University of London, 16-19 June: Combinatorial structure of paths, network flows, marriage, routes for Chinese postmen, traveling salesmen, and itinerant preachers, optimum systems of trees and branchings. (Contact: Alex Fink)
  • At the London Taught Course Centre, 22-23 June (an LTCC Intensive): Combinatorial structure of submodularity, matroids, learning, transferable & other n-person games, bimatrix games and Nash equilibria. (Contact: Nisha Jones)

Further details will be available from the web page.

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