0
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ $\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. $\endgroup$ – Wojowu Jan 21 at 9:18
  • 5
    $\begingroup$ Also, before you ask, every countable graph is an induced minor of $\omega^3$. $\endgroup$ – Wojowu Jan 21 at 9:21
  • 3
    $\begingroup$ See here for a proof planar graphs are minors of grids. The construction should be tweakable as to make them induced minors. $\endgroup$ – Wojowu Jan 21 at 9:35
  • $\begingroup$ 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? $\endgroup$ – Dominic van der Zypen Jan 21 at 15:37
6
$\begingroup$

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: enter image description here

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: enter image description here

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: enter image description here

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

$\endgroup$
  • $\begingroup$ Wonderful construction, thanks @wojowu! $\endgroup$ – Dominic van der Zypen Jan 21 at 16:49

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.