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

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

• $\omega^2$ is planar, hence so is its every minor. Every planar graph will be a minor, which you can see by approximating a drawing in a suitable way. Jan 21, 2019 at 9:18
• Also, before you ask, every countable graph is an induced minor of $\omega^3$. Jan 21, 2019 at 9:21
• See here for a proof planar graphs are minors of grids. The construction should be tweakable as to make them induced minors. Jan 21, 2019 at 9:35
• Can you put a short argument for your first comment into an answer so we can close this thread? Comment #2 is amazing! Do you have a proof/reference? Jan 21, 2019 at 15:37

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

• Wonderful construction, thanks @wojowu! Jan 21, 2019 at 16:49