"Universal" infinite graph (with respect to minors)

Question

Let $\kappa\geq \aleph_0$ be a cardinal. Is there a simple undirected graph $G=(V,E)$ such that every simple undirected graph on $\kappa$ vertices is isomorphic to a minor of $G$?

Answer 1

Yes. In fact, a stronger statement is true: for every cardinal $\kappa$, there is a simple undirected graph $G = (V,E)$ such that every simple undirected graph on $\kappa$ vertices is isomorphic to an induced subgraph of $G$.

There are several ways to see this. My favorite is as follows. First, assume that $\kappa$ is a regular cardinal (otherwise just use $\kappa^+$ instead). Let $V = V_\kappa$ denote the set of all sets that have rank smaller than $\kappa$, and define $E$ so that $x$ and $y$ are connected if and only if either $x \in y$ or $y \in x$. (In other words, $E$ is the symmetrization of the membership relation.) I claim that this graph has the desired property.

To see this, simply note that if $X$ and $Y$ are disjoint subsets of $V$, and both $X$ and $Y$ have size less than $\kappa$, then (by regularity) there is some $\alpha < \kappa$ such that every "vertex" in $X$ and $Y$ is a set of rank at most $\alpha$. Then there is a set of rank $\alpha+1$ that is connected to everything in $X$ and nothing in $Y$ (namely, the set $X$ itself). This shows that $G$ has the "extension property" (as it's often called for the countable random graph), and it's easy to use this property, along with a standard argument by transfinite recursion, to build a copy of any size-($<\kappa$) graph inside of $G$.

Notes:

1. If $\kappa = \omega$, then this construction gives you the countable random graph.

2. If you don't like this construction, you can build a graph G with the "extension property" directly by transfinite recursion.

3. You can use $H_\kappa$ in the place of $V_\kappa$ and this argument still works. With a touch more work, this shows that, assuming GCH, there is for any $\kappa$ a graph of size $\kappa$ that contains as an induced subgraph every graph of size less than $\kappa$ (i.e., nice analogs of the Rado graph at higher cardinals). This (or versions of it) is sometimes possible to attain even without GCH, as in the paper of Shelah linked to in Tony's answer.

Answer 2

For countably infinite graphs you can take the Rado Graph, which contains all countable graphs (even as induced subgraphs). For higher cardinals, see this paper of Shelah. As I mention in a comment, the version with minors is not that interesting, since you can just take the complete graph on $\kappa$ vertices.