Maximal Antichains of Isomorphic Subgraphs of the Rado Graph

Miloš 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 $. 

Full Text:



  • There are currently no refbacks.