Easy to state, hard to solve?

I described here how Pablo Spiga and I showed that all but finitely many nontrivial switching classes of graphs with primitive automorphism group contain a graph with trivial automorphism group, and found the six exceptions. (The trivial switching classes are those containing the complete and null graphs.)

Being in Prague makes me think about graph homomorphisms, so I wondered:

Problem Is it true that all but finitely many nontrivial switching classes of graphs with primitive automorphism group contain a rigid graph (one with trivial endomorphism monoid)?

The difficulty seems to be that homomorphisms privilege edges over nonedges (edges must map to edges, but non-edges can be collapsed or mapped to edges or nonedges), whereas switching treats edges and nonedges on the same footing. I can’t see how to begin: what possible connection exists between the endomorphism monoids of graphs related by switching?

(And yet, switching classes are equivalent to double covers of complete graphs, which are certainly things with a homomorphism-like feel to them.)

On the subject of switching, I managed to show the analogue for tournaments of the result for graphs. There are no “trivial” tournaments (admitting the symmetric group), so the result is:

Theorem With two exceptions (on 4 and 8 vertices), a switching class of tournaments with primitive automorphism group contains a tournament with trivial automorphism group.

This is much easier than the result for graphs. While any permutation group preserves a switching class of graphs, the groups preserving switching classes of tournaments are much more restricted: the Sylow 2-subgroups are cyclic or dihedral and act semiregularly. The only primitive groups occurring are groups of odd order (and odd degree), and groups between PSL(2,q) and PΣL(2,q), where q is a prime power congruent to 3 (mod 4).

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

From Lisbon to Prague

I love Lisbon

A plane, three trains, various buses and tubes, and I have been translated from Lisbon to Prague. Time to celebrate with some eye candy perhaps: from here

Almada church

to here:

Charles Bridge and Castle

Prague is beautiful too, and full of magic:

Art gallery window

Posted in geography | Tagged , | 1 Comment

Poe on algebraists

Michael Kinyon reminded me of Edgar Allan Poe’s comments on algebraists in his story “The Purloined Letter”. Here they are in full.

“But is this really a poet?” I asked. “There are two brothers, I know; and both have attained reputation in letters. The minister I believe has written learnedly on the Differential Calculus. He is a mathematician, and no poet.”

“You are mistaken; I know him well; he is both. As poet and mathematician, he could reason well; as mere mathematician, he could not have reasoned at all, and thus would have been at the mercy of the Prefect.”

“You surprise me,” I said, “by these opinions, which have been contradicted by the voice of the world. You do not mean to set at naught the well-digested idea of centuries. The mathematical reason has long been regarded as the reason par excellence.”

‘Il y a à parièr,’” replied Dupin, quoting from Chamfort, “‘que toute idée publique, toute convention reçue, est une sottise, car elle a convenue au plus grand nombre.’ The mathematicians, I grant you, have done their best to promulgate the popular error to which you allude, and which is none the less an error for its promulgation as truth. With an art worthy of a better cause, for example, they have insinuated the term ‘analysis’ into application to algebra. The French are the originators of this particular deception; but if a term is of any importance—if words derive any value from applicability—then ‘analysis’ conveys ‘algebra’ about as much as, in Latin, ‘ambitus’ implies ‘ambition’, ‘religio’ religion, or ‘homines honesti’ a set of honorable men.”

“You have a quarrel on hand, I see,” said I, “with some of the algebraists of Paris; but proceed.”

“I dispute the availability, and thus the value, of that reason which is cultivated in any especial form other than the abstractly logical. I dispute, in particular, the reason educed by mathematical study. The mathematics are the science of form and quantity; mathematical reasoning is merely logic applied to observation upon form and quantity. The great error lies in supposing that even the truths of what is called pure algebra are abstract or general truths. And this error is so egregious that I am confounded at the universality with which it has been received. Mathematial axioms are not axioms of general truth. What is true of relation—of form and quantity— is often grossly false in regard to morals, for example. In this latter science it is very usually untrue that the aggregated parts are equal to the whole. In chemistry also the axiom fails. In the consideration of motive it fails; for two motives, each of a given value, have not, necessarily, a value when united, equal to the sum of their values apart. There are numerous other mathematical truths which are only truths within the limits of relation. But the mathematician argues from his finite truths, through habit, as if they were of an absolutely general applicability—as the world indeed imagines them to be. Bryant, in his very learned ‘Mythology’, mentions an analogous source of error, when he says that ‘Although the pagan fables are not believed, yet we forget ourselves continually, and make inferences from them as existing realities.’ With the algebraists, however, who are pagans themselves, the ‘pagan fables’ are believed, and the inferences are made, not so much through lapse of memory as through an unaccountable addling of the brains. In short, I never yet encountered the mere mathematician who could be trusted out of equal roots, of one who did not clandestinely hold it as a point of his faith that x2+px was absolutely and unconditionally equal to q. Say to one of these gentlemen, by way of experiment, if you please, that you believe occasions may occur when x2+px is not altogether equal to q, and, having made him understand what you mean, get out of his reach as speedily as convenient, for, beyond doubt, he will endeavour to knock you down.”

