ANZ 8: Glasshouses

Glasshouse mountains

The Glasshouse Mountains are a number of volcanic cores in the hinterland of the Sunshine Coast north of Brisbane. Over millions of years, the surrounding soil has eroded away leaving these strangely shaped peaks. They were named by Captain Cook in May 1770 during his first voyage. At school we were taught that they reminded him of glasshouses in his native Whitby, but it seems that glass furnaces were what he had in mind.

The people who lived here for tens of thousands of years have a legend about them, with strangely modern overtones. It concerns a family threatened by rising sea levels, the need for people to help one another, and the tragedy that arises from human weakness. (You can find an account on the Wikipedia page.)

Our holiday began with a train trip from Roma Street station in Brisbane to Beerwah, a small village named after the highest of the Glasshouse Mountains, where we sat in the sunshine waiting for my sister to arrive. The pleasant village had interesting places to eat, and two strange-looking structures by the pedestrian crossing. These turned out to be Apparatus for Expedient Market Deployment – Ananas Comosus, essentially a matter transference device developed by Joseph King in the 1930s for getting his pineapples to market before his competitors.

AEMDAC

The best place for viewing the Glasshouse Mountains is the Mary Cairncross Park, a small pocket of rainforest in the Blackall Range. We went there a few days later and met my cousin Chris and his wife Rhonda.

At Mary Cairncross Park

Chris is an expert on birds as well as a skilled photographer. In a leisurely walk around the forest he pointed out to us many small birds as well as the calls of larger birds in the canopy, and we saw several pademelons (small wallabies).

Pademelon

We spent a few days at the nearby coastal resort of Alexandra Headland. I used to go for family holidays here when I was a child. At that time, it was almost completely undeveloped, and my great-aunt had an old house right on the headland. There was neither a refrigerator nor sewage; a man delivered blocks of ice for the icebox, and the nightsoil men came to empty the backyard toilet. Now it is built up along the coast and some way inland as well; country that was swamp with paperbark and ti-tree is now covered in holiday homes, shopping malls and even a university. But the beaches and rock pools are still as they were. They have left a small area of virgin bushland, which is full of birds; sensibly in my view, its existence is not widely advertised, and it took us some time and trouble to find our way in.

Mooloolaba

We stayed in a beach resort right opposite the surf club, and walked along to the nearby mouths of the Maroochy and Mooloolah rivers. One benefit of the development is the existence of very good eating places. I don’t mind giving a plug to the Lemon and Thyme in Mooloolaba, where I had the best tapas I have ever eaten (Hervey Bay scallops with mango chilli salsa and fresh avocado, or baked Meredith goats cheese with macadamia nuts, lemon and thyme honey and toasted ciabatta, anyone?). At Maroochydore we went to Cottontree, the calm safe stretch of river where we used to swim as children, and pelicans floated on the clear water. On the way to Mooloolaba one day, we were given a long serenade by a butcherbird in a paperbark tree.

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

New Year thoughts

It was with some relief that I saw that this year WordPress have not sent a summary of the year just past. So I was able to look at the statistics and make my own judgement.

Numbers of visitors and views were down for the second year running, and in fact the decrease was much greater than last year’s. Of course this doesn’t account for email or RSS subscribers; though the statistics give the numbers of subscribers, this is not really comparable. Related to this is the fact that the number of comments is down. I do not know whether subscribers can easily post a comment, not having ever subscribed to a blog myself.

It happened that I had just been reading an article in the Guardian by Hossein Derakhshan, the “blogfather of Iran”. Six years ago, the regime regarded his blogging activities as so dangerous that they sent him to prison for 20 years. They have recently (and unexpectedly) released him, and so (comparing himself to the Sleepers of Ephesus) he returns to a world which has changed quite a lot in six years. He says very forcefully that the web “has been stripped of its political power and just streams social trivia”. If the authorities in Iran had noticed the same thing, perhaps that is why they released him.

