Runnymede and Whitby

Whitby Abbey

The two excursions at the Durham symposium were a walk down to Palace Green to see the Cathedral and the Magna Carta exhibition, and a trip to Robin Hood’s Bay and Whitby (with a walk between the two).

This year is the 800th anniversary of the signing of Magna Carta, so there has been a lot of publicity. Durham holds the only surviving version of a 1216 issue of the document, and this was on show, together with a lot of material discussing the political and religious context and the subsequent history.

Magna Carta is widely regarded as the cornerstone of our liberties, but originally it was far from that; it was part of a power struggle between king and barons, and had little to say about the common people. Moreover, it seems to have been remarkably ineffective. As soon as King John escaped from the baron’s clutches, he asked the Pope to annul the document, which the pope did. The fact that it was re-enacted so many times during the following century shows how little observed it was. (If a law is strictly observed, it doesn’t need to be re-enacted.) It was later that it came to be seen in the way we now view it, in particular in the struggle between King and Parliament that preceded the English civil war of the seventeenth century.

So how come the king was able to appeal to the Pope as a higher authority? This is because of what was maybe a far more important event that happened 550 years earlier, the Synod of Whitby. (Our walk took us right past the ruins of the monastery where the synod took place, although they are of much later date. The monastery was then called Streonshalh, and was administered by St Hilda. The name Whitby was the result of the Viking invasion, which also precipitated the move of Cuthbert’s relics which ended in Durham – but that is another story.)

Christianity came to Northumberland from two directions: from Iona, where the missionaries had been brought up in the Celtic form of religion current in Ireland; and from Canterbury, founded by Augustine under the direction of Pope Gregory of Rome. There were many differences between the Celtic and Roman forms. The best known concerns the date of Easter: occasionally the rules adopted by the two sides led to Easter being celebrated a week earlier in the Celtic rite than in the Roman. But I think the most important differences were political. In Celtic Christianity, the bishop was often one of the monks of the local monastery, not always the most important. There was no contradiction between Cuthbert (whose remains are venerated in Durham cathedral) being bishop of Lindisfarne and his being a hermit on the remote Farne islands. By contrast, the Roman church was hierarchical, with bishops, priests and deacons like army officers and the laity the common soldiers.

Bede, the first English historian (whose remains are also in Durham cathedral), records in detail the debates at the Synod of Whitby in 664, called to resolve the differences between the two forms of religion. King Oswiu presided over the synod, and made the closing speech in which he decided in favour of the Roman view. In Bede’s account, the king was concerned to make the right choice so as not to risk the salvation of his soul. But it seems very likely that there was a big political element in the settlement. Wilfrid, the champion of the Roman cause, had already appealed to the pope in several disputes with his ecclesiastical colleagues. (As we saw, he was by no means the last to do so.) By choosing the Roman form of Christianity, Northumberland became firmly a part of Europe rather than of the Celtic fringe.

It could be said that 664 was when England (or at least an important part of England) joined Europe for the first time. Relevant for current debates, perhaps?

PS Why is there a pirate ship in the road outside the abbey? Don’t ask!

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

A precious jewel

One of my favourite textbooks is Simmons’ Introduction to Topology and Modern Analysis. In the introduction, the author distinguishes two types of mathematics: the rare jewels, like the formula saying that the Riemann zeta function evaluated at 2 is π2/6; and the general theories, such as the book is about (Part 1 is general topology, Part 2 is linear algebra up to the spectral theorem, and Part 3 merges them to give functional analysis).

Two jewels of a kind of mathematics that aspires to be a general theory are among my favourite objects. I have known about the random graph for nearly 40 years, and can no longer remember when I first heard about it. Fifteen years ago, when I talked about it at the ECM in Barcelona, Anatoly Vershik introduced me to the Urysohn space. Now, in a lecture by Slavomir Solecki, I have met a third such object, the pseudo-arc.

If you have an eye for such things, you will have noticed that each of these has the definite article as part of its name; this implies that each such object is unique, and hints that however you try to construct it (within a wide range) you will end up with the same thing. The same is true of the pseudo-arc.

First, a brief comment about Baire category, a way of saying “almost all” which is complementary to saying “measure 1″ in a probability space. In a complete metric space, a subset is residual if it contains a countable intersection of open dense sets. Residual sets are “large”: they are non-empty (this is the Baire category theorem); the intersection of countably many residual sets is residual; and a residual set meets every open set.

