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

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$$?

• I think the term "induced minor" is more commonly used for what you are referring to: an induced minor is obtained from a graph by vertex deletion and edge contraction. Is that correct? – Puck Rombach Jan 1 at 17:11
• $2^\omega$ consists of continuum many paiwise isomorphic components. Each component is countable. Hence every connected minor is countable. (I think I gave a similar answer earlier: mathoverflow.net/questions/301942/… ) – Goldstern Jan 1 at 17:45
• Right @PuckRombach, will correct the terminology. – Dominic van der Zypen Jan 1 at 20:27
• Thanks @Goldstern, have removed the question for uncountable minors – Dominic van der Zypen Jan 1 at 20:29

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, 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.