## 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.)

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?

I count all the things that need to be counted.
This entry was posted in exposition, open problems, the Web and tagged , , . Bookmark the permalink.

### 4 Responses to The arXiv

1. Oh, you devil! Luring us in with some easy-reading about arxiv, and then hitting us with your latest theorem!

• You’re allowed to skip that bit, you know…

2. The paper is
http://arxiv.org/abs/1108.3958
should you want to take a look.

3. James Mitchell has computed the probabilities that two random elements of Tn synchronise, for n=3,4,5,6; they are 0.7531, 0.7861, 0.8257 and 0.8597 respectively.

This site uses Akismet to reduce spam. Learn how your comment data is processed.