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?


1 Answer 1


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.

This is classical so I was surprised by the trouble of finding a neat reference tailored to your question. An overkill reference is Theorem 1 in Section 4 of P. Hell On some strongly rigid families of graphs and the full embedding they induce. Algebra Universalis 4 (1974), 108–126

Edit: Actually rigid families of graphs require a stronger condition - no nonidentity homomorphisms (including endomorphisms) between its members. But of course every rigid family satisfies your requirements.

  • $\begingroup$ @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? $\endgroup$
    – Avshalom
    Jun 3, 2015 at 13:40
  • $\begingroup$ @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. $\endgroup$ Jun 6, 2015 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.