Derakhshan remarks on two huge changes in six years.

  1. Since its inception, the web has been based on hyperlinks. In his view, a web page with no hyperlinks is a cul-de-sac, or (in a different metaphor) is blind; but a web page to which no hyperlinks point is dead. However, it seems (I didn’t know this, but I have never visited this site) that Instagram disables web links posted there, so that visitors are unable to escape!
  2. Most users of the web now go straight to Facebook or something similar. Then “algorithms” (whose operation is never made clear but is somehow dependent on past browsing habits) suggest further reading to them, which they usually accept. He says, “I miss when people took time to be exposed to opinions other than their own, and bothered to read more than a paragraph or 140 characters.”

As a consequence, it is not enough to post an article and put hyperlinks to it. He says, “I miss the days when I could write something on my own blog, publish on my own domain, without taking an equal time to promote it on numerous social networks”.

He says that the main factors influencing the algorithms are novelty and popularity. Old items sink into obscurity, and unless you attract “likes”, nobody will read what you write.

By his standards, I am terribly old-fashioned. (Though I have a confession to make; although I do not spend time promoting my blog, I am very grateful to Alexander Konovalov, who runs the CIRCA twitter account in St Andrews, for tweeting some of my posts which he thinks may be interesting to CIRCA followers. However, this fact makes the next observation even more surprising.)

I looked at the list of my most-read posts and pages in 2015. The top 18 of these were posted in earlier years! So it seems that, at least among people who read what I write, novelty is not so important. As usual, topics like lecture notes, mathematical typesetting, mathematics and religion, and expositions such as the symmetric group, stay near the top from year to year.

I also noticed that my monthly pictures from my 2015 calendar were right down at the bottom. So I have decided not to continue with this. I have created a calendar each year since 2009, and produced copies for family members. At first they were “walking calendars”, with each month’s picture of a place where I had walked in the same month the previous year. In 2013 I generalised the concept a bit, and produced a calendar with pictures of the Regent’s Canal in London, and the following year of the Fife Coastal Path. 2015 marked a move away from documentary pictures to something more “artistic”.

This year’s calendar is called “Ancient Seats of Learning”, and features pictures of Bologna, Cambridge, Coimbra, Leuven, Oxford, Paris, Prague, and St Andrews. At my sister’s request I produced some notes to go with the calendar. So this year I will simply put the notes here, and forgo the monthly pictures.

A final note. While posting this, I see that the WordPress editor does not know the word “hyperlink”.

Posted in the Web, typography | Tagged , , , , , | 4 Comments

Circular repeated-measurements designs

My first paper in a real statistical journal has just been almost accepted (just a bit of re-formatting …)

The paper is entitled “On optimality and construction of circular repeated-measurements designs”, the other authors are R. A. Bailey, K. Filipiak, J. Kunert and A. Markiewicz. You can find a preliminary version here on the arXiv.

I won’t talk about the statistics here (which wasn’t my part anyway), but there are some interesting mathematical aspects.

In matrix terms, we have a t×t matrix S which has the properties

  • S has all diagonal entries 0 and off-diagonal entries λ−1 and λ, for some λ;
  • S has constant row and column sums n;
  • SST is completely symmetric (that is, its diagonal entries are constant and its off-diagonal elements are constant), where T denotes transpose.

More is required; I will discuss the extra requirements below.

It is convenient to put A = ST−(λ−1)(JI), where J is the all-1 matrix. Then A is a zero-one matrix with zero diagonal and constant row and column sums such that ATA−(λ−1)(A+AT) is completely symmetric. Furthermore, we then divide cases as follows:

  • Type I if A+AT is completely symmetric;
  • Type II if A+AT is not completely symmetric and λ = 1;
  • Type III if A+AT is not completely symmetric and λ > 1.

In cases I and II, ATA is completely symmetric, so A is the incidence matrix of a symmetric BIBD (or 2-design). Moreover, in Type I, A+AT = JI, so A is the adjacency matrix of a doubly regular tournament (a regular tournament in which the number of points dominating a pair of points is constant). The extra that is required is a decomposition of the arcs of the tournament into Hamiltonian cycles. It is conjectured that any doubly regular tournament has such a Hamiltonian decomposition. Quite a few examples are known.

