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$.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityDoes 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$.
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.