Now consider the set of compact connected subsets of the unit square. There is a metric, the Hausdorff metric, which makes this set into a complete metric space. (Two sets are within distance ε in this metric if the ε-neighbourhood of either set contains the other.) Now there is an element P of this space (a compact connected set) with the property that the set of elements homeomorphic to P is residual; in other words, “almost all compact connected sets” are homeomorphic to P“. This P is the pseudo-arc.

Now if we started with the unit cube in n dimensions (with n>1), or countably many dimensions, we would obtain an object whose homeomorphism class is residual; but the object we obtain is in all cases homeomorphic to P.

(Why not one dimension? There is again a unique object, but it is not P. Compact connected subsets of [0,1] are intervals and points, and almost all of them are intervals; all intervals are homeomorphic.)

Aside: How depressing that it has taken so long before I learned about this object. Lines of communication across the continuous/discrete divide of mathematics clearly don’t work too well!

Slavomir’s talk explained why people on our side of the divide should know about it. Here is an outline of his talk.

  • We know very well Fraïssé’s construction. We take a class of finite structures with the amalgamation property (this says that, given A,B,C in the class with injective maps from A into each of B and C, there is a structure D in the class and injective maps from B and C into D such that the obvious diagram commutes). Fraïssé tells us that there is a unique countable limit of the class, a homogeneous structure such that all our finite structures have injective maps to it. Now turn all the arrows around and replace “injective” by “surjective”; the analogue of Fraïssé’s theorem holds, so that the inverse limit of the class is the unique dual homogeneous object which has surjections to all the finite structures in our class.
  • Now perform this construction for the class of finite objects which are paths with a loop at every vertex. Homomorphisms of such objects correspond to walks which at each step can move either way or stay where they are. These things can be arbitrarily tangled! But they form a dual Fraïssé class, and so the dual homogeneous structure P exists.
  • This is not what we want; an inverse limit of finite structures with the discrete topology is going to be a Cantor space, that is, totally disconnected. But there is a natural way of glueing some pairs of points together to make a connected space which turns out to be the pseudo-arc!

The last step is perhaps described by analogy. The usual Cantor space consists of points in the unit interval whose ternary expansion contains only the digits 0 and 2. If we map each point by replacing 0 and 2 by 0 and 1 and regarding this as the binary expansion, our map is one-to-one except for a small set (points whose expansion ends with an infinite string of 2s are identified with points whose expansion ends with an infinite string of 0s), and the resulting set is the whole interval.

This approach allows them to do some interesting things. They have a new proof of a theorem of Bing stating that the homeomorphism group of the pseudo-arc acts transitively on its points, and they are developing higher homogeneity properties. These results are hard work since points are quite difficult to see in inverse limits!

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

Did I prove that?

Two interesting and contrasting experiences in two days at the Durham symposium (about which you will hear lots more later). I should begin by saying that these were both during excellent talks.

Yesterday, Rehana Patel gave the first of three talks by her and her collaborators Nate Ackerman and Cameron Freer about ergodic measures concentrated on isomorphism classes of first-order structures, or on first-order sentences. I have described before the content of their first result, which is that there is an exchangeable measure concentrated on the isomorphism type of a first-order structure M if and only if definable closure in M is trivial (which means, in permutation group terms, that the stabiliser of a finite tuple of points in the automorphism group of M fixes no additional points). One new result is that the number of such measures which are ergodic is 0, 1, or the cardinality of the continuum. We know when the case 0 occurs; the case 1 occurs if and only if the automorphism group is highly homogeneous, that is, acts transitively on unordered n-element sets for every natural number n. She quoted my theorem from 1976 (my first result on infinite permutation groups) describing such groups; this shows that there are only five such structures, the countable dense linear order without endpoints, its derived betweenness, circular order, and betweenness relations, and a set without structure. Most people who quote this nowdays say that I found all the reducts of the linear order, that is, all closed overgroups of its automorphism group; I have somehow become a pioneer in the study of reducts. When I proved the theorem, I didn’t even know what a reduct was! In fact my theorem, as stated by Rehana, is more general.