Type II allows symmetric BIBDs with other (non-Hadamard) parameters. If the BIBD arises from a difference set modulo t, all of whose elements are coprime to t, the Hamiltonian decomposition is easily found: for each element d of the difference set, take the cycle which takes steps of size d.

Type III is the most interesting and mysterious. We give several constructions. One of these takes a doubly regular tournament and simply “blows up” each vertex into a fixed number m of vertices. Another uses a “double cover” of the complete directed graph, similar to double covers of complete graphs which correspond to regular two-graphs. The only reference we could find in the literature was to a paper I wrote with Laci Babai, which I discussed here. We proved that a finite group is the automorphism group of a switching class of tournaments if and only if its Sylow 2-subgroups are cyclic or dihedral. The digraphs, to which we gave the slightly silly name “S-digraphs”, have the property that the vertices are paired, with no arc between paired vertices; the induced subgraph on any two pairs of vertices is a 4-cycle. From doubly regular tournaments we construct S-digraphs which give Type III designs in some cases.

The existence question is not completely solved; for example, the question about Hamiltonian decompositions of doubly regular tournaments is still open as far as I know. Something worth working on here, maybe?

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

Drums

Here is a small contribution to Bob Dylan scholarship. This occurred to me during jetlag-induced sleeplessness.

In several of Dylan’s songs of the mid-1960s, there is an association between mysterious dominating women and drums:

  • The heroine of “She belongs to me” is descried thus: “She’s a hypnotist collector, you are a walking antique”. In the last line the subject is admonished “For Christmas, give her big drums”.
  • In “Fourth time around”, the subject of the song “… [works] on my face until breaking my eyes”, and later the narrator “taps on her drum”.
  • The song “Sad-eyed lady of the lowlands” contains many questions, but the most urgent is when the narrator should deliver to her his Arabian drums. [At Christmas, surely? –Ed.]

The daf, or Middle Eastern frame drum, would seem to fit here, although it is not just Arabian. (I heard it played in Tehran.) It is big; it is a drum on which you tap.

So why are there no drums in “Visions of Johanna”?

Posted in Uncategorized | Tagged , | Leave a comment

Happy New Year

Back in London after my trip to the southern hemisphere. There is more to say about that, which I hope to get round to saying in the near future. But I spent Christmas on my brother’s farm at Lagoon Pocket, near Gympie; it was the first time for many years that my brother, my sister and I had all sat down to Christmas dinner together.

with Marie and John

For various reasons, the flight home was even less pleasant than usual. But it started well enough. We took the Greyhound bus from Kybong (which is just across the river from Lagoon Pocket, though you have to go out of the way to cross the river) non-stop to Brisbane airport.

Two Greyhounds pulled in at almost the same time.

Greyhounds

You see how the dog is older and has more fleas than the pup.

Posted in Uncategorized | Tagged , , | Leave a comment

Cycles and trees

The cycle has taken us up through forests …

Robert M. Pirsig, Zen and the Art of Motorcycle Maintenance

Here is a little nugget, and a problem. Nothing new but it might entertain you.

Every permutation is a product of transpositions, as is well known. The smallest number of transpositions required to express an n-cycle is n−1. So we could ask:

In how many ways can an n-cycle be written as the product of n−1 transpositions?

There is a beautiful answer: nn−2. The proof is quite short.

We can think of a transposition as an edge of an undirected graph. Now it is easy to see that the product of n−1 transpositions is an n-cycle if and only if the transpositions are the edges of a tree. Now there are nn−2 trees on the vertex set {1,…,n}, and the transpositions can be ordered in (n−1)! ways. So the number of pairs consisting of an n-cycle and an expression for it as a product of n−1 transpositions is nn−2(n−1)!.

But there are (n−1)! cycles, and all are conjugate in the symmetric group, so each has the same number of expressions as the product of n−1 transpositions.

Given this nice result, and the fact that the number of trees on {1,…,n} is also nn−2, it would be natural to wonder if perhaps, given any labelled tree, every cycle can be obtained (uniquely) by ordering the edges suitably.

In the case of the star, with edges (1,i) for 2 ≤ i ≤ n, this is true; this follows from the fact that

(1,a1)(1,a2)… = (1,a1,a2,…),

