Maximal antichains of isomorphic subgraphs of the Rado graph


Milos S. Kurilić, Petar Marković




If $\langle R,E\rangle$ is the Rado graph and $\mathcal R(R)$ the set of its copies inside $R$, then $\langle\mathcal R(R),\subset\rangle$ is a chain-complete and non-atomic partial order of the size $2^{\aleph_0}$. A family $\mathcal A\subset\mathcal R(R)$ is a maximal antichain in this partial order iff (1) $A\cap B$ does not contain a copy of $R$, for each different $A,B\in\mathcal A$ and (2) for each $S\in\mathcal R(R)$ there is $A\in\mathcal A$ such that $A\cap S$ contains a copy of $R$. We show that the partial order $\langle\mathcal R(R),\subset\rangle$ contains maximal antichains of size $2^{\aleph_0}$, $\aleph_0$ and $n$, for each positive integer $n$ (thus, of all possible cardinalities, under CH). The results are compared with the corresponding known results concerning the partial order $\langle[\omega]^\omega,\subset\rangle$.