Does the minor graph of graphs on $\mathbb{N}$ have an uncountable independent set?

Question

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\}$. We write $V(G) := V$.

If $S, T$ are disjoint subsets of $V(G)$ we say that $S, T$ are connected to each other if there is $s\in S, t\in T$ such that $\{s,t\}\in E(G)$. If $G,H$ are graphs, we say $H$ is a minor of $G$ (in symbols $G \geq_{\text{min}} H$) if there is a family ${\cal S}$ of pairwise disjoint connected subsets of $V(G)$ and a bijection $\varphi:V(H)\to {\cal S}$ such that whenever $\{v,w\}\in E(H)$ then $\varphi(v)$ and $\varphi(w)$ are connected to each other.

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\geq_{\text{min}} H \lor H \geq_{\text{min}} G)\big\}.$$ Let $G_{\mathbb{N}} = (C,E)$ and let ${\cal I}$ be the collection of independent sets in $G_{\mathbb{N}}$.

Question: Set $\kappa = \text{sup}\{|I|: I\in {\cal I}\}$. What is the value of $\kappa$, and does $G_{\mathbb{N}}$ have an independent set $I_0$ such that $|I_0| =\kappa$?

Answer 1

This is not really an answer, but a (hopefully relevant) observation or two that won't fit into the comments section.

If you don't insist on using countable graphs, then the answer is yes.

To see this, we'll need to use a result of Robin Thomas. In this paper, Thomas comes up with a way of associating to each $X \subseteq 2^\omega$ a graph $G_X$. If you look at his construction, it's fairly easy to see that $G_X$ is always connected (we'll use this later). He shows that $G_X$ is a minor of $G_Y$ only if $X$ "almost embeds" into $Y$, meaning that there is a continuous injection from a co-countable subset of $X$ into $Y$ (using the standard Cantor-set topology on $2^\omega$). In Section 4 of the paper, Thomas says that Petr Simon has shown that there is a countable set $Y_1, Y_2, \dots$ of subsets of $2^\omega$ such that $Y_i$ does not almost embed in $Y_j$ for any $i \neq j$. Putting this together:

Lemma: (Simon and Thomas) There is a countable set of connected graphs (each of size $\mathfrak{c}$) such that no one of these graphs is a minor of another.

This automatically tells us that there is a countable set of "independent" graphs in the sense you describe (although the graphs are of size $\mathfrak{c}$). Using the fact that they're all connected, we can also find an uncountable set. Let $\{G_n : n \in \mathbb N\}$ be a set of graphs as described in the lemma. For each $A \subseteq \mathbb N$, let $H_A$ be the disjoint sum of all the $G_n$ with $n \in A$. I claim that $H_A$ is a minor of $H_B$ if and only if $A \subseteq B$.

The "if" part is obvious: if $A \subseteq B$ then $H_A$ is a subgraph of $H_B$. For the "only if", suppose $A \not\subseteq B$ and pick $n \in A \setminus B$. Then $G_n$ is a connected component of $H_A$. Suppose $\mathcal S$ and $\varphi$ witness that $H_A$ is a minor of $H_B$. Since each member of $\mathcal S$ must be connected, and because $G_n$ is connected, it must also be true that $\bigcup \varphi[G_n]$ is connected. But this means that $\bigcup \varphi[G_n]$ must be a subset of some fixed $G_m$, $m \in B$, which means that $G_n$ is a minor of $G_m$. Since $n \notin B$, $m \neq n$ and we have a contradiction.

Using the claim, we get our uncountable set of graphs just by noting that there is an uncountable family $\{A_\alpha : \alpha \in \mathfrak{c}\}$ of subsets of $\mathbb N$ such that no one member of this family is a subset of another (an almost disjoint family will do). An uncountable family of independent graphs is $\{H_{A_\alpha} : \alpha \in \mathfrak{c}\}$.

Two more observations:

If you can find a countable independent set in $G_{\mathbb N}$, and each member of that set is a connected graph, then your question is answered affirmatively, since the above argument let's us step up from a countable set of connected graphs to an uncountable set of graphs.

As Paul McKenney points out in the comments, it's probably very difficult (if possible at all) to find an infinite independent set in $G_{\mathbb N}$. Given the subtlety of Robin Thomas's paper, I would say that doing so would probably require a lot of effort. On the other hand, a negative answer to your question could also require quite a bit of effort, since it would mean an extension of the Robertson-Seymour Theorem (and it's fair to say this is not an easy theorem). So (although I'm happy to be wrong), I don't think you can expect this question to be answered easily!