The second occurred today in Christian Rosendal’s talk on the coarse geometric structure of automorphism groups. He attributed to me the theorem, or observation, that any countably categorical structure is quasi-isometric to a point. I was a bit taken aback; the first thought that crossed my mind is that this had something to do with the fact that a countably categorical structure M has the property that any structure N younger than M (that is, all finite substructures of N are embeddable in M) is itself embeddable in M: an application of König’s Infinity Lemma. However, it turned out that this followed from the statement that, for any finite tuple a of elements of M, the stabiliser of a in the automorphism group has only finitely many double cosets, or in other words, the action of the automorphism group on the orbit of a has only finitely many orbits on pairs; a trivial consequence of the Ryll-Nardzewski theorem. (If I did make this comment somewhere, it was certainly before I knew what a quasi-isometry is.)

Posted in doing mathematics | Tagged , , , , , , | Leave a comment

Computer down again

Ubuntu has let me down again, for the second time in two months.

The menu bar and launch panel have disappeared. By some ingenuity I managed to get a web browser launched, and searched for a solution to this problem. It turns out it is a common problem, and many solutions are suggested by people out there. But sad to say, none of them works for me.

So communication will be sporadic until I get back to St Andrews next month (unless anyone can provide me with a solution that does work!)

Posted in Uncategorized | Tagged , | Leave a comment

Good news on metrics

HEFCE have released their report on the use of metrics in research assessment.

And, wonderful to relate, it is good news.

You can find an excellent commentary on it, as well as a link to the report itself, on David Colquhoun’s blog. Just to quote a couple of things from the commentary (I have not had time to read the report itself yet):

  • “The tragic case of Stefan Grimm, whose suicide in September 2014 led Imperial College to launch a review of its use of performance metrics, is a jolting reminder that what’s at stake in these debates is more than just the design of effective management systems.”
  • The correlation analysis shows clearly that, contrary to some earlier reports, all of the many metrics that are considered predict the outcome of the 2014 REF far too poorly to be used as a substitute for reading the papers.
  • HEIs should consider signing up to the San Francisco Declaration on Research Assessment (DORA).

Now we await action on this report. I am not too hopeful: EPSRC commissioned an International Review of UK mathematics, and proceeded to ignore it and do the opposite of its recommendations. But HEFCE should be aware that we are watching them.

Posted in Uncategorized | Tagged , , | Leave a comment

Beginning a career

Yesterday was my tenth consecutive day of conferences.

I’ll start this post with a detour. Bill Tutte was one of the deepest thinkers on combinatorics in the twentieth century. One of my favourite mathematics books is his Graph theory as I have known it. What appears on the surface to be a number of chapters on unrelated topics in graph theory actually charts the progress of his mathematical career, with clear explanations of the links and thought processes that brought him from one topic to the next.

His first mathematical work, done (with Brookes, Smith and Stone while they were undergraduates at Cambridge, where Tutte was actually studying chemistry) was on squaring the square, that is, dissecting a square into squares of unequal sizes. Graham Farr showed us the origin of this problem with H. E. Dudeney in the early twentieth century, and a picture of a beautiful realisation of the solution that Tutte and his coauthors found on the Tutte memorial in his hometown of Newmarket near Cambridge.

The National Museums website, linked above, suggests that the squared square represents “Bill’s early fascination with mathematical puzzles”. But, as the graph theory book makes clear, and as Graham stressed in his talk, this was much more than a puzzle: it led Tutte, via electrical networks and Kirchhoff’s laws, to deletion and contraction and so to the Tutte polynomial and some deep insights in graph theory and matroid theory. It was indeed the start of his career, and arguably the event that persuaded him to become a mathematician rather than a chemist.

I was reminded of this yesterday at the final day of a Cambridge conference, celebrating the birthdays of two of my mathematical brothers, Martin Liebeck and Jan Saxl.

Martin Liebeck and Jan Saxl

I caught just four talks, by Laci Pyber, Aner Shalev, Cheryl Praeger and Peter Neumann.

