The finite partition of a random graph has an element that is a random graph

Question

I want to show that in the finite partition of a random graph there is a random graph. I am not really sure how to do this. I think I need to show that a subset of a random graph satisfies the theory of a random graph, but I am very confused as to how to proceed.

Answer 1

I guess the "random graph" you're referring to is the countably infinite random graph aka the Rado graph, which is characterized up to isomorphism as a (simple undirected) countable graph $G=(V,E)$ with the property that, for any disjoint finite sets $X,Y\subseteq V$, there is a vertex $v\in V\setminus(X\cup Y)$ which is joined to every vertex in $X$ and to no vertex in $Y$. (This condition will be satisfied with probability one if we take a countably infinite set of vertices and for each pair of vertices let an independent fair coin toss decide whether to join them with an edge.)

I guess the partition theorem you want to prove is the following: If $G=(V,E)$ is the Rado graph, and if $\{V_1,\dots,V_n\}$ is any partition of the vertex set $V$ into finitely many parts, and if $G_i=G[V_i]$ is the induced subgraph of $G$ on the vertex set $V_i$, then we have $G_i\cong G$ for some $i$.

Assume for a contradiction that no $G_i$ is isomorphic to $G$. Then for each $i$ there are disjoint finite sets $X_i,Y_i\subseteq V_i$ such that there is no vertex in $V_i\setminus(X_i\cup Y_i)$ which is joined to every vertex in $X_i$ and to no vertex in $Y_i$.

Since $X=X_1\cup\cdots\cup X_n$ and $Y=Y_1\cup\cdots\cup Y_n$ are disjoint finite subsets of $V$, there is a vertex $v\in V\setminus(X\cup Y)$ which is joined to every vertex in $X$ and to no vertex in $Y$. Then $v\in V_i\setminus(X_i\cup Y_i)$ for some $i$, and $v$ is joined to every vertex in $X_i$ and to no vertex in $Y_i$, contradicting our assumption.