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

You must log in to answer this question.

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