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

  • 2
    $\begingroup$ 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. $\endgroup$ – Wojowu Jun 2 '18 at 15:59
  • $\begingroup$ Thanks for your argument! Will put it into the problem statement as remark $\endgroup$ – Dominic van der Zypen Jun 2 '18 at 16:42
  • 1
    $\begingroup$ "$m(2)>2$ would allow to construct a counterexample to the $4$-color theorem" -- you meant $m(2)>4$, of course. $\endgroup$ – Adam Przeździecki Jun 2 '18 at 16:59
  • $\begingroup$ Right Adam - will correct $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Is the infinite case directly realizable, in that $K_\omega$ is a minor of $\mathbb{Z}^3$? $\endgroup$ – Geoffrey Irving Jun 2 '18 at 23:05
  • $\begingroup$ @Yes, just take $m=\infty$ and $i,j<m$ $\endgroup$ – Adam Przeździecki Jun 3 '18 at 8:21

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.