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

A paper on synchronization

A paper on synchronization, written with João Araújo, Wolfram Bentz, Gordon Royle and Artur Schaefer, has just appeared on the arXiv.

It is quite a substantial paper, and goes well beyond anything we have published (or that I have written about here before). So I cannot describe it all. Here is what I think is the most dramatic new idea.

By way of recap: a permutation group G, acting on a set X, is said to synchronize a map f if the monoid generated by G and f contains an element mapping everything to a single point. Then G is said to be a synchronizing group if it synchronizes every non-permutation, and an almost synchronizing group if it synchronizes every non-permutation which is uniform in the sense that the sizes of the inverse images of all points in its range are the same.

A more “classical” notion: G is primitive if it preserves no non-trivial equivalence relation on X, that is, there is no partition of X whose parts are permuted by G other than the partition into singletons and the partition with a single part.

There is a connection between these concepts. It is known that any synchronizing group is primitive (as, indeed, is any almost synchronizing group). A theorem of Rystsov shows that a permutation group of degree n is primitive if and only if it synchronizes every map of rank n−1 (that is, a map which collapses two points to the same place and is injective on the remaining points). Indeed, the largest part of our paper is to push down this bound: with long and delicate arguments, we show that a primitive group of degree n synchronizes any map of rank n−4 or greater.

It was conjectured for a while that, conversely, a primitive group is almost synchronizing. I described here how we refuted this conjecture last year. Our new examples go much further.

The most powerful tool for examining this problem is the use of graphs and graph endomorphisms. A transformation monoid M fails to be synchronizing if and only if there is a simple graph X (that is, undirected and without loops or multiple edges) whose endomorphism monoid contains M; moreover, we can assume that X has clique number equal to its chromatic number, and that every edge is contained in a maximal clique.

