Measuring triangle-free graphs

Anatoly Vershik is almost certainly the nearest thing to a universal mathematician that I know. The range of his interests is impossible to summarise: logic, algebra, combinatorics, analysis, probability, dynamical systems, mathematical physics, …

I first met him in 2000, at the European Congress of Mathematics in Barcelona. I was a section speaker in Combinatorics, and talked about one of my favourite topics, the random graph. After the talk, Anatoly introduced himself to me and told me about the Urysohn space, a complete separable metric space with properties similar to those of the random graph (but discovered nearly half a century earlier). Later we wrote a paper about this beautiful object, applying some of the techniques I had used to investigate automorphisms of the random graph. It seems that our work has had some impact already.

Last Saturday I spent a happy afternoon with him in Penderel’s Oak, a nice pub near Holborn in central London. Among a lot of mathematics that we exchanged, he told me that he and Fedor Petrov had managed to do something that I had never succeeded in doing: they found a probability measure on the set of graphs on a countable vertex set which is exchangable (invariant under all permutations in the symmetric group) and concentrated on Henson’s universal triangle-free graph.

As I have explained here, most finite triangle-free graphs are bipartite, so if you try to pick a random triangle-free graph by a finitary method (building it up a bit at a time) in a way which is not biased towards a particular ordering of the vertices, there is a very strong tendency for the infinite graph you get to be bipartite. So Petrov and Vershik instead “come down from above”. First, with a great deal of ingenuity, they build a topological or measure-theoretic triangle-free graph on the real numbers. (This means that triangles don’t have to be completely banned, as long as the chance of getting one is zero; similarly, the universality axioms are not reqired to hold universally, only with high probability.) Then they get a countable graph by taking countably many independent samples from a probability distribution on the real numbers. The actual distribution used is not so crucial; a Gaussian distribution will do. The resulting graph is isomorphic to Henson’s graph with probability 1.

They do more: using a theorem of Aldous on exchangeable measures (which I described in the earlier post), they are able to characterise completely all measures with the required property. I imagine that this could be used to decide whether a finitary approach is really doomed to failure; Anatoly thinks that it is.

What I really wanted a measure concentrated on Henson’s graph for was to find out more about the graph itself. The paradigm is the proof that the random graph has uncountably many nonconjugate cyclic automorphisms. To show this, choose a random set S of positive integers, and build the graph whose vertices are all the integers, two vertices joined if their difference belongs to S. With probability 1, this graph is isomorphic to the random graph, and it admits the cyclic shift as an automorphism. Moreover, a simple argument shows that different sets S give nonconjugate automorphisms. Can anything similar be done for Henson’s graph? In the end I was able to succeed, using Baire category in place of measure; but I would still hope that the measure theory might do something!

The reason for Vershik’s presence in London was that, like me, he was on his way to a London Mathematical Society workshop on homogeneous structures in Leeds. At this workshop, we heard a beautiful pair of talks by Rehana Patel and Cameron Freer. They, with Nate Ackerman, had achieved this. Choose your favourite countably infinite structure M. Is there an exchangeable measure concentrated on the structures isomorphic to M? They give a necessary and sufficient condition. If you have followed me this far, you might like to stop and guess what the condition is before reading on.

It is a symmetry condition, expressed in terms of the automorphism group of M. It is precisely the following: the stabiliser of a finite number of points in Aut(M) doesn’t fix any additional points. This is more or less what logicians would express by saying “definable closure is trivial”. For example, it holds for the random graph, or for the rational numbers as ordered set, but not for an infinite path or tree (where the stabiliser of two points fixes every point in the interval joining them).

The proof involves a preliminary logical manoeuvre, involving a logic stronger than first-order, namely Lω1,ω, where infinite conjunctions and disjunctions are allowed, but only finite quantifications. In this logic, the countable structure M can be characterised by a Scott sentence, in much the same say that a finite structure can be characterised by a single sentence of first-order logic. The condition on the automorphism group shows that any point outside a finite set A can be “cloned”, that is, there is another point of the same type; this is used in the construction. From then on they follow Petrov and Vershik: they construct a topological version of the structure in the real numbers, and then sample countably many independent reals from a fixed distribution and take the induced substructure.

The reason that this beautiful result disappoints me slightly is that it is too general. I can imagine that a measure concentrated on the Henson graph would tell us something about that graph; but since we can do this for such a very wide class of structures, it seems rather unlikely that we can prove a strong result about all of them!

There was far more than just this at what was an extremely enjoyable workshop. Many thanks to John Truss for organising it, and the London Mathematical Society for funding it.


About Peter Cameron

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

2 Responses to Measuring triangle-free graphs

  1. Pingback: Weekly Picks « — the Blog

  2. Pingback: More Continuous Logic | jamesfreitag

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