Is every finite graph an induced minor of $\omega^2$?

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 $\omega^2$ into a graph by saying that $(x_0, y_0),(x_1,y_1)\in \omega^2$ form an edge if and only if $|x_0-x_1|+|y_0-y_1|=1$ (that is any point and its direct successor in the product order of $\omega^2$ form an edge).

Is every finite graph an induced minor of $\omega^2$?

Answer 1

Definitely not all graphs are minors of $\omega^2$ - $\omega^2$ is obviously a planar graph, and hence so is each of its minors. In fact, it turns out the converse also holds - every planar graph is an induced minor of $\omega^2$. Let me illustrate the construction with a small example. In the following illustrations, each small square is meant to represent an element of $\omega^2$, and two such are neighbours iff they share a side.

Consider the following graph on four vertices:

We replace each vertex with a suitably large blocks (the higher the degree, the larger the block will need to be), and replace each edge with a chain of squares between corresponding two blocks, so that no two chains have squares sharing a side:

Now we just need to split those squares into sets, which I will represent with colors. Each vertex block gets a separate color, and a chain corresponding to an edge can be given either color of its endpoints:

I am not crazy enough to write out the details of how such construction would work for arbitrary planar graph, but I hope the idea gets across, and that it's more or less clear that it's always possible.

In the comment I have mentioned that there is no such restriction in three dimensions, and indeed any countable graph is an induced minor of $\omega^3$. For finite graphs a procedure as above can be repeated, but it's not immediately clear that it will work for infinite graphs, so let me spell out an explicit construction.

Let $G=(\omega,E)$ be any graph with vertex set $\omega$. Take first the sets $\{(2n,0)\}\times\omega$ for $n\in\omega$. Those correspond to vertex blocks from the previous construction. We now just need to add chains for edges. For an edge $E=\{n,m\},n<m$, take a chain consisting of vertices $$(2n,1,2k),(2n,2,2k),(2n+1,2,2k),(2n+2,2,2k),\dots,(2m,2,2k),(2m,1,2k)$$ (think of a bridge going from the $n$-th block to the $m$-th block, going over all intermediate blocks), where $k$ is any integer. Choosing $k$ different for every edge, and assigning (as above) to the same set as one of the chains it connects, it's easy to see the resulting graph minor is isomorphic to $G$.

Note that this construction shows that, in fact, any graph is a minor of $\omega^2\times 3$. We know from above that precisely planar graphs are minors of $\omega^2\times 1$. It's not immediately clear to me what graphs are minors of $\omega^2\times 2$. My construction doesn't translate directly, but some nonplanar graphs, like $K_5$, are minors. Perhaps the answer is more complicated in this case...