the standard expression used to show that a cycle can be written as a product of transpositions.

However, this example is misleading:

Theorem Let T be a tree on the vertices {1,…n}. Then every n-cycle arises from a unique ordering of the edges of T if and only if T is a star.

The reason is very simple. For any tree which is not a star, there are two disjoint edges (a,b) and (c,d). Consider an ordering of the edges in which these two are consecutive. Since these transpositions commute, we can reverse them without changing the product. So some cycles occur more than once, whence necessarily some occur not at all (since the average number of occurrences is 1.)

Problem Given a tree, what is the distribution of numbers of occurrences of cycles as products of its transpositions in some order?

For example, if T is the 4-vertex path, then of the six 4-cycles, two occur twice, two occur once, and two do not occur at all.

PS I am sure that once, while walking in England, I saw a sign saying “xxxx Forest: No cycles”; but I didn’t have a camera with me, and I can’t recall which forest it was.

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

Conference for Geoff Whittle

In 2013, when I retired from Queen Mary (my first, unsuccessful, attempt at retiring), Geoff Whittle came and spoke at the conference my colleagues organised for me. He is also someone who has appeared on these pages a few times.

Me and Geoff Whittle

So I have been very happy to return the favour. Even though Geoff’s field is matroid theory, where I haven’t made many contributions, there are very few mathematicians (indeed, very few people) in the world who are as much on my wavelength as Geoff; in the pub the evening before the conference we discovered that for both of us, our favourite poem is T. S. Eliot’s Four Quartets, that we resist reading what literary critics have to say about it, and that we have used snippets from it in describing mathematical processes.

I will say a bit about some of the talks at the conference, which I found very stimulating. I would like to discuss everything, but life is too short … Indeed, since I am not a matroid theorist, my selection will be a bit biased; perhaps a more balanced account will appear on the Matroid Union blog. (Matroid theorists admit that they are a small and closely-linked community; they all know the difference between James and Jim, for example.)

Day 1

James Oxley opened the meeting with a talk about Geoff’s early career. I met him fairly late on, and didn’t realise how many things he had done before settling down to work on Rota’s conjecture with Jim Geelen and Bert Gerards. Between school and university, he worked in various mines in Australia, and saved up money which he spent on travelling around South-East Asia; between undergraduate and PhD, he taught in a girls’ high school in Tasmania. The main function on the talk was the critical exponent of a matroid, and some of Geoff’s results and conjectures in this general area.

James described Tutte’s definition of a “tangential k-block”. Someone asked why he had called it that; James’ reply was that he couldn’t get inside Tutte’s head to see the geometric intuition behind the name.

Rob Goldblatt, who may have been the department chair when Geoff was appointed in Wellington, began with some reminiscences about the history of the department. In 1919, Duncan Sommerville (of Dehn–Sommerville equations fame) was the entire mathematics department in what was then Victoria College. (Later in the St Andrews History of Mathematics I found some more interesting things. Sommerville had been a student, and then a lecturer, at St Andrews before going to New Zealand; and he had tutored Alexander Aitken by correspondence after the professor of mathematics at Otago had a nervous breakdown. Among the links opened up here are the facts that Geoff Whittle was the inaugural Aitken lecturer, and one of the places on the itinerary of his lecture tour of Britain was St Andrews.) Rob made the very good point that matroid theory, especially in Geoff’s hands, maintains the Wellington tradition of excellence in geometry.

His talk was about mereotopology, a formulation of topology where the basic objects are regions rather than points. According to Wikipedia, this was invented by A. N. Whitehead, although Rob gave credit to the work of Lesnievski. The relation to the foundations of mathematics is that it is a first-order theory with a single binary relation on the set of regions, whereas topology is not first-order on points. The idea has been taken up by various computer scientists. To be specific, the elements are the “regular” closed sets, those which are the closure of their interior: these form a Boolean algebra, where join is as usual, meet is the closure of the interior of the intersection, and complement is the closure of the interior of the set-theoretic complement. The added binary relation describes “connection” (perhaps better described as “closeness”) of regions. The Stone duality between Boolean algebras and Stone spaces (compact Hausdorff 0-dimensional spaces) extends to a duality between BCAs and T0 mereocompact mereotopological spaces. I will spare you the definitions.

