The arXiv

It will be absolutely clear to anyone who has given this blog more than a casual glance that I am a dinosaur mired in the 1960s or thereabouts, and quite out of tune with the modern world of Facebook, impact, and “quality”. But events seem to conspire to drag me into the third millennium, or at least the very early years of it. I recently used MathOverflow for the first time, and now I have become a user of the arXiv.

This was in part inspired by an article by Paul Ginsparg in the current issue of Nature, celebrating the twentieth anniversary of the arXiv. Readers a few years younger than I will no doubt be amazed to learn that when Paul started the arXiv, he (in common with most people on planet earth at that time) had never even heard of the World Wide Web: he began it as a preprint mail server. A bit later he heard rumours of this innovation developed at CERN, and changed his system into a web server, as it remains. The workload, of course, grew beyond what he alone could handle, and now it is administered by the Cornell University library.

(I remember an occasion when Don Taylor visited Oxford, and was talking excitedly about the World Wide Web. I hadn’t the faintest idea what he was on about. I cannot remember exactly when it was.)

Anyway, I do have papers on the arXiv, but before today, these had all been put there by various co-authors. I had in the past tried to upload a paper, and had had a humiliating failure. But I discovered that the ghosts of past failures come back to haunt you. When I tried to register as an author, I was refused permission, on the grounds that I already existed on the system. I was completely unable to find out what my username was, and indeed I still don’t know. But at least I was able to reset my password, and then to log in with my email address and password, so I guess I can live without knowing my username.

Then the paper submission. I dutifully read the instructions first, and had all the information ready. The system tried to throw me by offering me the possibility of choosing a second category. Then it tried to throw me again by not giving me a “submit” button. Eventually I found that you have to refresh the page in the browser, which the browser doesn’t like. But finally it was all done.

The paper I submitted, if you are interested, “describes” the maximal non-synchronizing submonoids of the full transformation monoid on a finite set. I solved this problem as (hopefully) a preliminary to showing that two random transformations synchronize with high probability, though everyone I talk to suggests that I am going about it the wrong way.

In more detail, a transformation monoid is synchronizing if it contains an element of rank 1, that is, one whose image has cardinality 1. My theorem is unsatisfactory in that there is a gap between the necessary and sufficient conditions. But there is a very close connection between monoids and graphs, which I exploit. Here are a couple of definitions:

• Let X be a graph. The hull of X is the graph on the same vertex set as X, in which two vertices v and w are joined if and only if there is no endomorphism of X which maps them to the same place. It is easy to see that X is a spanning subgraph of its hull.
• Let X be a graph with clique number ω(X). The derived graph X‘ of X has the same vertices as X, and those edges of X which are contained in cliques of size ω(X).

Now the main theorems of the paper are the following:

Theorem 1. Let M be a maximal non-synchronizing submonoid of the full transformation monoid on {1,…,n}. Then there are graphs X and Y on the vertex set {1,…,n} such that End(X) = End(Y) = M, the clique numbers and chromatic numbers of X and Y are all equal, X is the hull of Y, and Y is the derived graph of X.

Theorem 2. If X is a graph which is equal to both its hull and its derived graph, then its endomorphism monoid is a maximal non-synchronizing submonoid of the full transformation monoid on the vertex set.

The obvious question is: do X and Y in the first theorem have to be equal? The further question is: can we say enough about these graphs in order to count the number of pairs of transformations which are contained in some maximal non-synchronizing submonoid, and hence show that almost all pairs synchronize?