MATH 557 Oct 17

Fraïssé Theory of Random Graphs

Key facts from Fräissé theory

To simplify things, we state everything in the context of a finite language that contains only constants and relations. In this case finitely generated is equivalent to finite.

  • \(\mathcal{M}\) is homogeneous if any isomorphism between finite substructures of \(\mathcal{M}\) can be extended to an automorphism of \(\mathcal{M}\).
  • \(\mathrm{age}(\mathcal{M})\) is the class of all finite \(\mathcal{L}\)-structures isomorphic to a substructure of \(\mathcal{M}\).
  • Any two countable homogeneous structures with the same age are isomorphic.
  • A class of finite structures \(\overline{K}\) is an amalgamation class if it satisfies (HP), (JEP), and (AP). In words, every substructure of a structure in \(\overline{K}\) is in \(\overline{K}\), any two structures in \(\overline{K}\) embed into another structure from \(\overline{K}\), and any two structures with a common substructure (up to isomorphism) amalgamate to another structure that preserves the common substructure.
  • Fraïssé’s Theorem: Suppose \(\overline{K}\) is a class of finite \(\mathcal{L}\)-structures such that there are only countably many isomorphism types in \(\overline{K}\). Then \(\overline{K}\) is an amalgamation class iff \(\overline{K}\) is the age of a countable homogeneous \(\mathcal{L}\)-structure.

Simple graphs

We consider the theory of undirected graphs without self-loops, also called simple graphs. Let \(\mathcal{L}_G = \{E\}\) be the language of graphs with one binary relation symbol \(E\).

Simple graphs are formalized by the axioms

  • \(\forall x \neg E(x,x)\)
  • \(\forall x, y \: (E(x,y) \to E(y,x))\)

We denote the theory of simple graphs by \(T_{G}\)

Exercise 1 Verify that \[ \overline{K} = \{\mathcal{G} : \mathcal{G} \models T_G, \mathcal{G} \text{ finite}\} \] is an amalgamation class with countably many isomorphism types.

It follows that \(\overline{K}\) has a Fraïssé limit. What does this limit look like?

Random graphs

We add the following extension axioms:

\[ \sigma_{n,m} \equiv \forall x_1, \dots, x_n \forall y_1, \dots, y_m \; \left ( \bigwedge_{i=1}^n \bigwedge_{j = 1}^m x_i \neq y_j \; \to \; \exists z \: \bigl ( \bigwedge_{i=1}^n (z \neq x_i \land E(z,x_i) ) \land \bigwedge_{j = 1}^m (z \neq y_j \land \neg E(z, y_j)) \bigr ) \right ) \]

Let \[ T_{RG} = T_G \cup \{ \exists x,y \: (x \neq y) \} \cup \{ \sigma_{n,m} : n, m \geq 1 \} \]

Exercise 2 Show that every countable model of \(T_{RG}\) is homogeneous.

Exercise 3 Show that if \(\mathcal{R}\) is a model of \(T_{RG}\), \(\operatorname{age}(\mathcal{R}) = \overline{K}\).

It follows from Fraïssé’s Theorem that \(T_{RG}\) has a countable model \(\mathcal{R}\), and that this model is unique up to isomorphism.

Exercise 4 Show that \(T_{RG}\) is complete.

\(\mathcal{R}\) is called the random graph and \(T_{RG}\) the theory of the random graph. Why? Let \(G_N\) be the set of all simple graphs on the vertex set \(\{1, \dots, N\}\). Put a probability distribution on \(G_N\) by giving every graph the same probability. (Alternatively, we could independently assign edges to any vertex pair with probability \(1/2\). This is called the Erdös-Renyi model.) Given an \(\mathcal{L}_G\)-sentence \(\sigma\), let \(\mathbb{P}_N(\sigma)\) be the probability that \(\sigma\) holds for a random graph in \(G_N\), i.e.

\[ \mathbb{P}_N(\sigma)= \frac{|\{ \mathcal{G} \in G_N : \mathcal{G} \models \sigma\}|}{|G_N|}. \]

It turns out, for large \(N\), graphs will satisfy the extension axioms with high probability.

Exercise 5 Show that for any \(n, m \geq 1\),

\[ \lim_{N \to \infty} \mathbb{P}_N(\sigma_{n,m}) = 1. \]

This justifies referring to \(\mathcal{R}\) as the random graph, since it can be seen as the “limit” of finite random graphs.

Further explorations

0-1 law for graphs

Theorem 1 For any \(\mathcal{L}_G\)-sentence \(\sigma\),

\[ \text{either } \lim_{N \to \infty} \mathbb{P}_N(\sigma) = 0 \text{ or } \lim_{N \to \infty} \mathbb{P}_N(\sigma) = 1. \] Moreover, \(T_{RG}\) axiomatizes the theory \[ \{ \sigma : \lim_{N \to \infty} \mathbb{P}_N(\sigma) = 1 \} \] and this theory is complete.

To prove the theorem, use that \(T_{RG}\) is complete together with Exercise 5. Give it a try!

Other Fraïssé classes

There are other classes of structures that are amalgamation classes, for example:

  • finite fields of characteristic \(p\)
  • finite groups
  • (non-trivial) finite Boolean algebras

What kind of object is the Fraïssé limit in each case?