I have this exercise
(Peter J. Cameron) Prove that for every infinite countable graph $M$ the following are equivalent
- $M$ is either random, complete or empty (i.e. $r^M = \emptyset$, in other words every point is isolated)
- if $M_1, M_2 \subseteq M$ are such $M_1 \sqcup M_2 = M$ (i.e. they form a partition) then $M_1 \simeq M$ or $M_2 \simeq M$ (Cameron calls this property Pigeonhole principle)
Now I have some problems in proving this statement. I traced the article (link) by Cameron in which this proposition appears (Prop. 4 page 5) but I'm having a hard time making sense of the proof presented. In particular I don't understand how can we say that $X$ and $Y$ (defined in the article's proof) form a partition. Any suggestion?
Thanks
Best Answer
We start with two disjoint non-empty subsets $A$ and $B$ such that $A\cup B$ doesn't have a corresponding "correctly joined" vertex in $\Gamma$. Then we enhance $A$ into $X$: a subset of those vertices not in $B$ that are not correctly joined with $A$. Since we explicitly avoided including $B$ vertices in this definition, $X$ and $B$ are disjoint as well. Now we enhance $B$ with vertices not in $X$ that are not correctly joined with $B$, and get a subset $Y$. Again, by this definition, $X$ and $Y$ are disjoint. Moreover, if we suppose that there is a $z\in\Gamma$ which avoided being picked into any of $X$ and $Y$, then it is correctly joined with both of $A$ and $B$, which contradicts the initial choice of $A\cup B$. Thus $X\cup Y=\Gamma$, as required.
Now, by pigeonhole principle, $X$ or $Y$ is isomorphic to $\Gamma$. Taking the isomorhism, say, $f\colon X\to \Gamma$, we obtain that $f(A)$ is a lesser (than $A\cup B$) subset in $\Gamma$ that doesn't have a corresponding "correctly joined" vertex. If we took $A\cup B$ to be the minimal such subset, we get a contradiction: the only way to avoid this is to assume that the minimal such subset is of size 1 and cannot be split into non-empty $A$ and $B$, which is handled above in the article proof.