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

  • 1
    $\begingroup$ 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? $\endgroup$ – Puck Rombach Jan 1 '19 at 17:11
  • 3
    $\begingroup$ $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/… ) $\endgroup$ – Goldstern Jan 1 '19 at 17:45
  • $\begingroup$ Right @PuckRombach, will correct the terminology. $\endgroup$ – Dominic van der Zypen Jan 1 '19 at 20:27
  • $\begingroup$ Thanks @Goldstern, have removed the question for uncountable minors $\endgroup$ – Dominic van der Zypen Jan 1 '19 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<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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.