# Uncountably many countable graphs with no homomorphism between them

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, w\}\in E(G)$ implies $\{f(v), f(w)\} \in E(H)$.

If $G,H$ are graphs and there is a graph homomorphism $f:G\to H$ we write $G\to H$, and otherwise $G\not\to H$.

Let $C$ be the set of graphs such that $V(G)=\mathbb{N}$. We set $$E = \big\{\{G,H\}: (G,H\in C) \land (G\not\to H) \land (H\not\to G)\big\}.$$ Let $G_{\mathbb{N}} = (C,E)$.

Question: Does $G_{\mathbb{N}}$ have an uncountable clique?

Yes. Such cliques are called rigid families of graphs. For every infinite cardinal $\kappa$ there exists a rigid family of graphs of cardinality $2^\kappa$, such that each graph in the family has $\kappa$ vertices.
• @Adam Przeździecki By any chance, do you know whether the cliques can be absolutely rigid, i.e. they remain rigid in any generic extension by forcing that preserves cardinals? Or does this only happen up to the first $\omega$-Erdös cardinal? – Avshalom Jun 3 '15 at 13:40
• @Avshalom -- Actually, I have never worked with absolute things, but I think you are right. I think that such cliques exists only up to the first $\omega$-Erdös cardinal. It probably follows from Droste, Göbel, Pokutta, Absolute graphs with prescribed endomorphism monoid, Semigroup Forum 76 (2008), 256–267. – Adam Przeździecki Jun 6 '15 at 11:35