Does every infinite cardinal $\kappa$ have the following property?
There is a simple, undirected graph $G_0=(\kappa, E_0)$ such that every simple, undirected graph $G=(\kappa, E)$ is isomorphic to an induced subgraph of $G_0$.
$\begingroup$
$\endgroup$
8
asked Oct 22, 2019 at 12:32
-
3$\begingroup$ The Rado graph witnesses this for $\kappa=\aleph_0$. $\endgroup$– Gabe ConantOct 22, 2019 at 12:35
-
4$\begingroup$ Oh I see, sorry. There is a paper by Shelah called "On universal graphs without instances of CH". The abstract states that it is consistent for there to be no universal graph in power $\aleph_1$. $\endgroup$– Gabe ConantOct 22, 2019 at 13:21
-
3$\begingroup$ @GabeConant: On the other hand, $\kappa^{<\kappa} = \kappa$ implies there is a graph like this for $\kappa$. (The graph even has a recognizable description: let $H$ be the set of all sets with cardinality hereditarily less than $\kappa$, and then put an edge between $a$ and $b$ if either $a \in b$ or $b \in a$.) Therefore GCH gives you a graph like this for every regular $\kappa$. I'm pretty sure that GCH also gives you universal graphs for singular $\kappa$, so the answer to Dominic's question should be ``consistently yes, and consistently no.'' $\endgroup$– Will BrianOct 22, 2019 at 14:16
-
4$\begingroup$ I just double-checked, and yes, GCH implies that every $\kappa$ has this property. (This follows from Props 5.1.7 & 5.1.8 and Thm. 5.1.16 in Chang and Keisler's book.) @GabeConant: I suggest you turn your comment into an answer, and mention the GCH result to establish that Dominic's question is independent of ZFC. $\endgroup$– Will BrianOct 22, 2019 at 14:39
-
3$\begingroup$ @Will Brian Yes I think that's right. Under GCH one should have universal models in all uncountable powers for any elementary class (in a countable language) with amalgamation and joint embedding (or something like that). I like your concrete description for regular $\kappa$ though. $\endgroup$– Gabe ConantOct 22, 2019 at 14:40
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
1
This turns my comments (and those of Will Brian) into an answer. The summary is that the answer to the question is consistently "yes", and consistently "no".
It is reasonable to treat the question one cardinal at a time:
Let $P(\kappa)$ be the property that there is a graph of cardinality $\kappa$ that embeds every graph of cardinality $\kappa$ as an induced subgraph.
We of course have that $P(\aleph_0)$ holds, witnessed by the countable Rado graph.
In the paper "On universal graphs without instances of CH", Shelah points out that it is consistent for $P(\aleph_1)$ to fail.
So it is consistent that $P(\kappa)$ fails for some infinite $\kappa$.
But we do have the following general statement.
Proposition. If $2^{<\kappa}=\kappa$ then $P(\kappa)$ holds.
Proof. Let $T$ be the theory of the Rado graph. Assume $2^{<\kappa}=\kappa$. Then one can build a $\kappa^+$-universal model $M$ of $T$ of cardinality $\kappa$ (by 5.1.7, 5.1.8, and 5.1.16 of Chang and Keisler). Since any graph of cardinality $\kappa$ is an induced subgraph of some model of $T$ of cardinality $\kappa$, it follows that $M$ embeds any graph of cardinality $\kappa$.
Remark. I also think that this can be turned into a general fact about elementary classes with the right amalgamation and joint embedding properties.
If GCH holds then any infinite cardinal $\kappa$ satisfies $2^{<\kappa}=\kappa$, and so it is consistent that $P(\kappa)$ holds for all infinite $\kappa$.
Remark. In the same paper mentioned above, Shelah also shows that it is consistent that $P(\aleph_1)$ holds, while also CH fails (in particular, $2^{\aleph_0}=2^{\aleph_1}=\aleph_2$). The paper "Universal structures in power $\aleph_1$" by Mekler has some related results.
Thanks to Will Brian for pointing out the relevance of GCH and tracking down the references to Chang and Keisler.
answered Oct 22, 2019 at 15:49
-
$\begingroup$ Thanks Gabe for this well-written answer, with the help of @WillBrian - thank you as well! $\endgroup$ Oct 23, 2019 at 6:48