4
$\begingroup$

Let $\Gamma$ be a connected graph, let $\lambda \ge 1$ and $c \ge 0$ be some constants. Recall that a combinatorial path $p$ in $\Gamma$ is said to be $(\lambda,c)$-quasigeodesic if for every combinatorial subpath $q$ of $p$ one has $$\ell(q) \le \lambda d(q_-,q_+)+c,$$ where $\ell(q)$ is the length of $q$, $q_-$ and $ q_+$ are the endpoints of $q$, and $d(\cdot,\cdot)$ is the standard metric on $\Gamma$.

Question 1: suppose that a path $s$ in $\Gamma$ has been obtained from a $(\lambda,c)$-quasigeodesic path $p$ by replacing some (combinatorial) subpaths of $p$ with geodesics. Is it true that this new path $s$ is again $(\lambda,c)$-quasigeodesic?

Intuitively, the answer should be "Yes", because replacing subpaths with geodesics ("shortcutting") should only improve the quasigeodesicity constants. However, I do not see how to prove this.

If the answer to Question 1 is negative, the natural next question is the following:

Question 2: suppose that a path $s$ in $\Gamma$ has been obtained from a $(\lambda,c)$-quasigeodesic path $p$ by replacing some subpaths of $p$ with geodesics. Is it true that this new path $s$ is $(\lambda',c')$-quasigeodesic, where the constants $\lambda' \ge 1$, $c' \ge 0$ depend only on $\Gamma$, $\lambda$ and $c$?

It's not hard to show that the answer to Question 2 is positive when the graph $\Gamma$ is $\delta$-hyperbolic, but I do not have a proof or a counter-example for more general graphs.

$\endgroup$
5
  • 1
    $\begingroup$ How about ${\mathbb Z}^2$? There are many geodesics with the same endpoints there. $\endgroup$
    – markvs
    Oct 12, 2021 at 14:20
  • 3
    $\begingroup$ here is an easy counterexample in $\mathbb Z^2$: the path [$k$ steps up, $k$ steps right, $k$ steps down] is a $(3,0)$ quasi-geodesic, but replacing the first $2k$ steps by the geodesic [$(k-1)$ steps right, $k$ steps up, one step right] does not preserve this. $\endgroup$ Oct 12, 2021 at 14:31
  • $\begingroup$ @FlorianLehner: thanks, that's a great counter-example for both questions! I have thought about the same path, but treated it as a $(1,2k)$-quasigeodesic, instead of changing the multiplicative constant! What if I require $\lambda=1$? $\endgroup$ Oct 12, 2021 at 14:43
  • 1
    $\begingroup$ @AshotMinasyan: If I'm not mistaken, then a path is a $(1,c)$-quasigeodesic if and only if its length exceeds the distance between its endpoints by at most $c$, i.e. we only need to check the whole path, not all sub-paths. This property is certainly preserved under replacing a subpath by a shorter (or equally long) one. $\endgroup$ Oct 12, 2021 at 15:26
  • $\begingroup$ @FlorianLehner: you are right, thanks for your comments. If you decide to put them as an answer I would be happy to accept it. $\endgroup$ Oct 12, 2021 at 21:14

1 Answer 1

4
$\begingroup$

As suggested, I am turning my comments into an answer. The answer to both questions is negative for any $\lambda > 1$, and positive for $\lambda = 1$.

For $\lambda = 1+\epsilon$ note that in $\mathbb Z^2$, the concatenation of the (unique) geodesics from $(0,0)$ to $(0,k)$, from $(0,k)$ to $(n,k)$ and from $(n,k)$ to $(n,0)$ is $(1+\epsilon,0)$-quasigeodesic given $\frac{2k}{n} < \epsilon$.

If we replace the segment between $(0,0)$ and $(n-1,k)$ by the geodesic from $(0,0)$ via $(n-1,0)$ to $(n-1,k)$ then the points $(0,n-1)$ and $(0,n)$ have distance $1$ in $\mathbb Z^2$, but distance $2k+1$ on the path. So this path can't be $(\lambda',c')$-quasigeodesic unless $\lambda'+c' \geq 2k+1$.

For $\lambda = 1$, note that a path $p$ is $(1,c)$-quasigeodesic if and only if $\ell(p) \leq d(p_-,p_+)+c$; in other words, it suffices to check the condition for the whole path rather than for all sub-paths. This property is clearly preserved when replacing any subpath by a shorter or equally long one.

$\endgroup$

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.