BCC, day 4

The highlight of the conference for me was the talk this afternoon by Manuel Bodirsky, on Ramsey classes.

No time now to explain all this – get the invited speakers’ volume and read it if you want to know – but let me just say one thing. This is a subject I thought I knew quite well, but Manuel answered one question that had puzzled me.

One of the earliest results about Ramsey classes of relational structures was that the structures in such a class must be rigid (have no non-trivial automorphisms). The usual way this is achieved is to assume that one of the relations is a total order, since finite total orders are rigid. But there are other ways to make structures rigid. For example,

  • a finite C-relation derived from a binary tree has the property that its automorphism group is a 2-group;
  • a tournament has the property that its automorphism group has odd order.

So, if we impose both of these relations, our structures will be rigid. Why cannot Ramsey classes be made this way?

The answer, it turns out, comes from the Kechris–Pestov–Todorcevic theorem, which asserts that a homogeneous structure has automorphism group which is extremely amenable (that is, every continuous action on a compact Hausdorff space has a fixed point) if and only if the amalgamation class of its finite substructures is a Ramsey class. This theorem is usually applied to known Ramsey classes to provide examples of extremely amenable groups. But here we use the KPT theorem the other way round.

Suppose that the age of a countable homogeneous structure M is a Ramsey class. Then the automorphism group of M is extremely amenable. Consider the “logic action” of Aut(M) on the set of all linear orders of the ground set. This is easily seen to be a continuous action on a compact Hausdorff space. So, since the group is extremely amenable by the KPT theorem, it must fix a linear order!

Out of the rest of the day, let me just pick out the talk by Terry Griggs on the combinatorics of the sonnet. A sonnet is a 14-line poem, invented in Italy but taken up by English (and Scottish) poets. Terry wanted to count the number of rhyme schemes possible in a sonnet, using the rules laid down in the Oxford Companion to English Literature. A sonnet is made up of an octave of 8 lines followed by a sestet of 6 lines. Various forms of rhyme scheme were used by Petrarch, Shakespeare, Spenser, and others. The common denominator seems to be that the octave is divided into two quatrains each of which contains two pairs of rhymes (three possibilities for each), while the sestet should have two or three rhymes. We can assume that the sestet splits as 2+2+2 or 3+3, since 2+4 is a specialisation of 2+2+2; so there are 15+10=25 possible rhyme schemes, for a total of 3×3×25 = 225 altogether.

Terry then looked at one of his favourite poets, John Clare, who actually broke the rules quite dramatically.

I once constructed a Petrarchian sonnet, out of first lines of sonnets by more famous poets, which you can find here.

Then Terry looked at the specialisation of 2+2+2 to 2+4, and considered the graph whose vertices are the patterns of either shape, joined if the second is a specialisation of the first. This bipartite graph is Tutte’s 8-cage, otherwise known as the generalized quadrangle of order 2, which is related to the outer automorphism of S6.

Then he generalised this pattern to see whether the graph obtained similarly from rhyme schemes with n rhymes each occurring r times, and the specialisation when two of the rhymes are equal, can be regular. Regularity is equivalent to the diophantine equation

n(n−1) = (2r)!/(r!)2.

Terry remarked that this equation has three known solutions apart from the trivial n = 2, r = 1: there is one with n = 3, r = 2 (corresponding to Tutte’s cage); one with n = 5, r = 3; and one with n = 221, r = 9. The graph corresponding to the last solution has rather a large number of vertices and has not been investigated.

Terry ended by remarking that the finiteness of the set of solutions of the diophantine equation might follow from a proof of the ABC conjecture, though this has not been demonstrated, and Terry is reluctant to try until the status of the conjecture becomes clearer. (This is one of the really big open problems in number theory, implying among other things Fermat’s last theorem.)

We had a second problem session, followed by an enjoyable dinner.

Advertisements

About Peter Cameron

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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