From the archive, 9

Looking for a book yesterday, I turned up a file of old papers. One of them I think deserves an afterlife, so I re-typed it and here it is.

First, the background.

Let A be an n×n matrix. The permanent of A is calculated in a similar way to the determinant (as a sum over permutations), but without the alternating signs. In other words, for each matching from rows to columns, take the n elements of the matrix picked out by the matching (those whose row and column numbers are matched), and multiply them; then sum the results over all n! matchings.

Unlike the determinant, which can be computed with O(n3) arithmetic operations, the permanent (despite its simpler definition) is hard to compute, indeed it is #P-hard. However, it is important, since it counts various things of interest. In the special case where the entries of A are all 0 or 1, the term corresponding to a matching is 1 if all the corresponding matrix entries are 1, and is 0 otherwise. So, regarding such a matrix as describing a bipartite graph (whose vertices are the rows and columns, with an edge wherever there is a 1 in the matrix), the permanent of A is the number of matchings (sets of n disjoint edges) in the graph.

A square matrix is said to be doubly stochastic if its entries are all non-negative and its row and column sums are all 1. The reason for the name is that a non-negative matrix with row sums 1 can be regarded as the transition matrix of a Markov chain with n states; the column sum condition essentially means that we can run the Markov chain backwards.

A permutation matrix (a (0,1)-matrix with a single 1 in each row or column) is doubly stochastic (though the Markov chain is not stochastic at all, but completely deterministic!); its permanent is 1. The matrix with every entry 1/n is also doubly stochastic (and represents a Markov chain which forgets where it came from after 1 step), and has permanent n!/nn.

In 1926, van der Waerden conjectured that the permanent of a doubly stochastic n×n matrix is at least n!/nn, with equality holding only for the constant matrix. This conjecture was proved in 1979 or 1980 independently by Egorychev and Falikman. However, it is less remembered that, in 1979, Bang and Friedland independently gave the slightly weaker lower bound 1/en. (I would like to pay tribute to Jack van Lint, who told me about these results.)

I had been thinking about Latin squares, Steiner triple systems, and what I then called “edge-parallelisms” (or 1-factorisations of complete graphs). These three have many things in common, including a Markov chain (proved for Latin squares but still conjectural in the other cases) for choosing one uniformly at random. Subsequently I invented the notion of a “generalised t-design” and remarked that these objects are the generalised 2-designs with block size 3 and λ = 1.

There were at the time upper and lower bounds for the numbers of such objects on n points. It was known by many people at the time that a proof of the van der Waerden conjecture would improve the lower bounds so that they would be much closer to the upper bounds. Indeed, the logarithms of the upper and lower bounds would be asymptotically equal, and would be cn2 log n, where c is 1 for Latin squares, 1/6 for Steiner triple systems, and 1/2 for edge-parallelisms.

Now it was clear to me in 1979 that the result of Bang and Friedland was good enough to have the same effect. Moreover, I saw that the upper bound for the number of objects having some non-trivial symmetry would be asymptotically smaller than the lower bound for the total number of objects. Hence:

Theorem Almost all Latin squares, Steiner triple systems, and edge-parallelisms have trivial automorphism group (in the sense that the proportion of such objects of admissible order having a non-trivial automorphism tends to 0 as n tends to infinity).

I thought this was an interesting result, and typed it up. But before I could submit it, or even properly check it, Laci Babai published the result for Steiner triple systems, and so I abandoned my manuscript.

Laci knows of its existence, and over the years has urged me to make it public. I was previously unable to do so since I couldn’t put my hands on it. But now I have found it, so I am happy to put it on the web (for the sake of history, not with any intention of claiming credit retrospectively).

Of course I don’t remember exactly when I wrote this. But the fact that I cite Bang and Friedland but not Egorychev and Falikman indicates that it was in the very small time gap between the appearance of these two pairs of papers, so in 1979 or 1980.

I have typed the manuscript “as is”. Apart from correcting one confusing misprint, and adopting LaTeX conventions such as numbering theorems and lemmas, it is an exact copy of the original (modulo the inevitable typos). In particular, I have not checked the mathematics; while typing it out I thought that the argument in the case of edge-parallelisms is not quite right. I think it can probably be put right.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, history and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s