Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around...

The question concerns the TSP problem (with fixed start- and end-vertex). The graph is the graph induced on the ball in an infinite grid. More precisely, the vertices are $B_n = \lbrace (x,y) \in \mathbb{Z}^2 \mid |x|+|y| \leq n \rbrace$ and two vertices $v'=(x',y')$ and $v=(x,y)$ are neighbours if $|x-x'| +|y-y'|=1$.

$\textbf{Questions:}$ For two distinct vertices $v$ and $v'$ in $B_n$ (say $n>2$) let $p_{v,v'}$ be the shortest path between these vertices which goes at least once through any vertex. Let $|p|$ be the length of a path $p$.

  • $\textbf{(1)}$ What is the smallest $k$ (possibly depending on $n$ but independent of $v$ and $v'$) such that $|p_{v,v'}| \leq |B_n| + k$? Can $k$ be chosen independently of $n$?

  • $\textbf{(2)}$ What is the smallest $\ell$ (possibly depending on $n$) such that $\max_{v,v'} |p_{v,v'}| \leq \min_{v,v'} |p_{v,v'}|+\ell$? Can $\ell$ be chosen independently of $n$?

For rectangles (of sides $m \times n$) instead of balls, it is known that $k$ and $\ell$ can be chosen to be (respectively) $1$ and $2$ as soon as $m,n \geq 3$. I have the impression that this is sharp contrast to the case of a ball ($\ell$ might still be uniformly bounded but $k$ is probably $\simeq An+B$)

share|improve this question
    
So, by "ball", you mean the ball in the $\ell_1$-norm, that is, a square with sides of angles $\pi/4$ with respect to the axes? –  Jan Kyncl Jun 20 at 7:23
    
Regarding question 2), which paths do you consider? What is a "path", actually, by your definition? –  Jan Kyncl Jun 20 at 7:30
1  
Sorry fot the delay: 1- yes, the ball is the one from the graph (or $\ell^1$) metric. 2- Here by path between $v$ and $v'$ I mean a "walk" i.e. a sequence of vertices $\lbrace v_i \rbrace_{i=0}^\ell$ with $v_0 = v$ and $v_\ell = v'$ and, for any $1 \leq j \leq \ell$ one has that $v_j$ is a neighbour of $v_{j-1}$. The length of this path is $\ell$. –  Antoine Jun 22 at 12:32
    
Actually, if one uses the definition of "path" as «a subgraph isomorphic to a "segment" graph», then there are lots of cases where the vertices may not all covered. The difference between rectangle and ball is still striking there. In this definition of path, a rectangle has a path which misses at most two vertices (independently of start and end vertex) whereas, in a ball, lots of points are missed by this kind of path. –  Antoine Jun 22 at 12:38
    
I see... so then it might be a good idea to edit the question and replace "path" by "walk", as a "path" in a graph usually means that it visits no vertex more than once. –  Jan Kyncl Jun 23 at 7:15

1 Answer 1

up vote 3 down vote accepted

For question (1), $k$ grows linearly with $n$, so it cannot be chosen independently.

Color the vertices of the grid black and white, so that the vertices $(x,y)$ with $x+y$ even are black and the remaining vertices are white. Clearly, every edge of the graph has one end black and the other end white. Therefore, on every walk, the number of black and white vertices differs by at most one.

Now it is easy to see that $B_n$ has $n^2$ vertices of one color and $(n+1)^2$ vertices of the other color. So every walk visiting all vertices of $B_n$ has at least $|B_n|+2n$ vertices, that is, at least $|B_n|+2n-1$ edges. Now, if the two vertices $v$ and $v'$ belong to the minor color, then the length of the walk from $v$ to $v'$ must be at least $|B_n|+2n+1$.

The lower bound $|B_n|+2n-1$ is achieved by a spiral-like walk that starts at $(0,n)$ and ends at $(0,0)$ for $n$ even, or $(1,0)$ for $n$ odd.

The case of arbitrary pair of endpoints remains to be solved. But clearly, $l$ is not larger than $2n+1$ (one can start with the spiral-like walk, perhaps rotated or reflected, and extend it to the required endpoints).

The existence of the spiral walk matching the necessary lower bound also implies that $k=l+2n-1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.