I must admit I would quite like to knock him down for this amazing farrago. But it is more interesting to refute him point by point. A good exercise for students?

And yet there is something in what he says. Julian Jaynes gives an example of valid poetic reasoning, which goes something like this: “Man dies; grass dies; so man is grass”. Could it be that this kind of reasoning is closer to what makes Dupin, Holmes, and their ilk great detectives than Boolean logic? Indeed, is it closer to how we do mathematics, rather than how we write it up afterwards?

I actually don’t think that mathematicians are much better than other people in applying logical reasoning to things outside mathematics; and I think that we teachers should feel a bit ashamed of that fact.

Posted in history, mathematics and ... | Tagged , , , | 3 Comments

Computational algebra in Lisbon

This week I was at a very nice workshop on Computational Algebra in Lisbon. Rarely do I learn so many new things at a conference, although it was only three days in duration.

Here are some of the highlights, roughly in order of appearance.

Catarina Carvalho told us about constraint satisfaction. I have heard several times about the Feder&hdash;Vardi dichotomy conjecture, according to which a constraint satisfaction problem is either in P or NP-complete; and I have heard several times about the clone of polymorphisms of a relational structure, and how it gives information about the CSP. But I hadn’t realised how clearly that there are five relevant complexity classes, in descending order NP, P, NL (nondeterministic logspace), L, and AC0 (I don’t know what this last one is), and five 2-point restrictions of the polymorphism clone, with proved or conjectured relations between the complexity classes and the non-occurence of various combinations of these types.

Pedro Silva talked about some work he has been doing with John Rhodes and others, connecting matroids, fundamental groups of simplicial complexes, and superBoolean algebras. This deserves more than a quick sketch, and I want to return to it in more detail later.

Michael Kinyon talked about the use of automated deduction systems (in particular Prover 9) in finding and proving big theorems about three classes of loops: Moufang loops, Bruck loops, and automorphic loops. He really kindled my interest in simple automorphic loops, and I hope to return to this later as well.

Mikhail Volkov gave two stunning talks.

The first was about expanders. It was advertised as primarily about algebraic constructions of expanders, but instead he spent some time showing us in detail how bipartite graphs with good expansion properties give rise to an infinite class of linear error-correcting codes in which both the rate and the relative error-correction (number of errors corrected divided by length) are bounded away from zero.

The second was about the Černý conjecture, which I have talked about here earlier. The conjecture asserts that, if a finite deterministic automaton with n states is synchronizing, then it has a reset word of length at most (n−1)2. If true, this would be best possible; but there are very few known examples attaining the bound: one infinite family, and eight sporadic examples all with n ≤ 6. Instead of trying to prove this, he and his student Vladimir Gusev computed the shortest reset word for all automata with 8 or 9 states. As expected, they found only one meeting the bound; below this there was a gap, then a small “island” of values, then another gap, then the “mainland” below that. For example, for n = 9, there is one automaton with reset word of length 64, then 6 with reset word in the set {56,57,58}, then a gap to 52.

He explained that this reminded him of very similar behaviour in a different problem where more is known. A non-negative matrix is primitive if some power of it is strictly positive; the smallest exponent of such a power is the exponent of the matrix. Wielandt showed in 1950 that the exponent of a matrix of order n is at most (n−1)2+1; there is one matrix of this exponent, and one of exponent (n−1)2, then a gap, an island, and another gap. The coincidence is not exact, but is still very striking.

So they went on and estabished very close connections between the two problems, so that slowly synchronizing automata can be constructed from matrices with large exponent. It hasn’t led to a proof of the conjecture, but it certainly has thrown some very interesting light on it!