Now the new idea for constructing graphs with a rich supply of endomorphisms uses the notion of the Cartesian product XY of graphs X and Y. Its vertex set is the Cartesian product of the vertex sets of X and Y (that is, the set of ordered pairs (x,y), where xX and yY; edges join pairs (x1,y1) and (x2,y2) whenever x1 = x2 and y1 and y2 are joined in Y, or vice versa (X components joined, Y components equal). Thus, for example, if Kk is the complete graph on k vertices, then KkKk is the k×k square lattice graph L2(k), the line graph of the complete bipartite graph on k+k vertices.

The picture shows L2(4) with a proper vertex colouring (aka a Latin square of order 4). The rows and columns are cliques.

Latin square

Now

  • if X has primitive automorphism group, so does XX (the wreath product of Aut(X) with the cyclic group of order 2, in the product action);
  • if X has clique number and chromatic number k, then it has a surjective homomorphism to Kk, and so XX has a surjective homomorphism to KkKk = L2(k).

So, if there is a homomorphism from L2(k) to X, then the composite

XX → L2(k) → X → XX

is an endomorphism of XX. (The last map sends X to the set of vertices of XX with fixed second coordinate.) The first and third homomorphisms are uniform, but the middle one gives us the chance to introduce non-uniformity.

This trick works rather well when the graph X is the complement of L2(k). (That is, vertices of the square grid are joined if they lie in different rows and different columns; X is the categorical product Kk×Kk.) This graph has clique number k (a diagonal of the square grid is a clique in the complement) and chromatic number k (give a colour to each row of the grid).

Our ingredient is a homomorphism from L2(k) to its complement. Such a map has the form (x,y) → (f(x,y),g(x,y)), and the homomorphism condition is equivalent to saying that each of f and g should be a Latin square (but with no relation between the two). Thus the image is given by the superposition of two Latin squares.

The rank of such a superposition is the number of different ordered pairs of entries which arise. Clearly it is between k and k2, the lower bound realised when the squares are identical and the upper bound when they are orthogonal. This rank is equal to the rank of the resulting endomorphism of XX. So we would like to know which ranks are possible for the superposition of two Latin squares.

Fortunately, this problem has already been solved by Colbourn, Zhu and Zhang, who have determined all the possible ranks. For k > 6, every value in the interval from k to k2 except k+1 and k2−1 occurs; all the exceptions for lower values of k have been determined.

So we have primitive graphs with k4 vertices, and with endomorphisms of k2k−1 different ranks, almost all of them non-uniform!

We have other examples too, but have not explored the new realms opened up by this idea. The conclusion is that things are much more complicated and interesting than anyone thought.

Posted in exposition | Tagged , , | Leave a comment

Open access and the REF, 2

Bob Dylan said,

When you think that you’ve lost everything,
You find out you can always lose a little more.

Open access for the REF is not in that league, but when you think you have plumbed the depths of HEFCE policy on open access, someone pops up to tell you that you haven’t got to the bottom yet.

I am going to tell you two entirely realistic scenarios which could lead to papers being judged ineligible for the REF despite your best intentions, or at least to a degrading of the quality of research in the name of “excellence”. But a couple of preliminary remarks first.

Recall that you must put a preprint of your article (in the final accepted form for publication) in a public archive within three months of acceptance, from 1 April 2016. (Incidentally, it is not entirely clear that this start date refers to acceptance of papers. We know how slow mathematical publication is, and it is quite possible that a paper accepted years earlier only comes to published form after that date.)

During my career, I have been fortunate to know several mathematicians of the highest level of creativity, including Graham Higman, John Conway, Paul Erdős, and Ian Macdonald. I can imagine the reaction that these people would have had if someone tried to impose the current HEFCE rules on them. Some of them would simply not have complied. So then the HEFCE bureaucrats, who after all know what research excellence is since they invented the concept, would decide that these people were not up to scratch.

On that theme, my current contract ends one month and a day before the new HEFCE rules come into force. I hope it will be renewed; but if it is not, the silver lining of the cloud will be that I will no longer be bound by these silly rules. I will be able to do research, post it on the arXiv, and if I am really proud of it, submit it to a diamond open access journal, and that will be that.

And further diverting on that theme, it really seems that neither HEFCE nor one of the commenters on my previous post realise that there is any alternative to gold or green open access.

Back to general issues. How do you prove acceptance date of a paper? By the date on the editor’s letter notifying acceptance, apparently (with some exceptions: I found one journal which included an official acceptance date in the letter). So you have to keep this letter. It probably came by email. The two University email systems I have to deal with are Outlook and Office365 based, which means that all my mail is stored in a cloud under the control of Microsoft. It seems more than a little naive to assume that it will still be there in 2020 when you might need it. Moreover, these systems do not allow you to save emails as local files, unlike the old workhorses I used to use such as mutt or squirrel mail. I have asked various systems managers for a way round this, but nobody has been able to help. So I have resorted to copying the text (including headers) into a text file and saving that somewhere that will get backed up.

And, while I am on general things, Martin Eve said,

If your institution isn’t allowing you to use arXiv to fulfil the requirements, that’s not HEFCE’s fault, it’s your institution being over-zealous. The policy explicitly allows arXiv: “a subject repository such as arXiv”.

I mentioned the fact stated in the last sentence in my original post. But the whitewash of HEFCE doesn’t hold, since it is their policy which has driven universities into this over-zealousness.

In pre-Internet days, we had a system which worked well for making papers public. Journals would provide a number, typically 50, of “offprints” of a published paper (printed documents identical with the published version). Anyone could then write to the author asking for an offprint, which would be sent provided that the paper was not so popular that the supply had been exhausted. Departments usually had a supply of request cards which could be filled in and posted. The analogue of gold was the facility to buy extra offprints at your own or your university’s expense.

Right, down to business …

First scenario

I write a paper, prepare it very carefully, and post it on the arXiv at the same time as submitting it to a journal. Let us say, either a diamond journal, or a gold journal for which my university is prepared to stump up a huge sum of money. Back it comes with referees’ reports pointing out that there is nothing wrong with the mathematics, but asking for small changes in grammar or style. I happen to think that these changes degrade the paper, making it less precise or harder to understand; but I want the paper published, I am busy, so I swallow my pride, make them, and send the paper back to the journal, who tell me it is now accepted. Now there is a superior version on the arXiv, but I can’t count the paper for the REF unless I post an inferior version. Moreover, the over-zealous administrators will probably expect me to post this inferior version on the institutional repository as well. Then finally it will appear in the journal.

So now there are four copies of the paper out there. The arXiv never deletes anything; if you update a paper, the old copy is still there. If you think about arXiv submissions of controversial papers claiming to solve big problems, you will quickly realise that this is the correct, indeed the only possible, strategy. (I don’t know if this is also true for institutional repositories.) So the “good” version is still there, but it is no longer the default, and you will only get it if you ask for it.

Is there anywhere a mathematician who thinks this scenario is not realistic?

Of course, if I decide to fight against this proliferation and depression of standards by not posting the second version, I can’t put the paper in the REF. So, even leaving aside the possible depression of standards, the effect of HEFCE policy is to fuel a big increase in the number of copies of a paper on the web, making searching for the “right” one virtually impossible.

Second scenario

I write a paper with an author in a different country. She does not realise the stupid bureaucracy that UK academics suffer from, and she knows that I am busy, so when the acceptance letter comes, she does not bother to forward it to me.

So how do I find out that the paper has been accepted? Maybe when it appears in the journal (or on their website), or maybe when I wonder why I have heard nothing and ask my coauthor. In either case, by this time it may be too late to satisfy the HEFCE requirement (even if the version on the arXiv may, as in the first scenario, be as good as or better than the published version).

I hasten to say that none of my co-authors would behave like this; they are without exception more conscientious than I am! (Not difficult, actually!) But it may be a bit intimidating or embarrassing for junior academics to have to nag senior colleages in other countries for these bureaucratic details.

Posted in maybe politics | Tagged | 5 Comments

G. C. Steward lectures 2008

While I was uploading lecture notes, I also put on the page the notes from my G. C. Steward lectures at Gonville and Caius College in 2008. You can find them here.

I spent the first half of 2008 in Cambridge, directing a programme on “Combinatorics and Statistical Mechanics” at the Isaac Newton Institute. Jan Saxl very kindly invited me to Caius, and arranged for me to be the G. C. Steward visiting fellow. Along with very congenial company at the excellent meals, and somewhat noisy accommodation above the infamous Gardenia restaurant in Rose Crescent, my only duties were to give “three or four” lectures to the mathematics students at the college, which I was very happy to do. I was able to play with various literary allusions: the title of the series was “Never apologise, always explain: scenes from mathematical life” – the first four words I regard as a good rule for a mathematician – and the individual lectures were “Before and beyond Sudoku”, “Proving theorems in Tehran”, “Transgressing the boundaries”, and “Cameron felt like counting”.

Posted in history, Lecture notes, Neill Cameron artwork | Tagged , , , , , , , , , , , , , , , | Leave a comment

Projective and polar spaces

I have produced a new edition of my lecture notes on Projective and Polar Spaces and put them with my lecture note collection.

I did this because it seems that people still find some use for these notes. According to Google Scholar, they are my 16th most cited publication, with 113 citations. The first edition was hard copy in the Queen Mary Maths Notes series in 1990; I had just taken over the editorship of the series from Karl Gruenberg. It was probably a bad time to do that; we sold copies by email (though we had to ask our customers to send a cheque), but didn’t realise how the web would become the location of choice for lecture notes.

In 2000, I produced a second edition which I did put on the web. Back then, downloading a big file was a tedious procedure, so I made each chapter a separate PDF file. Now things have changed, and so I have re-integrated them. Apart from that, the changes are very small, detailed below. I regard this as, in some sense, a historical document, and I am too busy at the moment to produce a proper revision.

In 1990, I had only recently moved to Queen Mary, and even more recently started using TeX. By choice, in those days, I used plain TeX, since I wasn’t very fond of the default LaTeX style and wanted to make my own decisions about how the notes looked. (I still don’t like default LaTeX very much, but this is what journals want these days.) So this was my first attempt at a large-scale TeX document.

Of course, there was a difficulty: a book like this is full of diagrams; not only geometric diagrams like Desargues’ Theorem but also Buekenhout diagrams, which sometimes had to be embedded within the text. LaTeX had a picture environment, which would do the job; how could I do it in plain TeX?

Someone pointed out to me that the code for the LaTeX picture environment is almost completely self-contained and can be detached from the rest of LaTeX. I did so. If I recall correctly, there was only one incompatibility that I had to deal with. Plain TeX used the command \line to refer to a line of text, and complained about the double use. So I simply replaced \line by \Line everywhere in the LaTeX code.

One interesting problem I had to face using this was the restriction on slopes of lines (which were produced by typesetting small line segments from special fonts). A line, other than a horizontal or vertical line, had to have slope which was a rational number with numerator and denominator coprime and at most 6 in absolute value. I needed to draw things like the Desargues configuration so as to appear fairly “generic”, without obvious symmetries or coincidence of slopes. This took a bit of work, but I think I managed fairly well.

However, one thing defeated me. I wanted to show the diagram showing how Desargues’ Theorem follows from Pappus’ Theorem, which involves adding some extra lines to the Desargues configuration so that the three invocations of Pappus are visible. The slopes of the extra lines I needed did not fit the restrictions! In the hard-copy first edition, I drew them in by hand; in the second edition, I threw in the towel, and put a statement in the preface apologising that several lines were missing. Now the LaTeX curves package will draw a straight line through any two points, so in the new edition I have been able to include them. I have also tried to make the diagram easier to follow by use of colour: the line whose existence we are trying to prove is red, projections of existing lines are blue, and other construction lines are green.

Incidentally, there is a problem related to the LaTeX picture environment, to which I don’t know the answer:

What is the maximum number of points in the plane with the properties that no three are collinear, and the line joining any two can be drawn in the LaTeX picture environment (that is, its slope is one of the allowed values)?

In the second edition I referred to some SOCRATES lecture notes containing related material. There was a European network run by Frank De Clerck in Ghent, which ran summer schools on finite geometry. The notes I referred to appear to have disappeared, I am not sure where. But I think that one set was my own notes on “Finite geometry and coding theory”, covering various topics related to quadratic forms over GF(2) including Reed-Muller, Kerdock and Preparata codes and an introduction to quantum codes. These may also have some historical value, so I have posted them here as well.

Enjoy!

Posted in history, open problems, the Web | Tagged , , , , , , | 3 Comments

Open access and the REF

After an exchange with one of the people employed by my university to “police” the institutional repository, I came upon an issue that I didn’t fully understand. If you are a UK academic hoping to submit papers to REF2020, you might want to know this.

The policy on open access comes into force on April Fools Day next year (2016). Your final peer-reviewed manuscript must be deposited in a publically accessible repository (which could be an institutional repository, or could be the arXiv) within three months of acceptance for publication. Acceptance is defined as the date on the letter or email from publisher to author informing that the paper is accepted. [The arXiv is the only subject repository specifically mentioned in the document.]

So what you must do in a year’s time, and what you should probably get into the habit of doing now, are two things:

  • post the final manuscript on the arXiv (or institutional repository);
  • keep a copy of the publisher’s acceptance letter where you will be able to find it in 2020.

It seems to me that this policy (which makes significant extra work for academics) has been designed by people with little idea about the academic publishing process. Even if your university has paid out the vast sum required for your paper to be published “gold open access”, you may still be in breach of this policy if the publisher took more than three months doing their job (not uncommon, even in high-status journals). (In fact, if it came to it, I doubt if HEFCE would refuse to accept a “gold open access” paper; it would be very bad PR for their whole open access policy if they did!)

And, while I am at it, let me state another reservation. The person I was in contact with told me that the university is not happy with the arXiv, and attempted to discourage me from using it, because “we don’t have the resources to be checking it for compliant articles”. (This despite the fact that they have four people policing their own repository!) So the knock-on effect of HEFCE policy as interpreted by universities is to put pressure on academics not to use the arXiv. In my view this is exactly the reverse of what they should be doing!

The HEFCE document on open access for the 2020 REF is here.

Posted in maybe politics, publishing | Tagged , , , | 8 Comments