Rado Graph ( “The Random Graph”)

Rado graph is a graph on countable number of vertices wtih an extension property. For any two disjoint finite subsets of vertices, there is a vertex connected to all the vertices in first subsets and not connected to any of the vertices in the second subset. It can be seen that any two graph with extension property have to be isomorphic. ( We can sequentially construct the isomorphism by looking at the finite portions of the graph. Start with an isomorphism on some subsets, we can extend to a new vertex precisely because of the extension property. We can make sure that the map is onto by doing the extension in a zig-zag (“back and forth”) manner – extend to a new vertex on one side, and then a new vertex on another side) The extension property helps to see that any finite or countable graph is contained in the Rado graph as an induced subgraph.

The above argument shows that there is a unique Rado graph provided it exists. What about the existence?

Constructions:

Ackermann’s construction: The graph is on non-negative integers. Put an edge between $x <y$ , if the binary expansion of $y$ is non-zero at the position $x$ . For instance, all odd numbers are connected to $0$ , because their last $0$ th bit is non-zero. And $1$ is connected to 0, plus all the numbers with non-zero first bit, hence numbers of the form $4k+2, 4k+3$ . The extension property is obvious- just construct a number with zeros and ones at the positions given by the two subsets of vertices respectively to make sure it’s connected completely to only one subset.
Random Graph: Take a random on a countable set by adding an edge between any two vertices independently with probability $1/2$ . This graph with probability $1$ has extension property. This models helps us to see that removing few edges from a Rado graph gives isomorphic copy. Or that the complement of Rado graph is also Rado graph. In general, if we switch between edges and non-edges between a finite set and it’s complement, we still get a Rado graph. We can also see that every countable graph is contained in Rado Graph
Direct construction: Start with a empty graph and inductively add vertices that satisfy extension property for every pair of subsets of the current graph.
Paley Graph: The graph is on primes which are $1 \mod 4$ , and connect two primes $p, q$ , if $\left( \frac{p}{q}\right) =1$ , that is one prime is a square modulo other prime. (By quadratic reciprocity, this is a symmetric relation for primes which are 1 modulo 4). The extension property follows from Chinese remainder theorem and prime number theorem in arithmetic progressions (actually just the fact that there are infinitely many primes in arithmetic progressions).
Circulant Graph: Choose a random subset $S$ of non-negative integers. Now connect two integers if their distance is an integers from $S$ . We can also make this deterministic by taking the indicator function $S$ to be concatenation of all finite binary strings. The property of $S$ we want is universality– we want every finite binary string to appear inside the indicator function of $S$ . Concatenation is just one way to obtain it, random subsets have the universal property with probability one.
Infinite Design: Take a design on a countable set with countable block sizes such that for every two elements $x, y$ , they are both contained in $2^{\aleph_0}$ many blocks, they are both not contained $2^{\aleph_0}$ many blocks, $x$ is contained, but $y$ is not contained in $2^{\aleph_0}$ many blocks, similarly $y$ is contained, but $x$ is not contained in $2^{\aleph_0}$ many blocks. The intersection graph is the Rado graph.
Fraisse Limit: The Fraisse Limit of all finite graphs is the Rado graph, that is it a canonical way to put all the finite subgraphs together to form a countable graph. For instance, if we have a isomorphism of two finite subgraphs, it extends to automorphism of the total graph.
Countable Model of Set Theory: By Skolem paradox, there is a countable model of set theory. Now join two sets in model by an edge if one is contained in another. If $\left \{A_1, A_2, \cdots A_k\right\}$ and $\left \{B_1, B_2, \cdots B_l\right\}$ are two disjoint collections of sets. Then the set $C= \left\{ A_1, A_2, \cdots A_n, \left\{B_1, B_2, \cdots B_l \right\} \right\}$ is connected to the sets $A_i$ . But is not connected to any of the $B$ ‘s because if it was connected either we have $B$ is contained in $C$ and hence equals $A_i$ or $\left\{B_1, B_2, \cdots B_l \right\}$ , or $C$ is contained $B$ . $B$ is not $A_i$ because the vertices are disjoint, and it cannot equal $\left\{B_1, B_2, \cdots B_l \right\}$ because we assume in (standard) set theory the foundation axiom that $x \not in x$ . If $C$ is contained $B$ , then $\left\{B_1, B_2, \cdots B_l \right\} \in C \in B \in \left\{B_1, B_2, \cdots B_l \right\}$ which is also not possible by foundation.

Properties:
1. Contains every countable/finite graph as induced subgraph. But the subgraphs need not be spanning, that is needn’t be obtained by just removing some edges on the same set of vertices, like for instance the complete countable graph is not a spanning subgraph.
2. For any two finite susbets of vertices of the Rado graph, the set of vertices that satisfy the extension property is itself an infinite set who induced subgraph is isomorphic to the full graph.
3. Using (2) we can see that we can always delete a few vertices and still have the extension property
4. We can also alter a finite number of edges again because of infinitude of vertices that extend a given pair of subsets.
5. We can switch edges and non-edges between any finite subsets and it’s complement and still get isomorphic (the extension property can be easily verified, or from random graph model makes this is obvious)
6. Pigeon hole: For any finite partition of the vertices of graph, there is a part which induces an isomorphic copy. In fact, the complete graph, empty graph and the Rado graph are the only countable graphs with this pigeon hole property.
7. First order Theory: If a first order statement in graphs is true for the Rado graph, it’s true for almost all finite graphs of any fixed size.

Share this:

Related

Leave a comment Cancel reply