While the first three told us lots of big impressive theorems (including, among many others, the disproof of a conjecture of Étienne Ghys, the solution of Waring’s problem in finite simple groups, and the proof of a conjecture of Charles Sims), Peter Neumann adopted a different strategy, which he only explained at the end of his talk, and which I am going to discuss here. He told us about a property of finite groups called the TPP (triple product property), devised by Henry Cohn and Christopher Umans in a group-theoretic approach to find new bounds for the exponent of matrix multiplication (the smallest number c such that two n×n matrices can be multiplied with at most nc+o(1) arithmetic operations.

Had they succeeded, this would have been highly significant; but they didn’t, and nobody else has since, so the problem has to stand on its own merit, and probably most people would agree that it is not the next big thing in finite group theory.

However, Peter (speaking as the thesis supervisor of both of the birthday boys, as well as of Cheryl Praeger and me), ended by talking about what is maybe the critical problem in supervising a student: finding a good problem. This should be a problem to which the supervisor does not know the solution, but believes that a reasonably strong student would be able to find it. (I completely agree: the default assumption about a new student is that (s)he will go beyond what I have been able to achieve.) It is also important that the problem will open up pathways leading in various different directions, which a good student will be able to follow. He seemed to regard the TPP problem as one filling this specification, as were the problems he suggested to Martin and Jan when they were students.

So let me conclude with my experience. As an undergraduate in Brisbane, I did a project on the simplicity of the groups PSL(n,q), taken from Dickson’s book (and quite hard going it was with its out-of-date terminology). But I also worked on several problems I devised myself, mostly general mathematics, but often with some combinatorial flavour (although, at the time, combinatorics was not a recognised subject at the University of Queensland). The best worked out was to develop an analogue of cartesian product for unordered n-tuples, that is, put structure on the set of unordered n-tuples of elements of some structured set.

In Oxford, Peter gave me the problem of finding all the primitive permutation groups of degree 57. (A long paper he had just written, on primitive groups of degree 3p for p prime, was to be my guide.) Now it just so happened that the only such group which is not 2-transitive is isomorphic to PSL(2,19); the point stabiliser is isomorphic to PSL(2,5), and acts as such on one of its orbits (having size 6). This 2-transitive action of the stabiliser meant that, in modern terminology, the orbital graph is 2-arc transitive. But at the time, Donald Higman and Charles Sims had only just introduced combinatorial and graph-theoretic methods into the study of finite permutation groups. Another primitive group in which the stabiliser acts 2-transitively on one of its orbits was the recently-discovered Higman–Sims group, which played a big part in my thesis. I described at my 60th birthday conference in Ambleside how I got from the Higman–Sims group to the Urysohn metric space.

So I think that my supervisor’s principle was just right for me.

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

The Tutte polynomial

Royal Holloway

The Tutte polynomial is an important 2-variable polynomial associated with a matroid (and in particular, with a graph). I have been at a workshop on “New Directions for the Tutte Polynomial”, organised by Jo Ellis-Monaghan and Iain Moffatt, at Royal Holloway University of London.

It was a very successful workshop, with plenty of “collaboration time” built in; many new directions were described by the participants. I will try to say a bit about some of these.

Slides of talks will shortly be available on the conference website.

Constructions of the Tutte polynomial

There are two standard formulae for the Tutte polynomial, one as a generating function for ranks and cardinalities of subsets, the other (Tutte’s original definition) in terms of “internal and external activity” of bases. Probably its most important property is the recurrence relation for it based on deletion and contraction; this allows us to express any parameter satisfying a deletion-contraction recursion (such as the number of q-colourings of a graph, or the weight enumerator of a code) as a specialisation of the Tutte polynomial.

Here are some of the approaches that participants took.

  • Alex Fink gave two constructions, one involving the geometry of polytopes, the other algebraic geometry, involving a double fibration of a certain flag space. (Stephen Huggett pointed out that this double fibration, in a special case, is at the basis of twistor theory, as developed by Roger Penrose. One one side we have a Grassmannian, which (when comlexified and compactified) becomes Minkowski spacetime; on the other, a product of two projective spaces. A cohomology class on one of these spaces yields (by what is known as the Penrose transform) a solution to field equations such as Maxwell’s in spacetime.)
  • Stephen Huggett described his construction (with Michael Eastwood) of a sequence of manifolds from a graph; using the Leray spectral sequence, the Euler characteristics of these manifolds are evaluations of the chromatic polynomial at positive integers. He described his attempts, not so far successful, to extend this to the Tutte polynomial.
  • Matthias Lenz gave us a construction based on box splines, things which have their roots in approximation theory.
  • Julien Courtiel gave a very general definition of internal and external activity which extends both Tutte’s definition and several others which have been proposed.

Other polynomials

Various generalisations or related polynomials were presented, among them the following.

  • Ribbon graphs are an abstraction of graphs embedded in surfaces: edges are two-dimensional ribbons which may be twisted. The corresponding matroid notation is that of a delta-matroid. Following an introduction by Steve Noble, we heard several talks about these structures and their polynomials. In particular, Hendrik Hoogeboom and Robert Brijder took us from the DNA of ciliates (these organisms have two nuclei: in one of them the genes are in random order and sometimes reversed, in the other they are correctly arranged, and biologists are interested in how this trick is done) to the structure of delta-matroids.
  • Iain Moffatt gave a very general construction of the Tutte polynomial of a combinatorial Hopf algebra. His method has the feature that it explains why three different polynomials for graphs on surfaces have been proposed (the Las Vergnas, Bollobás–Riordan, and the Krushkal polynomials). These arise from three different conventions that could be adopted about contracting a loop; he illustrated by tightening his own belt.
  • Andrew Goodall gave us several instances of sequences (Gn) of graphs, where the number of homomorphisms from a given graph to Gn is the evaluation at n of a suitable graph polynomial. (Choosing the complete graphs gives the usual chromatic polynomial.)
  • I talked about orbit counting versions of the Tutte polynomial, where sometimes one needs two potentially infinite families of variables rather than just two variables. Unlike most other generalisations, there is no deletion-contraction available here, since these operations change the symmetry. (The student magazine, by the way, is called Orbital.)
  • Graham Farr took up another of Tutte’s themes, alternating dimaps, arising from dissections of triangles into triangles. Here there are three notions corresponding to deletion and contraction, and they don’t commute, which makes the theory much harder.
  • Alan Sokal was at the meeting. Although he didn’t give a talk, he encouraged many people to develop multivariate versions of their polynomials. But on the last day, he got more than he bargained for. Jo Ellis-Monaghan defined a new gadget called the V-polynomial, which (regarded as a generalisation of the Tutte polynomial) specialises to the list colouring polynomial, and (regarded as a generalisation of the Potts model partition function) allows arbitrary interactions and arbitrary (variable) external field!

Related topics

We had several talks on related issues.

  • James Oxley reminded us of the critical problem for matroids, in which a lot of very hard conjectures (including Hadwiger’s conjecture and Tutte’s 5-flow and tangential 2-block conjectures) lie hidden. He kept us awake by asking questions, encouraging audience response by rewarding correct answers with granola bars thrown with unerring accuracy.
  • Gordon Royle reported on progress with Steve Noble on the Merino–Welsh conjecture, which relates values of the Tutte polynomial at (0,2), (1,1), and (2,0). Seongmin Ok recorded further progress on this.
  • Joseph Kung introduced us to the G-invariant of a matroid, and the notion of a freedom matroid (homage to George W. Bush). The G-invariant records, for all orderings of the elements of the matroid, the positions where rank increases when the elements are added; in other language, the position of the lexicographically first basis in the ordering.
  • I am sure that this is connected to the topic of trellis decoding, a real-time decoding method assuming that the word received over a communication channel is analog (has real components), and is better than digitising it and decoding digitally. The method uses a directed network called a trellis. In brief, for binary codes, the trellis doubles in size at positions of the lexicographically first basis associated with the code, and halves at positions of the last basis; the tension between pushing the first basis late and the last basis early makes the problem interesting. Is there an analogue of the G-invariant which records both first and last basis? Does the Tutte polynomial encode information about the “average” trellis complexity of a code under all orderings?
  • Dong Fengming told us about zero-free regions for the flow polynomial of certain graphs. (This polynomial is a specialisation of the Tutte polynomial which is in some sense “dual” to the chromatic polynomial, though as I argued in my talk it is really dual to the tension polynomial.)

In conclusion

An extremely successful workshop. Joseph Kung told me that, early in his career, he had been advised not to work on such a minority subject as matroid theory. Hopefully, the subject is so well connected to the rest of mathematics that this couldn’t happen now!

Royal Holloway has a beautiful campus, rich in mature trees of many kinds, and is within walking distance of Windsor Great Park. The weather was mostly kind to us. The bedrooms were comfortable, much less cramped than those at Warwick. Lunch was provided outside the lecture room, except on Monday, when we were “bumped” by a graduation event.

Wi-fi provision was deficient. The conference information promised that eduroam would be available. It was on the wi-fi menu, but nobody I spoke to could connect to it. The conference network had been designed by people who think that the only way anyone accesses the internet is via a web browser; so ssh, Dropbox, and Thundebird were all disabled. So I was effectively out of communication for the entire meeting. To make things worse, I had forgotten to bring the power supply for my notebook, so was restricted to its five-hour battery life. I was glad to find that I didn’t find myself getting twitchy because I couldn’t check my email; it was a welcome break.

But apologies if you were waiting for a response from me …

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