0
$\begingroup$

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

Improve this question
$\endgroup$
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
    Commented Jun 2, 2018 at 15:59
  • $\begingroup$ Thanks for your argument! Will put it into the problem statement as remark $\endgroup$
    – Dominic van der Zypen
    Commented Jun 2, 2018 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
    Commented Jun 2, 2018 at 16:59
  • $\begingroup$ Right Adam - will correct $\endgroup$
    – Dominic van der Zypen
    Commented Jun 2, 2018 at 18:39

1 Answer 1

Reset to default
3
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .