# Complete minors of the grid graphs $\mathbb{Z}^n$

Let $n>1$ be an integer. We say that two points $(x_1,\ldots,x_n),(y_1,\ldots,y_n)\in\mathbb{Z}^n$ are a member of the edge set $E_n$ if and only if $$\sum_{i=1}^n|x_i-y_i| = 1.$$

Question. Given an integer $n>1$, is there a maximal integer $m(n)$ such that the complete graph $K_{m(n)}$ is a minor of $(\mathbb{Z}^n, E_n)$? If yes, it would also be nice to know an explicit formula for $m(n)$.

Remark. I believe that for $n=2$ there is such a maximal integer, and $m(2) \in \{3,4\}$. I am fairly certain that $m(2) >4$ would allow to construct a counterexample to the 4-color theorem.)

Edit. In the comment section, Wojowu shows that $m(2)=4$.

• I'm pretty sure $m(2)=4$ (consider minor given by sets $\{(1,1)\},\{(0,0),(0,1),(0,2)\},\{(1,0),(2,0),(2,1)\},\{(1,2),(2,2)\}$) and $m(n)$ is infinite for $n>2$ (by some construction similar to the fact any graph can be embedded in $\mathbb R^3$ without intersections). I will let someone else write up the details. – Wojowu Jun 2 '18 at 15:59
• Thanks for your argument! Will put it into the problem statement as remark – Dominic van der Zypen Jun 2 '18 at 16:42
• "$m(2)>2$ would allow to construct a counterexample to the $4$-color theorem" -- you meant $m(2)>4$, of course. – Adam Przeździecki Jun 2 '18 at 16:59
• Right Adam - will correct – Dominic van der Zypen Jun 2 '18 at 18:39

Either I am missing something or for $n>2$ you have $m(n)=\infty$. It is enough to show this for $n=3$. Choose any $m$ and a set of edges in $E_3$ which is the union of the following three sets:
• $\{(i,j,0),(i,j+1,0)\}\mbox{ such that } 1\leq i\leq m\mbox{ and } 1\leq j < m$
• $\{(i,j,1),(i+1,j,1)\}\mbox{ such that } 1\leq i < m\mbox{ and } 1\leq j\leq m$
• $\{(i,i,0),(i,i,1)\}\mbox{ such that } 1\leq i\leq m$
Then the subgraph determined by these edges has $m$ connected components and any two of them are "connected" to each other in your sense.
• Is the infinite case directly realizable, in that $K_\omega$ is a minor of $\mathbb{Z}^3$? – Geoffrey Irving Jun 2 '18 at 23:05
• @Yes, just take $m=\infty$ and $i,j<m$ – Adam Przeździecki Jun 3 '18 at 8:21