Here is a small plum from Petr Hlineny’s talk. Suppose that you have an oracle which tells you whether a given graph is 3-colourable. Can you use it to find an explicit 3-colouring in polynomial time? The answer is yes, and the trick is very simple: I will give it later.

Stefan van Zwam showed a nice theorem about the correspondence between binary matroids and binary codes. If a minor-closed class C of matroids contains (matroids corresponding to) an asymptotically good sequence of codes (that is, with both rate and minimum distance over length are bounded away from zero, then it must be the class of all binary matroids. (A similar result holds for representable matroids over any finite field, but we have to exclude the case that the class contains all matroids representable over the prime field.) The proof used two theorems of Kashyap proving the result for graphic and cographic matroids, and a theorem of GGW asserting that any minor-closed class of binary matroids has the property that its sufficiently connected members form a perturbation of the class of sufficiently connected graphic or cographic matroids.

Stefan showed a picture of Geoff among the examiners at his (Stefan’s) PhD defence in Eindhoven. I was interested to see, on the wall behind them, a picture of my good friend Jack van Lint, from whose book I learned Shannon’s theorem about the existence of asymptotically good codes.

Finally Gordon Royle talked about his attempts to find the excluded minors for the class of graphs with contraction degeneracy at most 4, a problem which seems to be just out of reach at present but has connections with real chromatic and flow roots of graphs. He began by showing a conference photograph containing many people who were either here or well known to some of us, and identified it as the ACCMCC in Taupo in 2004.

Day 2

Charles Semple, Geoff’s first student, began the day’s proceedings with a talk mostly concerned with the question: for which sets of fields can a matroid be representable over just those fields, and can we describe the matroids? A sample theorem: a matroid is representable over GF(3) if and only if it is representable over GF(3) and GF(q) for some q in the set {2,4,5,7,8}.

By the end of his talk, we had met another theorem asserting that every flower is either an anemone or a daisy. (I am not quite sure, but you might have to exclude some “ground-dwelling junk”.)

Will Critchlow bravely tackled the question of what a random matroid looks like. It is thought that most rank r matroids on n points are sparse paving matroids: these are matroids in which every circuit has cardinality r, and any two circuits meet in at most r−2 points. Thus, the collection of circuits (which specifies the matroid) is an independent set in the Johnson graph J(n,r), a graph well known to association scheme theorists: the vertices are the r-subsets of an n-set, two vertices joined if they intersect in r−1 points.

The Johnson graph has large independent sets. Graham and Sloane, following a suggestion of Knuth, observed that, if the vertex set is {1,…,n}, then the collection of r-sets with sum congruent to k (mod n) is an independent set, so there is some independent set whose size is at least a fraction 1/n of the number of vertices in the graph. A sparse paving matroid is of GS type if its circuits form a subset of an independent set of this form, for some ordering of {1,…,n}. There are many such matroids but whether they predominate in an enumeration is not clear.

Mike Newman told us about the non-existence of axioms for representable matroids. This is a question which some people think that Peter Vamos solved, but in fact he didn’t; the axioms for a matroid are monadic second order, and so it is only reasonable to ask if there is a monadic second order axiom for representability. Mike, with Dillon Mayhew and Geoff Whittle, have shown by an ingenious argument that there is not. This involves looking carefully about what a monadic second order axiom can actually say about a matroid, and showing that for any such axiom there are representable and non-representable matroids which it does not distinguish.

Carolyn Chun talked about delta-matroids. Briefly: a ribbon graph is a structure equivalent to a graph embedded in a surface. (Fatten up each vertex of the graph to a small disc, and each edge to a small strip. These are more general than graphs since edges may be twisted.) Now a quasi-tree in a ribbon graph is a subgraph with only one boundary component. Just as the spanning trees in a graph are the bases of a matroid, so the quasi-trees in a ribbon graph are the “feasible sets” in a structure called a delta-matroid. There are many connections with matroid theory, and Carolyn made the subject look very attractive; but I won’t attempt to say more.

Day 3

After three beautiful days, the rain came this morning; no sunlight sparkling on the harbour or blue mountains on the other side.

The first talk was by Jim Geelen, one of the three knights who had succeeded in their quest for the Holy Grail, the proof of Rota’s conjecture. The conjecture asserts that, for any fixed finite field F, the (minor-closed) class of matroids representable over F is defined by a finite number of excluded minors. The quest took not too far short of twenty years, and is a massive piece of work. Jim described very well the highs and lows of the enterprise which he, Bert Gerards and Geoff Whittle underwent. One small example: the three-way collaboration arose when Jim was at the Fields Institute and had double-booked, inviting the other two to come and work with him in the same week; the only way he could achieve that was to get all three to work together, showing that the set of F-representable matroids of bounded branch-width is well-quasi-ordered. (A false lead, as it turned out, but it stoked their enthusiasm for a structure theorem for representable matroids, extending the Robertson–Seymour theory for graphs, which they achieved in 2010.

Next, Henry Crapo talked about another Rota conjecture, his basis conjecture. This asserts that, in a matroid of rank r, if we take any r bases (not necessarily distinct), then we can order them so that, when we take them as the rows of a matrix, the columns also form bases. (This is unknown even in the linear algebra context.) He first observed that the converse is true: if a set of r-element sets has this property then it is the set of bases of a matroid. (We only need the property for r-tuples of the form (A,A,…,A,B). For suppose the property holds for such a tuple. The first r−1 rows of the matrix form a partial Latin square, which can be completed uniquely to a Latin square; the correspondence from the last row of this square to the last row of the given square is a map from A to B which shows the exchange axiom for A and B. Henry thinks the conjecture is true, but had been using the computer to look for counterexamples, so far without finding any.

A cyclic flat in a matroid is a flat which is a union of cycles. Unlike most matroid concepts (bases, circuits, flats, rank function), the cyclic flats do not determine the matroid uniquely. However, they form a lattice of subsets of the ground set, and with the extra information about the rank of each of these sets, the matroid is determined. Bonin and de Meir have given axioms for a matroid in terms of its cyclic flats and their ranks. Kadin Prideaux told us about work in progress: given a lattice of subsets of a set, can we determine the possible ranks for which they form as the lattice of cyclic flats of a matroid? The axioms give a bunch of linear inequalities for the values, and so determining them is an integer programming problem. Sad to say, the admissible polytope can have non-integral vertices, so the job won’t be easy.

(Unfortunately, he went through the definition of a cyclic flat very quickly, while I was still making notes on his first slide, so I missed it, and had to look it up later.)

After lunch, there were just two talks. Rod Downey told us about using logic to investigate invariants (in a very general extent: Ulm invariants, homotopy groups, etc.) He ranged from Shelah’s dichotomy theorem (announced by an abstract entitled “Why I am so happy”), through Borel equivalence and reductions, to computational classification and the arithmetic and analytic hierarchy. A natural problem in the classification theory of torsion-free abelian groups lies, remarkably, on level 7 of the arithmetic hierarchy.

Rod also claimed that Geoff continued Wellington’s strong tradition in logic. I think both his statement and Rob Goldblatt’s are correct.

Dillon Mayhew closed the meeting with a talk on some early work of his with Geoff about the number of inequivalent representations of a 3-connected matroid with no U3,6 minor. One slightly remarkable thing was that in looking over his slides at lunchtime he had found an error in the proof, which he had managed to fix on the spot.

And so the conference closed, and we drifted off.

Postscript

Here is the solution to Petr Hlineny’s puzzle: given an oracle for 3-colourability, find a 3-colouring.

First, of course, check with the oracle that the graph is really 3-colourable. Then add an edge not already present in the graph, and ask the oracle if this graph is 3-colourable. If it says “yes”, leave the edge in and repeat the step. If it says “no”, remove the edge but note that its ends must have the same colour in any 3-colouring. As the process proceeds, we are approaching a complete 3-partite graph from below (with the edges present) and above (with the information on the partition).

The trick can be adapted to other situations: can you think of any?

Posted in events, exposition | Tagged , , , , , , , , , , , , , , , | 2 Comments