I have just come to the end of the longest uninterrupted sequence of conferences I have ever had: five in a row, one of them a two-week conference. Since the start of July I have been at conferences in Egham, Mile End, Durham, Prague, and St Andrews. Now I can begin to catch my breath until I am off to Belfast in September.
One of the features of the Durham symposium was a beautiful series of lectures by Dan Král’ on the relatively recent type of graph limits introduced by Lovász and others, called graphons. Dan began with a simpler case, namely permutons, or limits of permutations. Here “permutations” are not the algebraic objects, namely bijections from a set to itself, that I am used to; the word is used in the sense of the theory of permutation patterns, so that a permutation is a sequence consisting of the numbers 1,2,…,n in some order, and a permutation σ of length m occurs in a permutation π of length n if m ≤ n and we can choose m of the entries of π which come in the same relative order as the entries of σ. Thus, 132 occurs in 42513 because the entries 2, 5, 3 of the latter permutation come in the same relative order as 132 (smallest first, largest second).
[As an aside, a permutation in this sense is a finite set with two distinguished orders on it: the first is used to match up the set with {1,2,…,n}, and then the second to put these values in order. Then the notion of containment is clear – it is just induced substructure – and the extension to the infinite is also clear.]
Having warmed up with the relatively simple case of permutons, he then gave us a detailed and clear exposition of the more complicated theory of graphons.
So now, at least in the case of graphs, we have now three competing notions of limit. I will discuss the simple case of all finite graphs, and the more complicated case of all finite triangle-free graphs.
First, a limit should be a countable object with nice properties, which contains all the finite objects in a nice way. This is what Fraïssé’s theory of amalgamation classes does. The limit for the class of all graphs is the countable “random graph” or Rado graph R, and the limit for the class of triangle-free graphs is a graph discovered by Henson (as one of an infinite family) and denoted by H3.
The name “random graph” hints at a second feature of this limit, related to probability. We can define a way of choosing a random graph on a countable vertex set by choosing edges independently with fixed probability p (not 0 or 1); then the resultant graph will be R with probability 1. I have discussed this at some detail in a series of posts starting here.
Things are not so simple for triangle-free graphs. It is a basic fact that almost all finite triangle-free graphs are bipartite, so any attempt to define a random triangle-free graph based on looking at finite subsets is likely to give a bipartite graph (which cannot contain all triangle-free graphs, and is certainly not Henson’s graph). One way round this is to replace the probability in the construction by the notion of Baire category; then Henson’s graph is indeed obtained.
A completely different notion of graph limit was introduced by Lovász and his co-workers. A graphon is a (measurable) function W from the unit square to the unit interval. To choose a finite random graph from a graphon, we sample n independent points from the unit interval; if xi is the ith point chosen, then we join the ith and jth vertices with probability equal to W(xi, xj).
Thus the Erdős–Rényi “random graph” model corresponds to the graphon W given by W(x, y) = p for all x,y.
Dan explained very clearly in his lectures what this had to do with “convergent sequences” of finite graphs, where “convergent” means that for any fixed graph H, the proportion of subgraphs of the graphs in the sequence which are isomorphic to H tends to a limit. (In the original approach, “homomorphism densities” were used; Dan replaced these by the simpler notion of “subgraph densities”.)
This is a very general and flexible construction for graphs, with many useful properties. Moreover, it combines well with Razborov’s flag algebra method to facilitate proving new results in extremal graph theory. However, it seems to me that the theory requires complete rewriting for each new class of structures. In Dan’s lectures, a permuton was conceptually quite a different thing from a graphon, even though their beautiful properties were very similar.
That leads me to the third approach, due to Petrov and Vershik in the case of triangle-free graphs. I described here how I spent a very pleasant afternoon with Anatoly Vershik in Penderel’s Oak (a pub in central London) while he explained to me how they had constructed an exchangeable measure on the class of countable triangle-free graphs which is concentrated on graphs isomorphic to Henson’s graph. This is the exact analogue of the work of Erdős and Rényi on the ordinary random graph. Moreover, their method has been extended by Ackerman, Freer and Patel to a very wide class of structures, namely, all amalgamation classes having trivial algebraic closure (this means that, when two finite structures are amalgamated, it is never necessary to make any identifications apart from the ones specified in the amalgam.
The remarkable thing is that, as in the case of graphons, a structure is first built on the unit interval; then a random countable structure is obtained by sampling points from the unit interval.
I am certain that there is a very close connection between these methods. It should be the case that the third method will enable the construction of analogues of “graphons” for very wide collections of structures, while techniques from the second method will enable extremal graph theory to be pushed to a much wider variety of situations.
What I would really like to see is how to use either of these two methods to achieve some things that have only been done with the first method: the connection of homogeneous structures with such areas as Ramsey theory and topological dynamics (extremely amenable groups). More specifically, one of my first ventures into the infinite was showing that the random graph is a Cayley graph for a very wide collection of countable groups (indeed, it is “the random Cayley graph” for these groups). Can the other techniques throw light on this problem for other kinds of structures apart from graphs?
So, of course, I have offered to talk about Cayley objects at the Belfast conference, in the hope that it will prod me into thinking more deeply about the connections.
Peter Cameron's Blog 
Maybe one distinguishing feature of a Fraisse limit is that it doesn’t (for obvious reasons) come with any measure, any idea of how big this subgraph is or how often it shows up – which is fine for some things but a disadvantage to people wanting to ask quantitative things.
The Razborov flag algebra notion is something you should probably think of as a fourth `competing’ limit model. If you have a sequence of graphs then they are convergent in Razborov’s model if the H-homomorphism density sequences converge for all H (you can as Dan did replace homomorphism with subgraph). Obviously there is nothing graph-specific here, you can replace graph with hypergraph or any other structure here (though defining density may be tricky for some structures). The limit object is then just the infinite vector of limit densities, and the proof that this makes sense is trivial – Prokhorov’s theorem, which is just compactness, and works for any structure.
The connection between Razborov and graphons is that Lovasz and coauthors proved that for graphs there happens to be a `nice’ object from which you can read off the vector of limit densities, namely the graphon which one can naturally think of as looking like a graph (Of course Lovasz et al didn’t know Razborov when they started their work) and that object can be given as a natural limit of the Szemeredi partitions of the graph sequence. Of course, you would like to say that this sort of thing will always happen, but the reality is that Nature is not so nice. Elek and Szegedy found the correct graphon-type limit object for k-uniform hypergraphs, which you can get naturally from the hypergraph regularity lemma and from which you can read off the vector of limit densities, but this object does not look like a k-uniform hypergraph (and in some sense it cannot). This is a problem, and arguably the best solution is to say that you should stop asking Nature for `nice’ limit objects as they typically don’t exist, and rather deal with what Nature gives you, namely the limit densities. But of course there are algebraic relations between these densities (this is what lies behind the applications of the flag algebra method) which put you back into some setting of trying to find at least a nice algebraic object which represents the collection of limit objects which you can achieve (Obviously you cannot achieve edge density zero and triangle density one, or vice versa..!) – this is a big project of Balasz Szegedy, but even for much simpler objects than graphs it seems to be very hard.
I don’t know what the connection between Petrov-Vershik and these limit notions is – it would be interesting to understand better.
Thanks for these comments.
You are right that Fraisse limit doesn’t see densities. In some sense, measure is not the right tool there; rather, one should use Baire category. These are tantalisingly similar ways of saying “almost all”, but don’t always agree; Baire category gives Henson’s graph as the almost-everywhere limit of finite triangle-free graphs, while measure gives the generic bipartite graph. Also of course Baire category lacks the ability to give numerical values between zero and one, and of course this is what extremal combinatorics needs. On the real line the null sets and meagre sets are isomorphic by an involution (the Sierpinski-Erdos theorem); it would be nice to know what contexts have a similar isomorphism.
Plenty to think about here!