James Mitchell talked about his software for establishing properties (e.g. order, R-classes) of various kinds of semigroups, beginning with transformation semigroups. Before this, state-of-the-art meant computing, storing and counting all the elements of the semigroup; an obvious disadvantage, but the advantage is that it only requires that you can multiply and test equality for the semigroup elements. By contrast, group theorists have the Schreier–Sims method which can give the order, membership test, etc., of a permutation group with given generators much more efficiently, and in particular without computing all the elements. James explained how his Semigroups package for GAP borrows not only ideas but code from the Schreier–Sims algorithm for doing the same thing for semigroups, and gave us a demonstration. The method works more generally, requiring only that your generators lie in some overarching regular semigroup. So as well as transformation semigroups, they work for semigroups or matrices, partition monoids, and so on. I have wished for something like this for a long time, and now it exists!

There was other nice stuff too, but for me these were the best.

The slides of my two talks are in the usual place.

At the end of the talk, João Araújo was interviewed by a journalist about his on-line PhD courses, which I mentioned earlier. After João’s interview, the journalist talked to three of the students who had come along (one of them, Manuel Martins, had spoken at the conference about his web-based version of GAP), and then to three of the teachers (Michael, James and me), and finally another session with João.

One of my regrets is missing the conference dinner in order to fly home. I was standing in a queue for forty minutes while the other delegates were presumably tucking in, and because of various delays along the way I didn’t walk in through my front door until ten past two in the morning.

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

A trip to Coimbra

World Heritage site

The University of Coimbra is the oldest in Portugal, having been founded in 1290 (younger than Oxford, older than St Andrews), but after bouncing back and forth between Coimbra and Lisboa for a while, it finally settled in Coimbra in 1537. Dom João III gave the University his royal palace at the top of the hill, and this is now the heart of the University, with an ancient library, chapel, meeting room, examination room, and so on. The wonderful University palace quadrangle and surrounding buildings are since 2013 a World Heritage site.

Rosemary and I spent two quite extraordinary days in and around Coimbra. I thought the purpose of the trip was for me to give a colloquium talk – I did that, speaking on “The Random Graph”, and drew an enthusiastic audience of over thirty, quite remarkable for this time of year – but it seems that the real purpose was for me to be shown some of the wonders of this part of Portugal, and to receive Portuguese hospitality from my hosts Jorge Picado and Maria Clementino.

Jorge met us at the station, gave us a tour of the University palace and courtyard, and then with Maria took us to lunch. After my talk, we were delivered to the hotel with instructions about where to find Coimbra fado that evening.

Mathematics and fado

Coimbra fado is different from the Lisboa variety, and its performance is jealously guarded. It seems to me that it gives the musicians much more interesting things to play. We heard a singer and two guitarists (one playing a Portuguese guitar, whose tuning pegs radiate out like a peacock’s tail, the other a regular Spanish guitar) at the Santa Cruz café. Fado, beer, and ham and cheese to pick at. After the fado, we walked through the park on the banks of the river Mondego, the largest river entirely within Portugal (the Tejo and Douro both rise in Spain), where we sat and watched swallows, kites, and wispy clouds.

The next day was all sightseeing, first to the Roman town of Conimbriga, and then to the forest of Bussaco.

The guidebook says that the name Conimbriga gave rise to Coimbra when it was transferred to the town formerly known as Aeminium, though according to Jorge, not all authorities agree. There was a sizeable settlement here from about 900BC, on a plateau at the edge of a steep river gorge. The town flourished in Roman times; only 15% of it has been excavated. Some of the most extensive houses were demolished to build a defensive wall against the barbarians at the end of the Roman empire. Much of the underfloor heating systems and many fine mosaic floors remain, and many artefacts of Roman life have been found.

Many of the mosaic patterns are geometric, including a couple of vertex-transitive tesselations (one with squares and octagons, one with triangles, squares and hexagons).


Bussaco has an alternative spelling Buçaco, sometimes in the same document. It was owned by a monastery of Carmelite friars, to whom its remoteness was a great benefit. They built a via sacra and hermitages as well as a monastery. In the Napoleonic Wars it was the scene of a fierce battle, when Portuguese and British forces inflicted the first defeat on Napoleon’s troops. Later a hotel was built overshadowing the old monastery, in a flamboyant neo-baroque style in which the stone almost seems to be a living and growing organism.

