### Fraïssé Limits

#### Posted by David Corfield

The Rado graph, or *random graph*, seems to be an extraordinary entity. Take countably many nodes, then for each pair of nodes flip a coin and if it shows heads, draw an edge between them. Almost surely you will have generated the Rado graph, $R$.

Any finite graph (and indeed any countable graph) is contained in $R$, not just in the sense of being embeddable, but in the sense of being an induced subgraph, that is, it is the full subgraph on a subset of nodes. Along with this *universality*, $R$ is also *homogenous* in the sense that any isomorphism between finite induced subgraphs extends to an automorphism of all of $R$.

$R$ is very robust, you can delete finitely many vertices, add or remove finitely many edges, or interchange edges and non-edges, and you still end up with a graph isomorphic to $R$. Furthermore, the odd thing about the construction of this graph is that I didn’t have to tell you the probability $p$ of the coin showing heads. So long as $p$ is in $(0, 1)$ and the tosses are independent, the Rado graph almost surely emerges.

Not only this, there are many ways to generate it without using random devices. Rado himself took the nodes to be the natural numbers, and an edge between $m$ and $n$ whenever either the $m$th bit of the binary representation of $n$ is nonzero, or the $n$th bit of the binary representation of $m$ is nonzero. Yet another method has us take as nodes the prime numbers equal to 1 mod 4. Then we join $p$ and $q$ if they are quadratic residues of each other.

I find myself interested in $R$ because it is an example of a Fraïssé limit. This is nicely explained in Artem Chernikov’s slides – What is…Fraïssé construction? We want a countable category, $K$, of finitely generated structures (for a countable signature) whose morphisms are embeddings, which satisfies the three properties:

- Hereditary: if $A$ embeds into $B$ and $B$ is in $K$, then so is $A$.
- Joint embedding property: for any $A, B \in K$, there exists a $C \in K$ and morphisms $A \to C \leftarrow B$.
- Amalgamation property: for arrows $f: A \to B, g: A \to C$ in $K$, there exist $r: B \to D$ and $s: C \to D$ in $K$, such that $r \circ f = s \circ g$.

So now some questions: Can this kind of limit be given a natural category theoretic description? Is it related to any of the completions we have listed here? It seems to be a kind of Ind-completion, pretty close to an ideal completion. Can we understand the homogeneity category theoretically?

I should imagine I need to get a look at this thesis – Trevor Irwin, Fraïssé limits and colimits with applications to continua:

The classical Fraïssé construction is a method of taking a direct limit of a family of finite models of a language provided the family fulfills certain amalgamation conditions. The limit is a countable model of the same language which can be characterized by its (injective) homogeneity and universality with respect to the initial family of models. A standard example is the family of finite linear orders for which the Fraïssé limit is the rational numbers with the usual ordering.

We present this classical construction via category theory, and within this context we introduce the dual construction. This respectively constitutes the Fraïssé colimits and limits indicated in the title. We provide several examples.

We then present the projective Fraïssé limit as a special case of the dual construction, and as such it is the categorical dual to the classical (injective) Fraïssé limit. In this dualization we use a notion of model theoretic structure which has a topological ingredient. This results in the countable limit structures being replaced by structures which are zero-dimensional, compact, second countable spaces with the property that the relations are closed and the functions are continuous.

We apply the theory of projective Fraïssé limits to the pseudo-arc by first representing the pseudo-arc as a natural quotient of a projective Fraïssé limit. Using this representation we derive topological properties of the pseudo-arc as consequences of the properties of projective Fraïssé limits. We thereby obtain a new proof of Mioduszewski’s result that the pseudo-arc is surjectively universal among chainable continua, and also a homogeneity theorem for the pseudo-arc which is a strengthening of a result due to Lewis and Smith. We also find a new characterization of the pseudo-arc via the homogeneity property.

We continue with further applications of these methods to a class of continua known as pseudo-solenoids, and achieve analogous results for the universal pseudo-solenoid.

Available treatments include Wieslaw Kubiś, Fraisse sequences - a category-theoretic approach to universal homogeneous structures:

We present a category-theoretic approach to universal homogeneous objects, with applications in the theory of Banach spaces and in set-theoretic topology,

and Olivia Caramello, Fraïssé’s construction from a topos-theoretic perspective:

We present a topos-theoretic interpretation of (a categorical generalization of) Fraisse’s construction in model theory, with applications to countably categorical theories.

## Re: Fraïssé Limits

Hi

This seems like a nice construction. You say:

Does this mean “the Rado graph emerges up to graph isomorphism” as suggested in the Wikipedia article, or are you suggesting some probability of occurrence?