Induced minors of $\{0,1\}^\omega$

Question

Let $G=(V,E)$ be a simple, undirected graph. Suppose that ${\cal S}$ is a collection of non-empty, connected, and pairwise disjoint subsets of $V$. Let $G({\cal S})$ be the graph with vertex set ${\cal S}$; and $S\neq T\in {\cal S}$ form an edge if and only if if there are $x\in S, y \in T$ such that $\{x,y\}\in E$.

If $H$ is a simple undirected graph, we say that $H$ is a induced minor of $G$ if there is a collection ${\cal S}$ of non-empty, connected, and pairwise disjoint subsets of $V(G)$ such that $H\cong G({\cal S})$.

We make $\{0,1\}^\omega$ into a graph by saying that $x,y\in\{0,1\}^\omega$ form an edge if $|\{k\in\omega:x(k)\neq y(k)\}|=1$.

Is every countable graph a induced minor of $\{0,1\}^\omega$?

Answer 1

Let $G=(\omega,E)$ be an arbitrary graph. Let $S_n=\{x_n\}\cup\{y_{nm}:\{n,m\}\in E\}$, where $x_n$ is the characteristic function of $\{2n\}$ and $y_{nm}$ is the characteristic function of $\{2m,2n+1\}$. The induced minor of $\mathcal S=\{S_n:n\in\omega\}$ is clearly isomorphic to $G$, showing every countable graph is an induced minor. (Note: in the definition of $S_n$ we could even restrict $m<n$, which would let each $S_n$ be finite.)

As Goldstern remarks in a comment, every connected component of $\{0,1\}^\omega$ is countable, hence so is every connected minor. Since the connected components are isomorphic and there is $2^{\aleph_0}$ of them, we can conclude induced minors of this graph are precisely ones which are unions of at most continuum many countable graphs.