The monks left much of the forest in its natural state, but also planted a wide variety of trees, so that now everything from pines to tree-ferns flourishes there. Many trees were blown down in a severe storm in January 2013, but there are so many trees in the forest, and so much conservation work has been done already, that the scars are not too noticeable. We had a pleasant hike down the stream and back up beside an artificial cascade, and then on the via sacra leading to the Coimbra Gate giving fine views over the countryside below.


At the end of the day, a fast train took us back to Lisbon, in half an hour less than it had taken us getting there the day before.

Posted in events, geography, history | Tagged , , , | 4 Comments

Pedro Nunes

Pedro Nunes

Pedro Nunes was a Portuguese mathematician of the sixteenth century, perhaps the greatest mathematician of his time in Europe.

Yesterday I was treated to a very informative short presentation about Nunes and his work by the historian of science Henrique Leitão. Here are three things I learned.

First, one of Nunes’ five books was a book on Algebra. What is remarkable about it for its time is the philosophy. Nunes believed that algebra is not just a growth from the root of geometry, but an entirely new subject. His proof was that some results in geometry are more easily proved by means of algebra than by geometric methods.

Second was his discussion of the rhumb line (now called the loxodromic curve), the line traced by a ship which sails always on a bearing making a constant angle with the meridian. Such a line is not a great circle, since it spirals in to the north and south poles. (This fact was already a great novelty at the time, a curve having a finite limit point.) The mathematical tools of the time did not permit finding its equation, but Nunes proposed a “finite difference method”. The navigator sets a bearing making the given constant angle with the meridian, and sails straight (i.e. alon a great circle) until his bearing deviates from the required value by more than a given fixed amount (say one degree); then he corrects the bearing and continues. This gives a practical method for calculating rhumb lines. Nunes’ method was used by many others, and tables were produced.

There has been a lot of interest in the question of how Mercator calculated his map projection. Leitão and a colleague propose a new answer to this. Since rhumb lines appear as straight lines in Mercator’s projection, he could simply use existing tables based on Nunes’ method to derive the spacings of the parallels. This hypothesis appears to fit the data better than any other suggestion.

Nunes’ third remarkable achievement was the following. Suppose that you place a vertical stick in the ground, and watch the movement of its shadow as the day progresses. Almost everyone would say that the movement of the shadow was monotonic. However, Nunes did the calculations and showed that retrograde motion of the shadow was possible under some conditions, and worked out exactly what the conditions were. He admitted that he had never seen the phenomenon, despite knowing what to look for, and nobody he had spoken to had seen it either; yet he had sufficient confidence in his mathematics that he could confidently assert its existence. This caused a certain amount of religious controversy; the fact of a shadow standing still is described in the Bible as a miracle, and yet Nunes was proposing that standing still or even reversing can happen strictly in accordance with natural laws. (I believe that this phenomenon, though small, has now been observed.)

Anyway, the reason for this was an extraordinary event yesterday. I mentioned in March that I was teaching a group theory course to PhD students in compuational algebra at the Universidade Aberta (the Portuguese Open University). There was a celebration of the successful completion of the first year of the course, at which two Pedro Nunes awards (voted by the students on the course) were presented, to Michael Kinyon and me, by the Chancellor of the University. The ceremony began with a short presentation by João Araújo (the driving force behind the course) of how the computational algebra course was set up, and how it had run.

All this in a morning out from the Portuguese Mathematical Society summer meeting, at which I lectured. I will probably say something about this meeting later.

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

Quieter times

Rainbow over Wolvercote

Things have been a little quieter for the last couple of weeks. Tomorrow, off to Portugal for a week and a half, then the Czech Republic for a week, then a couple of weeks to catch my breath before New Zealand …

I have managed a bit of rushing round to see family.

Neill’s second book, How to make Awesome Comics, is out next month from David Fickling Books. For the young person in your life, make sure you get hold of one! He also did some artwork for the Cowley Road Carnival last weekend, and said it was quite spooky to see it plastered on every bus stop in Oxford!

Bus stop, Morrell Avenue

I learned a little bit more about Hester’s working life too. She was surprised to find a recent presentation she gave about decommissioning in the oil industry available on the web. To my somewhat biased view, she has done a good job, presenting hard facts and mostly avoiding management-speak.

Apart from all that, I have been doing some work: Pablo Spiga and I have a first draft of the paper on the theorem I discussed in the last post, and Sebastian Cioabă and I have nearly finished the paper on edge partitions of complete graphs I discussed last year.

Oh, and I set a resit exam for Mathematical Structures (but I don’t have to mark it :) )

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