}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{}{}}{{}}
{{{}}{{}}}{{}}{{{}}{{}}}{}{{}}{}{}{}{}\pgfsys@moveto{36.2488pt}{5.57669pt}\pgfsys@curveto{44.87306pt}{10.5559pt}{55.76721pt}{9.95842pt}{55.76721pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{}{}}{{}}
{{{}}{{}}}{{}}{{{}}{{}}}{}{{}}{}{}{}{}{} {}{}{}{}{{}{}{}{}}{{}{}{}{}}
{{}{}{}{}} {{}{}{}{}}
{}{}{}{}{}\pgfsys@moveto{55.76721pt}{0.0pt}\pgfsys@curveto{55.7672pt}{-9.05095pt}{46.76804pt}{-10.36925pt}{38.653pt}{-6.79607pt}\pgfsys@stroke\pgfsys@invoke{
}{{{ {{}{}{}{}}{{}{}{}{}}{}{{}}{}{}{{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.89189}{0.45226}{-0.45226}{-0.89189}{39.81636pt}{-7.38571pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{61.97563pt}{-2.5pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\cdots$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\
\stackrel{{\scriptstyle\left\lceil l,r\right\rceil}}{{\Longrightarrow}}_{m}\
\raisebox{-2.58334pt}{ \leavevmode\hbox to13pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 6.49966pt\lower-4.83301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.16666pt}{-0.5pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\raisebox{-1.0pt}{
\leavevmode\hbox to3pt{\vbox to3pt{\pgfpicture\makeatletter\hbox{\hskip
1.5pt\lower-1.5pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@curveto{1.5pt}{0.82843pt}{0.82843pt}{1.5pt}{0.0pt}{1.5pt}\pgfsys@curveto{-0.82843pt}{1.5pt}{-1.5pt}{0.82843pt}{-1.5pt}{0.0pt}\pgfsys@curveto{-1.5pt}{-0.82843pt}{-0.82843pt}{-1.5pt}{0.0pt}{-1.5pt}\pgfsys@curveto{0.82843pt}{-1.5pt}{1.5pt}{-0.82843pt}{1.5pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$

Hence removing the edge $1$ from $\mathrm{T_{\infty}}$ silently removes the
edges $n$ for all $n>1$.

We therefore see that single pushouts implement a semantics where edges can be
silently removed, but minimally so for a monograph to be obtained. This may
remove edges in a cascade, a feature that does not appear on graphs. Note that
item (1) of the gluing condition may also be breached when an edge is marked
more than once for removal, in which case it is deleted, but also when an edge
is marked both for removal and for preservation. Example 7.6 shows that in
such cases the edge is also removed. All edges marked for removal are
guaranteed to be deleted, and the other edges are preserved only if this does
not conflict with deletions. This semantics of transformation rules is thus
dual to the previous one, and should be more appealing to the daring (or lazy)
programmer.

##  9 Attributed Typed Monographs

The notion of E-graph has been designed in [2] in order to obtain an adhesive
category of graphs with attributed nodes and edges. This follows from a line
of studies on Typed Attributed Graph Transformations, see [21, 22, 23]. The
attributes are taken in a data type algebra and may be of different sorts
(booleans, integers, strings, etc.). In the case of E-graphs only the nodes of
sort values represent such attributes. But they are also typed by E-graphs,
and in the type E-graphs each node of sort values represent a sort of the data
type algebra. This should recall the constructions of Section 6 that we now
use in order to generalize the notion of typed attributed graphs given in [2].
The idea is similarly to impose that the edges typed by a sort of a data type
algebra are the elements of the corresponding carrier set.

######  Definition 9.1 (categories $\mathbf{ATM}(T,\varSigma)$).

For any monograph $T$ and signature $\varSigma:\varOmega\rightarrow
S^{<\omega}$, an _attributed typed monograph_ (ATM for short) over $T$,
$\varSigma$ is a pair $(a,\mathcal{A})$ of an object $a:A\rightarrow T$ in
$\mathbf{Monogr}\setminus T$ and a $\varSigma$-algebra $\mathcal{A}$ such that
$\mathcal{A}_{s}=(\mathsf{A}_{T}a)_{s}$ for all $s\in S\cap\mathsf{E}{T}$.

A _morphism_ $m$ from $(a,\mathcal{A})$ to an ATM $(b,\mathcal{B})$ over $T$,
$\varSigma$ is a pair $(\vec{m},\dot{m})$ of a morphism $\vec{m}:a\rightarrow
b$ in $\mathbf{Monogr}\setminus T$ and a $\varSigma$-homomorphism
$\dot{m}:\mathcal{A}\rightarrow\mathcal{B}$ such that
$\dot{m}_{s}=(\mathsf{A}_{T}\vec{m})_{s}$ for all $s\in S\cap\mathsf{E}{T}$.

Let
$\mathrm{1}_{(a,\mathcal{A})}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}(\mathrm{1}_{a},\mathrm{1}_{\mathcal{A}})$ and for any morphism
$m^{\prime}:(b,\mathcal{B})\rightarrow(c,\mathcal{C})$ let $m^{\prime}\circ
m\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}(\vec{m}^{\prime}\circ\vec{m},\dot{m}^{\prime}\circ\dot{m})$ that
is a morphism from $(a,\mathcal{A})$ to $(c,\mathcal{C})$. Let
$\mathbf{ATM}(T,\varSigma)$ be the category of ATMs over $T$, $\varSigma$ and
their morphisms.

The edges that are considered as attributes are not the nodes of a specific
sort as in E-graphs; they are characterized by the fact that they are typed by
an edge of $T$ that happens to be also a sort of the data type signature
$\varSigma$, i.e., an element of $S$. This is consistent with the typed
attributed E-graphs of [2].

We therefore see that the signatures $\mathsf{S}T$ and $\varSigma$ share sorts
but we shall consider them as otherwise distinct, in particular w.r.t.
operator names. To account for this property we need the following
construction.

######  Definition 9.2 (signature $\varSigma\dotplus\varSigma^{\prime}$).

Given two signatures $\varSigma:\varOmega\rightarrow S^{<\omega}$ and
$\varSigma^{\prime}:\varOmega^{\prime}\rightarrow S^{\prime<\omega}$, let
$(\varOmega+\varOmega^{\prime},\mu_{1},\mu_{2})$ be the coproduct of
$(\varOmega,\varOmega^{\prime})$ in $\mathbf{Sets}$ and $j$, $j^{\prime}$ be
the canonical injections of $S$, $S^{\prime}$ respectively into $S\cup
S^{\prime}$, let
$\varSigma\dotplus\varSigma^{\prime}:\varOmega+\varOmega^{\prime}\rightarrow(S\cup
S^{\prime})^{<\omega}$ be the unique function such that
$(\varSigma\dotplus\varSigma^{\prime})\circ\mu_{1}=j^{<\omega}\circ\varSigma$
and
$(\varSigma\dotplus\varSigma^{\prime})\circ\mu_{2}=j^{\prime<\omega}\circ\varSigma^{\prime}$.

$\varOmega+\varOmega^{\prime}$$(S\cup
S^{\prime})^{<\omega}$$\varOmega$$\varOmega^{\prime}$$S^{<\omega}$$S^{\prime<\omega}$$\mu_{1}$$\mu_{2}$$\varSigma$$\varSigma^{\prime}$$j^{<\omega}$$j^{\prime<\omega}$$\varSigma\dotplus\varSigma^{\prime}$

We leave it to the reader to check that this construction defines a coproduct
in the category $\mathbf{Sig}_{\mathrm{srt}}$ and therefore that
$\varSigma_{1}\mathrel{\dot{\simeq}}\varSigma_{2}$ and
$\varSigma^{\prime}_{1}\mathrel{\dot{\simeq}}\varSigma^{\prime}_{2}$ entail
$\varSigma_{1}\dotplus\varSigma^{\prime}_{1}\mathrel{\dot{\simeq}}\varSigma_{2}\dotplus\varSigma^{\prime}_{2}$.
For the sake of simplicity we will assume in the sequel that $\mathsf{S}T$ and
$\varSigma$ have no operator name in common, thus assimilate
$\mathrm{\Omega}_{T}+\varOmega$ to $\mathrm{\Omega}_{T}\cup\varOmega$ and omit
the canonical injections, so that
$\mathsf{S}T=(\mathsf{S}T\dotplus\varSigma)|_{\mathrm{\Omega}_{T}}^{(\mathsf{E}{T})^{<\omega}}$
and $\varSigma=(\mathsf{S}T\dotplus\varSigma)|_{\varOmega}^{S^{<\omega}}$.

######  Definition 9.3 (functor
$\mathsf{D}:\mathbf{ATM}(T,\varSigma)\rightarrow(\mathsf{S}T\dotplus\varSigma)\mbox{-}\mathbf{Alg}$).

For every signature $\varSigma:\varOmega\rightarrow S^{<\omega}$ and monograph
$T$ such that $\mathrm{\Omega}_{T}\cap\varOmega=\varnothing$, let
$\varSigma^{\prime}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\mathsf{S}T\dotplus\varSigma$ and
$\mathsf{D}:\mathbf{ATM}(T,\varSigma)\rightarrow\varSigma^{\prime}\mbox{-}\mathbf{Alg}$
be the functor defined as follows: for every object $(a,\mathcal{A})$ of
$\mathbf{ATM}(T,\varSigma)$ let $\mathsf{D}(a,\mathcal{A})$ be the
$\varSigma^{\prime}$-algebra $\mathcal{A}^{\prime}$ defined by

  * •

$\mathcal{A}^{\prime}_{s}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\mathcal{A}_{s}$ for all $s\in S$ and
$\mathcal{A}^{\prime}_{e}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}(\mathsf{A}_{T}a)_{e}$ for all $e\in\mathsf{E}{T}$,

  * •

$o^{\mathcal{A}^{\prime}}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}o^{\mathcal{A}}$ for all $o\in\varOmega$ and
$\texttt{[}e{\cdot}\iota\texttt{]}^{\mathcal{A}^{\prime}}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\texttt{[}e{\cdot}\iota\texttt{]}^{\mathsf{A}_{T}a}$ for all
$\texttt{[}e{\cdot}\iota\texttt{]}\in\mathrm{\Omega}_{T}$.

For every morphism $m:(a,\mathcal{A})\rightarrow(b,\mathcal{B})$, let
$(\mathsf{D}m)_{s}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\dot{m}_{s}$ for all $s\in S$ and
$(\mathsf{D}m)_{e}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}(\mathsf{A}_{T}\vec{m})_{e}$ for all $e\in\mathsf{E}{T}$.

It is straightforward to check that $\mathsf{D}m$ is a
$\varSigma^{\prime}$-homomorphism from $\mathsf{D}(a,\mathcal{A})$ to
$\mathsf{D}(b,\mathcal{B})$, and hence that $\mathsf{D}$ is a functor.

######  Theorem 9.4.

$\mathsf{D}$ is an equivalence from $\mathbf{ATM}(T,\varSigma)$ to
$(\mathsf{S}T\dotplus\varSigma)\mbox{-}\mathbf{Alg}$.

###### Proof.

It is easy to see that $\mathsf{D}$ is full and faithful by the same property
of $\mathsf{A}_{T}$.

We prove that $\mathsf{D}$ is isomorphism-dense. For any
$\varSigma^{\prime}$-algebra $\mathcal{B}^{\prime}$, let $\mathcal{B}$ (resp.
$\mathcal{C}$) be its restriction to $\varSigma$ (resp. $\mathsf{S}T$). Since
$\mathsf{A}_{T}$ is isomorphism-dense by Theorem 6.8, there exist an object
$a:A\rightarrow T$ in $\mathbf{Monogr}\setminus T$ and an
$\mathsf{S}T$-isomorphism $h:\mathsf{A}_{T}a\rightarrow\mathcal{C}$. We define
simultaneously a set $\mathcal{A}_{s}$ and a function
$k_{s}:\mathcal{A}_{s}\rightarrow\mathcal{B}_{s}$ for all $s\in S$ by taking
$\mathcal{A}_{s}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\mathcal{B}_{s}$ and
$k_{s}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\mathrm{1}_{\mathcal{A}_{s}}$ if $s\in S\setminus\mathsf{E}{T}$,
and $\mathcal{A}_{s}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}(\mathsf{A}_{T}a)_{s}$ and
$k_{s}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}h_{s}$ if $s\in S\cap\mathsf{E}{T}$ (in this case we have
$\mathcal{C}_{s}=\mathcal{B}^{\prime}_{s}=\mathcal{B}_{s}$). We then define
for every $o\in\varOmega$ the function
$o^{\mathcal{A}}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}k_{\mathrm{Rng}(o)}^{-1}\circ o^{\mathcal{B}}\circ
k_{\mathrm{Dom}(o)}:\mathcal{A}_{\mathrm{Dom}(o)}\rightarrow\mathcal{A}_{\mathrm{Rng}(o)}$,
and the $\varSigma$-algebra
$\mathcal{A}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\big{(}(\mathcal{A}_{s})_{s\in
S},(o^{\mathcal{A}})_{o\in\varOmega}\big{)}$. By construction
$(a,\mathcal{A})$ is obviously an ATM over $T,\varSigma$ and
$k\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}(k_{s})_{s\in S}$ is a $\varSigma$-isomorphism
$k:\mathcal{A}\rightarrow\mathcal{B}$.

$\mathcal{A}$$\varSigma$$\mathcal{B}$$\mathsf{A}_{T}a$$\mathsf{S}T$$\mathcal{C}$$\varSigma^{\prime}$$\mathcal{A}^{\prime}$$\mathcal{B}^{\prime}$$k$$h$

Let
$\mathcal{A}^{\prime}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\mathsf{D}(a,\mathcal{A})$,
$h^{\prime}_{s}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}k_{s}:\mathcal{A}^{\prime}_{s}\rightarrow\mathcal{B}^{\prime}_{s}$
for all $s\in S$ and
$h^{\prime}_{e}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}h_{e}:\mathcal{A}^{\prime}_{e}\rightarrow\mathcal{B}^{\prime}_{e}$
for all $e\in\mathsf{E}{T}$, since $h_{s}=k_{s}$ for all $s\in
S\cap\mathsf{E}{T}$ then
$h^{\prime}\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}(h^{\prime}_{s})_{s\in S\cup\mathsf{E}{T}}$ is well-defined. It is
then easy to see that
$h^{\prime}:\mathcal{A}^{\prime}\rightarrow\mathcal{B}^{\prime}$ is a
$\varSigma^{\prime}$-isomorphism, so that
$\mathsf{D}(a,\mathcal{A})\simeq\mathcal{B}^{\prime}$. ∎

Theorem 9.4 generalizes333Our proof is also much shorter than the 6 pages
taken by the corresponding result on attributed typed E-graphs. This is due
partly to our use of $\mathsf{A}_{T}$ (Definition 6.7) and of Theorem 6.8, but
also to the simplicity of monographs compared to the 5 sorts and 6 operator
names of E-graphs. [2, Theorem 11.3] that establishes an isomorphism between
the category of attributed E-graphs typed by an attributed E-graph ${ATG}$ and
the category of algebras of a signature denoted $\mathrm{AGSIG}(ATG)$. In
particular Theorem 11.3 of [2] requires the hypothesis that
$\mathrm{AGSIG}(ATG)$ should be _well-structured_ , which means that if there
is an operator name of $\mathsf{S}T$ whose domain sort is $s$ then $s$ is not
a sort of the data type signature $\varSigma$. Obviously this is equivalent to
requiring that only nodes of $T$ can be considered as sorts of $\varSigma$ and
is linked to the fact that only values nodes of E-graphs are supposed to hold
attributes. Since we are not restricted to E-graphs there is no need to
require that attributes should only be nodes. This has an interesting
consequence:

######  Corollary 9.5.

For every signatures $\varSigma$, $\varSigma^{\prime}$ and graph structure
$\varGamma$ such that $\varSigma^{\prime}=\varGamma\dotplus\varSigma$ there
exists a monograph $T$ such that
$\varSigma^{\prime}\mbox{-}\mathbf{Alg}\approx\mathbf{ATM}(T,\varSigma)$.

###### Proof.

By Lemma 6.3 there exists a monograph $T$ such that
$\mathsf{S}T\mathrel{\dot{\simeq}}\varGamma$, hence
$\mathsf{S}T\dotplus\varSigma\mathrel{\dot{\simeq}}\varGamma\dotplus\varSigma=\varSigma^{\prime}$
and therefore
$\varSigma^{\prime}\mbox{-}\mathbf{Alg}\simeq(\mathsf{S}T\dotplus\varSigma)\mbox{-}\mathbf{Alg}\approx\mathbf{ATM}(T,\varSigma)$.
∎

Obviously, any signature $\varSigma^{\prime}$ can be decomposed as
$\varGamma\dotplus\varSigma$ by putting some of its monadic operators (and the
sorts involved in these) in $\varGamma$ and all other operators in
$\varSigma$. And then any $\varSigma^{\prime}$-algebra can be represented as
an ATM over $T,\varSigma$, where $\mathsf{S}T\mathrel{\dot{\simeq}}\varGamma$.
This opens the way to applying graph transformations to these algebras, but
this requires some care since it is not generally possible to remove or add
elements to a $\varSigma^{\prime}$-algebra and obtain a
$\varSigma^{\prime}$-algebra as a result.

The approach adopted in [2, Definition 11.5] is to restrict the morphisms used
in span rules to a class of monomorphisms that are extensions of
$\varSigma$-isomorphisms to $(\varGamma\dotplus\varSigma)$-homomorphisms. It
is then possible to show [2, Theorem 11.11] that categories of typed
attributed E-graphs are adhesive HLR categories (a notion that generalizes
Definition 4.13, see [24]) w.r.t. this class of monomorphisms.

A similar result holds on categories of ATMs. For the sake of simplicity, and
since rule-based graph transformations are unlikely to modify attributes such
as booleans, integers or strings (and if they do they should probably not be
considered as graph transformations), we will only consider morphisms that
leave the data type algebra unchanged, element by element. This leaves the
possibility to transform the edges whose sort is in $\varGamma$ but not in
$\varSigma$.

######  Definition 9.6 (categories $\mathbf{ATM}(T,\mathcal{A})$, functor
$\mathsf{U}$, $f$ stabilizes $\mathcal{A}$).

For any $\varSigma$-algebra $\mathcal{A}$ let $\mathbf{ATM}(T,\mathcal{A})$ be
the subcategory of $\mathbf{ATM}(T,\varSigma)$ restricted to objects
$(a,\mathcal{A})$ and morphisms $(f,\mathrm{1}_{\mathcal{A}})$.

The _forgetful functor_
$\mathsf{U}:\mathbf{ATM}(T,\mathcal{A})\rightarrow\mathbf{Sets}$ is defined by
$\mathsf{U}(a,{\mathcal{A}})\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\mathsf{E}{A}$, where $a:A\rightarrow T$ and
$\mathsf{U}(f,\mathrm{1}_{\mathcal{A}})\mathrel{\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}}\mathsf{E}{f}$ (usually denoted $f$).

By abuse of notation we write $\mathcal{A}$ for the set $\bigcup_{s\in
S\cap\mathsf{E}{T}}\mathcal{A}_{s}$. A function $f$ _stabilizes_ $\mathcal{A}$
if $f^{-1}[x]=\\{x\\}$ for all $x\in\mathcal{A}$.

The proof that the categories $\mathbf{ATM}(T,\mathcal{A})$ are adhesive will
only be sketched below. The key point is the following lemma.

######  Lemma 9.7.

For all objects $(a,\mathcal{A})$, $(b,\mathcal{A})$ of
$\mathbf{ATM}(T,\mathcal{A})$ and morphism $f:a\rightarrow b$ of
$\mathbf{Monogr}\setminus T$, we have

$(f,\mathrm{1}_{\mathcal{A}}):(a,\mathcal{A})\rightarrow(b,\mathcal{A})\text{
is a morphism in }\mathbf{ATM}(T,\mathcal{A})\ \text{ iff }\ f\text{
stabilizes }\mathcal{A}.$

###### Proof.

For all $s\in S\cap\mathsf{E}{T}$ we have
$\mathcal{A}_{s}=(\mathsf{A}_{T}a)_{s}=a^{-1}[s]$ and
$\mathcal{A}_{s}=b^{-1}[s]$. Since $b\circ f=a$ then
$f^{-1}[\mathcal{A}_{s}]=f^{-1}[b^{-1}[s]]=a^{-1}[s]=\mathcal{A}_{s}$, hence
$f^{-1}[\mathcal{A}]=\mathcal{A}$. Thus $f$ stabilizes $\mathcal{A}$ iff
$f(x)=x$ for all $x\in\mathcal{A}$ iff
$(\mathsf{A}_{T}f)_{s}=f|_{\mathcal{A}_{s}}^{\mathcal{A}_{s}}=\mathrm{Id}_{\mathcal{A}_{s}}=(\mathrm{1}_{\mathcal{A}})_{s}$
for all $s\in S\cap\mathsf{E}{T}$ iff $(f,\mathrm{1}_{\mathcal{A}})$ is a
morphism in $\mathbf{ATM}(T,\mathcal{A})$. ∎

Hence the property of stabilization characterizes the difference between
morphisms in $\mathbf{Monogr}\setminus T$ and morphisms in
$\mathbf{ATM}(T,\mathcal{A})$. Besides, it is well-known how pushouts and
pullbacks in $\mathbf{Monogr}\setminus T$ can be constructed from those in
$\mathbf{Monogr}$, and we have seen that these can be constructed from those
in $\mathbf{Sets}$.

But then it is quite obvious that in $\mathbf{Sets}$, starting from a span of
functions that stabilize $\mathcal{A}$, it is always possible to find as
pushout a cospan of functions that stabilize $\mathcal{A}$. Hence not only
does $\mathbf{ATM}(T,\mathcal{A})$ have pushouts, but these are preserved by
the functor $\mathsf{U}$. A similar result holds for pullbacks, and a
construction similar to Corollary 4.7 yields that $\mathsf{U}$ also preserves
monomorphisms. Finally, we see that $\mathsf{U}$ reflects isomorphisms since
$f^{-1}$ stabilizes $\mathcal{A}$ whenever $f$ does. We conclude as in Theorem
4.17.

######  Theorem 9.8.

$\mathbf{ATM}(T,\mathcal{A})$ is adhesive.

This result does not mean that all edges that are not attributes can be freely
transformed. Their adjacencies to or from attributes may impose constraints
that only few morphisms are able to satisfy.

######  Example 9.9.

Let $\varSigma$ be the signature with no operation name and one sort s, and
$\mathcal{A}$ be the $\varSigma$-algebra defined by
$\mathcal{A}_{\texttt{s}}=\\{a,b\\}$. We consider the type monograph
$T=\\{(e,\texttt{s}),(\texttt{s},e)\\}$. A monograph typed by $T$ has any
number (but at least one) of edges typed by $e$ that must be adjacent either
to $a$ or $b$, and two edges typed by s, namely $a$ and $b$, that must be
adjacent to either the same edge $x$ typed by $e$, which yields two classes of
monographs

$a$$b$$x$$a$$b$$x$

(to which may be added any number of edges typed by $e$ and adjacent to either
$a$ or $b$), or $a$ and $b$ are adjacent to $y$ and $z$ respectively, and we
get four more classes:

$a$$y$$b$$z$$a$$y$$b$$z$$a$$y$$b$$z$$a$$y$$b$$z$

The function $y,z\mapsto x$ is a morphism from these last two monographs to
the two monographs above (respectively). There are no other morphisms between
monographs from distinct classes. We therefore see that in the category
$\mathbf{ATM}(T,\mathcal{A})$ it is possible to add or remove edges typed by
$e$ to which $a$ or $b$ are not adjacent, but there is no way to remove the
edges $y$ and $z$ (because this would require a rule with a left morphism from
an ATM without $y$ and $z$ to an ATM with $y$ and $z$, and there is no such
morphism), though they are not attributes.

Besides, we see that this category has no initial object, no terminal object,
no products nor coproducts.

##  10 Conclusion

Monographs generalize standard notions of directed graphs by allowing edges of
any length with free adjacencies. An edge of length zero represents a node,
and if it has greater length it can be adjacent to any edge, including itself.
In “monograph” the prefix mono- is justified by this unified view of nodes as
edges and of edges with unrestricted adjacencies that provide formal
conciseness (morphisms are functions characterized by a single equation); the
suffix -graph is justified by the correspondence (up to isomorphism) between
finite $\omega$-monographs and their drawings.

Monographs are universal with respect to graph structures and the
corresponding algebras, in the sense that monographs are equivalent to graph
structures extended with suitable ordering conventions on their operator
names, and that categories of typed monographs are equivalent to the
corresponding categories of algebras. Since many standard or exotic notions of
directed graphs can be represented as monadic algebras, they can also be
represented as typed monographs, but these have two advantages over graph
structures: they provide an orientation of edges and they (consequently)
dispense with operator names.

Algebraic transformations of monographs are similar to those of standard
graphs. Typed monographs may therefore be simpler to handle than graph
structured algebras, as illustrated by the results of Section 9. The
representation of oriented edges as sequences seems more natural than their
standard representation as unstructured objects that have images by a bunch of
functions. Thus type monographs emerge as a natural way of specifying graph
structures.

## References

  * [1] T. Boy de la Tour, R. Echahed, Parallel rewriting of attributed graphs, Theoretical Computer Science 848 (2020) 106–132.
  * [2] H. Ehrig, K. Ehrig, U. Prange, G. Taentzer, Fundamentals of Algebraic Graph Transformation, Monographs in Theoretical Computer Science. An EATCS Series, Springer, 2006.
  * [3] M. Löwe, Algebraic approach to single-pushout graph transformation, Theoretical Computer Science 109 (1993) 181–224.
  * [4] T. Boy de la Tour, Monographs, a category of graph structures, in: Recent Trends in Algebraic Development Techniques, 25th International Workshop, WADT 2020, Revised Selected Papers, Vol. 12669 of LNCS, Springer, 2021, pp. 54–74.
  * [5] P. Suppes, Axiomatic Set Theory, Dover Publications, Inc., 1972.
  * [6] D. Sannella, A. Tarlecki, Foundations of Algebraic Specification and Formal Software Development, Monographs in Theoretical Computer Science. An EATCS Series, Springer, 2012.
  * [7] H. Herrlich, G. E. Strecker, Category Theory, 3rd Edition, Heldermann Verlag, Berlin, 2007.
  * [8] S. Lack, P. Sobocinski, Adhesive and quasiadhesive categories, Informatique Théorique et Applications 39 (3) (2005) 511–545.
  * [9] D. Plump, Term graph rewriting, in: H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg (Eds.), Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2: Applications, Languages and Tools, World Scientific, 1999, pp. 3–61.
  * [10] A. Burroni, Higher-dimensional word problems with applications to equational logic, Theoretical Computer Science 115 (1) (1993) 43–62.
  * [11] E. Robinson, G. Rosolini, Categories of partial maps, Information and Computation 79 (2) (1988) 95–130.
  * [12] A. Corradini, T. Heindel, F. Hermann, B. König, Sesqui-pushout rewriting, in: ICGT 2006, Vol. 4178 of LNCS, Springer, 2006, pp. 30–45.
  * [13] A. Corradini, D. Duval, R. Echahed, F. Prost, L. Ribeiro, AGREE - algebraic graph rewriting with controlled embedding, in: 8th ICGT, Vol. 9151 of LNCS, Springer, 2015, pp. 35–51.
  * [14] A. Corradini, D. Duval, R. Echahed, F. Prost, L. Ribeiro, The PBPO graph transformation approach, J. Log. Algebr. Meth. Program. 103 (2019) 213–231.
  * [15] T. Boy de la Tour, R. Echahed, Parallel coherent graph transformations, in: Recent Trends in Algebraic Development Techniques, 25th International Workshop, WADT 2020, Revised Selected Papers, Vol. 12669 of LNCS, Springer, 2021, pp. 75–97.
  * [16] H. Ehrig, M. Pfender, H. J. Schneider, Graph-grammars: An algebraic approach, in: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, 1973, pp. 167–180.
  * [17] A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel, M. Löwe, Algebraic approaches to graph transformation - part I: basic concepts and double pushout approach, World Scientific, 1997, pp. 163–246.
  * [18] A. Habel, J. Müller, D. Plump, Double-pushout graph transformation revisited, Math. Struct. Comput. Sci 11 (5) (2001) 637–688.
  * [19] J.-C. Raoult, On graph rewritings, Theoretical Computer Science 32 (1,2) (1984) 1–24.
  * [20] M. Löwe, Extended algebraic graph transformation, Ph.D. thesis, Technical University of Berlin, Germany (1991).
  * [21] M. Löwe, M. Korff, A. Wagner, An algebraic framework for the transformation of attributed graphs, in: R. Sleep, R. Plasmeijer, M. van Eekelen (Eds.), Term Graph Rewriting: Theory and Practice, John Wiley, New York, 1993, pp. 185–199.
  * [22] R. Heckel, J. M. Küster, G. Taentzer, Confluence of typed attributed graph transformation systems, in: A. Corradini, H. Ehrig, H. Kreowski, G. Rozenberg (Eds.), Graph Transformation, First International Conference ICGT 2002, Vol. 2505 of LNCS, Springer, 2002, pp. 161–176.
  * [23] H. Ehrig, K. Ehrig, U. Prange, G. Taentzer, Fundamental theory for typed attributed graphs and graph transformation based on adhesive HLR categories, Fundam. Informaticae 74 (1) (2006) 31–61.
  * [24] H. Ehrig, J. Padberg, U. Prange, A. Habel, Adhesive high-level replacement systems: A new categorical framework for graph transformation, Fundam. Informaticae 74 (1) (2006) 1–29.


undefined

# Short retractions of CAT(1) spaces

Alexander Lytchak and Anton Petrunin

###### Abstract

We construct short retractions of a CAT(1) space to its small convex subsets.
This construction provides an alternative geometric description of an analytic
tool introduced by Wilfrid Kendall.

Our construction uses a _tractrix flow_ which can be defined as a gradient
flow for a family of functions of certain type. In an appendix we prove a
general existence result for gradient flows of time-dependent locally
Lipschitz semiconcave functions, which is of independent interest.

##  1 Introduction

Recall that a subset $K$ in a metric space ${\mathcal{U}}$ is called _weakly
convex_ if any two points $x,y\in K$ can be connected by a minimizing geodesic
in $K$.

Let ${\mathcal{U}}$ be a metric space and $K\subset{\mathcal{U}}$. A distance
nonexpanding map $f\colon{\mathcal{U}}\to K$ such that $f(x)=x$ for any $x\in
K$ is called a _short retraction to $K$_. If in addition a local Lipschitz
constant of $f$ is strictly less than 1 at any point $x\notin K$, then we say
that $f$ is a _strictly short retraction from ${\mathcal{U}}$ to $K$_.

1.1. Theorem. Let $\mathcal{U}$ be a complete length $\mathrm{CAT}(\kappa)$
space. Suppose $K$ is a weakly convex closed subset in $\mathcal{U}$ and there
is $p\in\mathcal{U}$ such that $|p-x|\leqslant\tfrac{\pi}{2}$ for any point
$x\in K$.

  1. (a)

If $p\in K$ and $\kappa\leqslant 1$, then there is a short retraction
$\Phi\colon\mathcal{U}\to K$.

  2. (b)

If $\kappa<1$, then there is a strictly short retraction
$\Phi\colon\mathcal{U}\to K$.

This statement is a generalization of the following well known statement about
$\mathrm{CAT}(0)$ spaces: _If ${\mathcal{U}}$ is a complete length
$\mathrm{CAT}(0)$ space and $K$ is a closed convex subset in ${\mathcal{U}}$,
then the closest point projection ${\mathcal{U}}\to K$ is a short retraction.
Moreover, if $\mathcal{U}$ is a $\mathrm{CAT}(\kappa)$ space for some
$\kappa<0$, then the closest point projection is a strictly short retraction_.

The theorem and a small trick imply the following:

1.2. Corollary. Let $\mathcal{U}$ be a complete length $\mathrm{CAT}(\kappa)$
space. Denote by $\Delta$ the diagonal in $\mathcal{U}\times\mathcal{U}$; that
is, $\Delta=\\{\,(x,x)\in\mathcal{U}\times\mathcal{U}\,\\}$.

Suppose there is a point $p\in\mathcal{U}$ such that
$|p-x|\leqslant\tfrac{\pi}{2}$ for any point $x\in\mathcal{U}$.

  1. (a)

If $\kappa\leqslant 1$, then there is a short retraction
$\Psi\colon\mathcal{U}\times\mathcal{U}\to\Delta$.

  2. (b)

If $\kappa<1$, then there is a strictly short retraction
$\Psi\colon\mathcal{U}\times\mathcal{U}\to\Delta$.

It is well known that if $\mathcal{U}$ is a complete length $\mathrm{CAT}(0)$
space, then the midpoint map $\mathcal{U}\times\mathcal{U}\to\mathcal{U}$ is
$\tfrac{1}{\sqrt{2}}$-Lipschitz and therefore it induces a short retraction
$\mathcal{U}\times\mathcal{U}\to\Delta$. The corollary provides an analogous
statement for $\mathrm{CAT}(1)$ spaces.

Motivation. In [1, (4.1)], Wilfrid Kendall observed that if $\mathcal{B}$ is a
regular geodesic ball of radius $r<\tfrac{\pi}{2}$ in a manifold with
sectional curvature at most 1, then, for an appropriate choice of constant
$\lambda$, the function

$(x,y)\mapsto\frac{1+\lambda-\cos|x-y|_{\mathcal{B}}}{\cos|p-x|_{\mathcal{B}}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}\cos|p-y|_{\mathcal{B}}}$

has convex level sets in ${\mathcal{B}}\times{\mathcal{B}}$. He also shows the
existence of a nonnegative convex function on
${\mathcal{B}}\times{\mathcal{B}}$ that vanishes only on the diagonal [1,
(4.2)]. These observations became a useful tool to study the Dirichlet problem
and its relatives; they allowed to extend a number of results from Hadamard
manifolds to Riemannian manifolds of small size and more generally to
$\mathrm{CAT}(1)$ spaces [2, 3, 4, 5, 6].

Our original goal was to make this tool transparent for geometers. Corollary 1
can be considered as a more geometric version of this tool. While Kendall’s
condition is optimal for uniqueness and regularity questions, the existence
statements can be derived from Theorem 1 in a slightly greater generality, as
we are going to explain now.

We will need the following definition, introduced by Stefan Wenger [7]; for
the definitions of ultrafilters and ultracompletions we refer to [7, 8, 9].

A metric space ${\mathcal{U}}$ is called _$1$ -complemented_ if for some _non-
principal ultrafilter_ $\omega$ there exists a short retraction of the
ultracompletion ${\mathcal{U}}^{\omega}$ to ${\mathcal{U}}$. Examples of
$1$-complemented spaces include all proper spaces, all CAT(0) spaces and all
$L^{p}$ spaces for $1\leq p\leq\infty$ [8, Proposition 2.1].

Recall that if ${\mathcal{U}}$ is $\mathrm{CAT}(\kappa)$, then so is
${\mathcal{U}}^{\omega}$. Applying these observations together with Theorem 1,
we obtain

1.3. Theorem. Let ${\mathcal{U}}$ be a complete length $\mathrm{CAT}(1)$
space. Assume there exists some $p\in{\mathcal{U}}$ such that
$|p-x|\leqslant\tfrac{\pi}{2}$ for any point $x\in{\mathcal{U}}$. Then
${\mathcal{U}}$ is $1$-complemented.

Let us list a few existence results which follow from the theorem, assuming
that the space ${\mathcal{U}}$ is as above:

  1. (a)

The existence of a solution $u$ of Dirichlet problem on the minimization of
energy in $W^{1,2}(\Omega,{\mathcal{U}})$ on any Lipschitz domain $\Omega$ in
a Riemannian manifold with prescribed trace $tr(u)$; see [10] and [8, Theorem
1.4].

  2. (b)

The existence of a minimal integral $k$-current filling any prescribed
boundary in ${\mathcal{U}}$; see [11] and [7, Theorem 3.3].

  3. (c)

The existence of a conformally parametrized disc $u:D\to{\mathcal{U}}$ of
minimal area for a given boundary curve $\gamma$, which is a Jordan curve of
finite length in ${\mathcal{U}}$; see [12] and [8, Theorem 1.2].

  4. (d)

For any Radon measure $\mu$ on ${\mathcal{U}}$ there exists a center of mass
$x\in{\mathcal{U}}$ for the measure $\mu$ [13, 2].

If in the theorem we assume strict inequality $|p-x|<\tfrac{\pi}{2}$, then the
existence results are known in all the cases (a–d). Moreover, the uniqueness
holds true under this stronger assumption in the cases (a), (b), and (d); see
[2, 5]. In our boundary case uniqueness definitely fails; for example
geodesics between points in a round hemisphere are not unique.

The uniqueness in each case can be shown using Corollary 1. Indeed if there
are different solutions of one of these problems, then their product in
${\mathcal{U}}\times{\mathcal{U}}$ does not lie in the diagonal. The latter
contradicts the existence of the strictly short retraction $\Psi$ provided by
Corollary 1.

About the proofs. We use a new tool which we call $r$-_tractrix flow_ , a
special time-dependent gradient flow. It gives a family of maps $\varphi_{t}$
for a given rectifiable curve $t\mapsto\nobreak\gamma(t)$. The important
properties of the tractrix flow are collected in Proposition 2. In particular,
(1) if $\mathcal{U}$ is $\mathrm{CAT}(1)$ and $r\leqslant\tfrac{\pi}{2}$, then
$\varphi_{t}$ is short for any $t$, and (2) if $r<\tfrac{\pi}{2}$, then the
local Lipschitz constant of $\varphi_{t}$ at $p$ is strictly less than 1 if
$p\neq\varphi_{t}(p)$.

In the proof of Theorem 1, the tractrix flow is applied in a space obtained by
gluing to $\mathcal{U}$ a spherical cone over $K$; this space is
$\mathrm{CAT}(1)$ by Reshetnyak’s gluing theorem. In Appendix B we indicate
another way of proving Theorem 1.

In the proof of Corollary 1 the additional trick consists in identifying the
product space $\mathcal{U}\times\nobreak\mathcal{U}$ with a subset of the
spherical join $\mathcal{U}\star\mathcal{U}$ and applying Theorem 1 to the
latter.

The tricks in both proofs show that it is useful to consider singular spaces
even in the case when the original space $\mathcal{U}$ is smooth; this is a
powerful freedom of Alexandrov’s world. More involved examples of such
arguments are given by Dmitry Burago, Sergei Ferleger, and Alexey Kanonenko
[14], Paul Creutz [15], and Stephan Stadler [16].

Acknowledgements. We thank Christine Brenier, Nicola Gigli, and the anonymous
referee for helpful comments. A. Lytchak was partially supported by DFG grant
SPP 2026. A. Petrunin was partially supported by Simons foundation
collaboration grant for mathematicians 584781.

##  2 Tractrix flow

For $\mathrm{CAT}(\kappa)$ spaces, we will follow the conventions in [9].

First let us describe the tractrix flow informally. Suppose that two points
$p$ and $q$ in ${\mathcal{U}}$ are connected to each other by a thread of
fixed length $r$. Imagine that the point $q$ follows the curve $\gamma$ and
drags $p$ if the thread is tight; if the thread is not tight, then $p$ does
not move. Then the trajectory of the point $p$ will be called $r$-_tractrix of
$p$ with respect to $\gamma$_. The family of maps $\varphi_{t}$ that send the
initial position of $p$ to its position at the time $t$ will be called the
$r$-_tractrix flow_ defined by $\gamma$.

More formally, suppose $\gamma\colon[a,b]\to\mathcal{U}$ is a 1-Lipschitz
curve. An $r$-tractrix with respect to $\gamma$ is defined as a gradient curve
for the time-dependent family of functions

$f_{t}=-\max\\{r,\mathop{\rm dist}\nolimits_{\gamma(t)}\\};$

here $\mathop{\rm dist}\nolimits_{x}$ denotes the distance function from the
point $x$. We also assume that the initial point lies in
$\bar{B}(\gamma(a),r)$. (We denote by $\bar{B}(x,r)$ and $B(x,r)$ the closed
and open balls of radius $r$ centered at $x$.)

The $r$-_tractrix flow_ with respect to $\gamma$ is defined as a family of
maps

$\varphi_{t}\colon\bar{B}(\gamma(a),r)\to\nobreak\bar{B}(\gamma(t),r)$

whose trajectory $t\mapsto\varphi_{t}(p)$ is the $r$-tractrix starting at
$p\in\bar{B}(\gamma(a),r)$.

The following proposition includes the properties of the tractrix flow which
will be used further in the paper.

2.1. Proposition. Let $\gamma\colon[a,b]\to\mathcal{U}$ be a 1-Lipschitz curve
in a complete length $\mathrm{CAT}(\kappa)$ space $\mathcal{U}$ for some
$\kappa\leqslant 1$ and $r<\pi$. Set $\bar{B}_{t}=\bar{B}(\gamma(t),r)$. Then
the $r$-tractrix flow $\varphi_{t}\colon\bar{B}_{a}\to\bar{B}_{t}$ is uniquely
defined. Moreover

  1. (a)

For any $t$, the map $\varphi_{t}$ is a limit of compositions
$\vartheta_{t_{n}}\circ\dots\circ\vartheta_{t_{0}}$ for $\delta\to 0$, where
$a=t_{0}<\dots<t_{n}=t$ is any partition of $[a,t]$ with
$|t_{i}-t_{i-1}|<\delta$ and where
$\vartheta_{t_{i}}:\bar{B}_{t_{i-1}}\to\bar{B}_{t_{i}}$ denotes the closest
point projection.

  2. (b)

If the family of balls $\bar{B}_{t}$ is decreasing in $t$ (that is, if
$\bar{B}_{t_{1}}\supset\bar{B}_{t_{2}}$ for $t_{1}<t_{2}$), then $\varphi_{b}$
is a strong deformation retraction from $\bar{B}_{a}$ to $\bar{B}_{b}$.

  3. (c)

If $r=\tfrac{\pi}{2}$, then $\varphi_{t}$ is short for any $t$;

  4. (d)

If $r=\tfrac{\pi}{2}$ and $\kappa<1$, then there is a positive constant
$\varepsilon$ such that the local Lipschitz constant of $\varphi_{t}$ at $p$
is bounded above by $\exp(-\varepsilon{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\ell)$, where $\ell=|p-\varphi_{t}(p)|_{\mathcal{U}}$.

Historically the first relative of the tractrix flow is the so called
_Sharafutdinov’s retraction_ [17] — a family of maps associated to a
continuous family of convex sets (in our case these sets are the balls
$\bar{B}_{t}$). Second relative is the _pursuer flow_ introduced and studied
by Stephanie Alexander, Richard Bishop, Robert Ghrist and Chanyoung Jun [18,
19, 20, 21].

Time-dependent gradient flows were studied by Chanyoung Jun [19, 21], by Lucas
C. F. Ferreira and Julio C. Valencia-Guevara [22], and by Alexander Mielke,
Riccarda Rossi, and Giuseppe Savaré [23]. Unfortunately Proposition 2 does not
follow directly from the results in these papers; for this reason we provide
in an appendix a short proof of the existence of gradient flows of Lipschitz
time-dependent family of semiconcave functions in $\mathrm{CAT}(\kappa)$
spaces.

Proof. Consider $f_{t}=-\max\\{r,\mathop{\rm dist}\nolimits_{\gamma(t)}\\}$ as
a family of functions defined in $B(\gamma(t),r+\nobreak\delta)$ for
sufficiently small $\delta>0$. Note that the family $f_{t}$ is Lipschitz. By
$\mathrm{CAT}(1)$-comparison, each $f_{t}$ is $\lambda$-concave for a fixed
$\lambda$. Moreover if $r<\tfrac{\pi}{2}$, then $\lambda=0$ and if
$r=\tfrac{\pi}{2}$, then $\lambda\to 0$ as $\delta\to 0$.

Consider the map $\varphi_{t}\colon\alpha(a)\mapsto\alpha(t)$, where $\alpha$
is a $f_{t}$-gradient curve. By A, if $\varphi_{t}(p)$ is defined, then it is
unique.

Consider the function $\ell(t)=\nobreak|\varphi_{t}(p)-\gamma(t)|$. By the
definition of the flow, we have that $\ell^{\prime}\leqslant 0$ if $\ell>r$.
It follows that $\varphi_{t}$ is defined for all $t$ and maps $\bar{B}_{a}$ to
$\bar{B}_{t}$.

(a). Given a partition $a=t_{0}<t_{1}<\dots<t_{n}=t$ with
$|t_{i}-t_{i-1}|<\delta$, consider a locally constant approximation
$\hat{f}_{t}$ of the family $f_{t}$ defined by $\hat{f}_{t}=f_{t_{i}}$ if
$t_{i}\leqslant t<t_{i+1}$. Denote by $\hat{\varphi}_{t}$ the corresponding
flow.

Given $p\in\bar{B}_{a}$, set $p_{i}=\hat{\varphi}_{t_{i}}(p)$. Observe that
$p_{i}=\vartheta_{t_{i}}(p_{i-1})$ for each $i$.

By the distance estimate (A) the flow $\hat{\varphi}_{t}$ converges to
$\varphi_{t}$ as the partition gets finer and finer, hence the result.

(b). It is sufficient to notice that $\varphi_{t}(p)=p$ if $|p-\gamma(s)|\leq
r$ for all $a\leq s\leq t$.

(c). Applying the distance estimate (A) for $s=0$, we get that

$|\varphi_{t}(p)-\varphi_{t}(q)|\leqslant|p-q|{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}e^{\lambda{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(t-a)}$

for any $p,q\in\bar{B}_{a}$, $t\geqslant a$. If $r\leqslant\tfrac{\pi}{2}$,
then the inequality holds for arbitrary $\lambda>0$; hence (c) follows.

(d). The proof of the strict inequality follows directly from (a) and the
following general consequence of the $\mathrm{CAT}(\kappa)$ comparison:

There exists some $\varepsilon>0$ such that the closest point projection
$\vartheta:\bar{B}(w,\frac{\pi}{2}+\varepsilon)\to\nobreak\bar{B}(w,\frac{\pi}{2})$
in any $\mathrm{CAT}(\kappa)$ is strictly short and satisfies

$|\vartheta(p)-\vartheta(q)|\leq e^{-\varepsilon{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|\vartheta(p)-p|}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|p-q|.$

∎

##  3 Proofs

Recall that spherical join $\mathcal{U}\star\mathcal{V}$ of two metric spaces
$\mathcal{U}$ and $\mathcal{V}$ is defined as the unit sphere (equipped with
the angle metric) in the product of Euclidean cones $\mathop{\rm
Cone}\nolimits\mathcal{U}\times\mathop{\rm Cone}\nolimits\mathcal{V}$. If
diameters of $\mathcal{U}$ and $\mathcal{V}$ do not exceed $\pi$, then
$\mathcal{U}\star\mathcal{V}$ can be defined as a metric space that admits an
onto map
$\iota\colon\mathcal{U}\times\mathcal{V}\times[0,\tfrac{\pi}{2}]\to\mathcal{U}\star\mathcal{V}$
such that

$\displaystyle|\iota(u_{1},v_{1},t_{1})$
$\displaystyle-\iota(u_{2},v_{2},t_{2})|_{\mathcal{U}\star\mathcal{V}}=$ ➊
$\displaystyle=\arccos[\sin t_{1}{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\sin
t_{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\cos|u_{1}-u_{2}|_{\mathcal{U}}+\cos t_{1}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}\cos t_{2}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\cos|v_{1}-v_{2}|_{\mathcal{V}}].$

Recall that the join of two $\mathrm{CAT}(1)$ spaces is $\mathrm{CAT}(1)$ [24,
Corollary 3.14].

Proof of 1. Consider the join of $K$ with a one-point space,
$\mathcal{J}=K\star\\{s\\}$. Since $\mathcal{J}$ is a $\mathrm{CAT}(1)$ space,
by Reshetnyak’s gluing theorem [9, 8.9.1], the space $\mathcal{W}$ glued from
${\mathcal{U}}$ and $\mathcal{J}$ along $K$ is a $\mathrm{CAT}(1)$ space;
moreover ${\mathcal{U}}$ and $\mathcal{J}$ are convex subsets in
$\mathcal{W}$.

Let $\gamma$ be the geodesic in $\mathcal{W}$ from $p$ to the pole $s$ of
$\mathcal{J}$. Set
$\bar{B}_{t}=\bar{B}(\gamma(t),\tfrac{\pi}{2})_{\mathcal{W}}$, then

  * $\diamond$

$\bar{B}_{0}=\bar{B}(p,\tfrac{\pi}{2})_{\mathcal{U}}\cup\mathcal{J}$,

  * $\diamond$

$\bar{B}_{\frac{\pi}{2}}=\mathcal{J}$, in particular
$\bar{B}_{\frac{\pi}{2}}\cap\mathcal{U}=K$,

  * $\diamond$

the family $\bar{B}_{t}$ is decreasing in $t$.

To see the last statement, note that $\mathcal{J}\subset\bar{B}_{0}$. Further,
by definition of a spherical join we have
$|x-p|_{\mathcal{W}}\leqslant|x-\nobreak\gamma(s)|_{\mathcal{W}}$ for any
$x\in K$. By construction of the metric on $\mathcal{W}$ the same inequality
holds for any $x\in\mathcal{U}$, Therefore $\bar{B}_{s}\subset\bar{B}_{0}$.
Finally, by $\mathrm{CAT}(1)$ comparison,
$\bar{B}_{t}\supset\bar{B}_{s}\cap\bar{B}_{0}=\bar{B}_{s}$ for any $s\geqslant
t\geqslant 0$.

According to 2(b), the $\tfrac{\pi}{2}$-tractrix flow $\varphi_{t}$ is a
strong deformation retraction of $\bar{B}_{0}$ to $\bar{B}_{\frac{\pi}{2}}$.
By 2(c) $\varphi_{\frac{\pi}{2}}$ is a short. If $\kappa<1$, then by 2(d),
$\varphi_{\frac{\pi}{2}}$ is a strictly short retraction.

Since ${\mathcal{U}}$ is $\mathrm{CAT}(1)$, given a point $x\in
B(p,\pi)_{\mathcal{U}}$ there is unique geodesic $\gamma_{x}$ parametrized by
its length from $p$ to $x$. By $\mathrm{CAT}(1)$ comparison, the map

$\Theta(x)=\begin{cases}p&\text{if\ }|p-x|_{\mathcal{U}}\geqslant\pi,\\\
\gamma_{x}(\pi-|p-x|_{\mathcal{U}})&\text{if\
}|p-x|_{\mathcal{U}}<\pi.\end{cases}$

is a short retraction of ${\mathcal{U}}$ to
$\bar{B}(p,\tfrac{\pi}{2})_{\mathcal{U}}=\bar{B}_{0}\cap\mathcal{U}$. Moreover
$\Theta$ is strictly short retraction if $\kappa<1$.

Therefore the composition $\Phi=\varphi_{\frac{\pi}{2}}\circ\Theta$ induces a
short retraction of ${\mathcal{U}}$ to $K$ which is strictly short if
$\kappa<1$.

Finally, we need to take care of the case $\kappa<1$ and $p\notin K$. Denote
by $\bar{p}\in K$ the closest point to $p$; by $\mathrm{CAT}(\kappa)$
comparison it exists and unique. Note that
$|\bar{p}-x|_{\mathcal{U}}<|p-x|_{\mathcal{U}}$ for any $x\in K$; therefore
$K\subset B(\bar{p},\tfrac{\pi}{2})$. It remains to apply the construction
above with $\bar{p}$ instead $p$. ∎

Proof of 1. Consider the spherical join $\mathcal{U}\star\mathcal{U}$ and the
map $\iota$ described at the beginning of the section. Note that ➊ ‣ 3 implies
that the map $(u,v)\mapsto\iota(u,v,\tfrac{\pi}{4})$ induces a length
preserving map

$\Theta\colon{\tfrac{1}{\sqrt{2}}}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}(\mathcal{U}\times\mathcal{U})\to\mathcal{U}\star\mathcal{U}.$

In particular, $\Theta$ is short.

Note that the diagonal $\tfrac{1}{\sqrt{2}}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\Delta$ is a convex set in $\tfrac{1}{\sqrt{2}}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(\mathcal{U}\times\mathcal{U})$. Moreover ➊ ‣ 3
implies that the restriction of $\Theta$ to $\tfrac{1}{\sqrt{2}}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}\Delta$ is distance preserving. In particular,
the image $K=\Theta(\tfrac{1}{\sqrt{2}}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\Delta)$ is a weakly convex set in $\mathcal{U}\star\mathcal{U}$.

Further note that $|q-y|_{\mathcal{U}\star\mathcal{U}}\leqslant\tfrac{\pi}{2}$
for any $y\in\mathcal{U}\star\mathcal{U}$ and $q=\Theta(p,p)$. Applying 1, we
get a short retraction $\Phi\colon\mathcal{U}\star\mathcal{U}\to K$. Since
$\Theta$ is short, it induces the needed short retraction
$\Psi\colon\mathcal{U}\times\mathcal{U}\to\Delta$.

Finally, by 1, if $\kappa<1$, then $\Phi$ is a strictly short retraction and
therefore so is $\Psi$. ∎

##  Appendix A Time-dependent gradient flow

Here we prove the existence, uniqueness and contractivity of the gradient flow
for a time-dependent family of functions. The proof relies mostly on the
corresponding statements for time-independent families — with minor conditions
on the space. The same proof works nearly without changes for spaces with
lower curvature bound and it should work in nearly any space with well defined
angles between geodesics starting at one point.

Time-independent flow. Suppose $\mathcal{U}$ is a complete length
$\mathrm{CAT}(\kappa)$ space.

For a locally Lipschitz semiconcave function $f$ defined on an open set
$\mathop{\rm Dom}\nolimits f\subset\mathcal{U}$, the differential
$d_{p}f\colon\mathrm{T}_{p}\to\mathbb{R}$ is defined at each point
$p\in\mathop{\rm Dom}\nolimits f$; it is a concave, Lipschitz, and positive-
homogeneous of degree 1 function on the tangent space at $p$.

Further, for any point $p\in\mathop{\rm Dom}\nolimits f$ there is unique
tangent vector $u\in\mathrm{T}_{p}$ such that the following two conditions

$\displaystyle\langle u,w\rangle$ $\displaystyle\geqslant d_{p}f(w),$ ➊
$\displaystyle\langle u,u\rangle$ $\displaystyle=d_{p}f(u)$

hold for any tangent vector $w\in\mathrm{T}_{p}$.111Here _tangent vector_
means _element of tangent cone_ , we use this term despite the tangent cone is
not a vector space. The scalar product $\langle u,w\rangle$ is defined as
$|u|{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}|w|{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\cos\vartheta$ where $\vartheta$ is the angle between the vectors. The
vector $u$ is called the _gradient of $f$ at $p$_; briefly $u=\nabla_{p}f$.

A locally Lipschitz map $t\mapsto\alpha(t)$ is called _$f$ -gradient curve_ if
it satisfies the following equation

$\alpha^{+}(t)=\nabla_{\alpha(t)}f$ ➋

for any $t$. Here $\alpha^{+}(t)\in\mathrm{T}_{\alpha(t)}$ denotes the _right
velocity vector_ ; that is,

$\alpha^{+}(t)=\lim_{\varepsilon\to
0+}\frac{\log_{\alpha(t)}[\alpha(t+\varepsilon)]}{\varepsilon},$

where $v=\log_{p}q$ if the vector $v\in\mathrm{T}_{p}$ points form $p$ in the
direction of $q$ and $|v|=|p-q|$.

The following proposition can be extracted from [25, Theorem 1.7] or [26].

A.1. Proposition. Let ${\mathcal{U}}$ be a complete length
$\mathrm{CAT}(\kappa)$ space and $f$ a Lipschitz and semiconcave function
defined on an open set $\mathop{\rm Dom}\nolimits f\subset{\mathcal{U}}$. Then
for any point $p\in\mathop{\rm Dom}\nolimits f$ there is a unique $f$-gradient
curve $t\mapsto\alpha(t)$ with initial point $\alpha(0)=p$ defined on a
maximal semiopen interval $[0,T)$ for some $T\in(0,\infty]$. Moreover if
$T<\infty$ then $\alpha$ escapes from any closed set $K\subset\mathop{\rm
Dom}\nolimits f$.

Time-dependent gradient flow. Our next aim is to define a gradient flow for a
time-dependent family of functions and prove an analog of Proposition A for
this flow. Let $f_{t}$ be a family of functions defined on open subsets
$\mathop{\rm Dom}\nolimits f_{t}$ of $\mathcal{U}$. More precisely, we assume
that the parameter $t$ lies in a real interval $\mathbb{I}$ and

$\Omega=\\{\,{(x,t)\in\mathcal{U}\times\mathbb{I}}\,:\,{x\in\mathop{\rm
Dom}\nolimits f_{t}}\,\\}$

is an open subset in $\mathcal{U}\times\mathbb{I}$.

A family of functions $f_{t}$ is called _Lipschitz_ if the function
$(x,t)\mapsto f_{t}(x)$ is $L$-Lipschitz for some constant $L$.

A family of functions $f_{t}$ will be called _semiconcave_ if the function
$x\mapsto f_{t}(x)$ is $\lambda$-concave for each $t$. A family $f_{t}$ is
called _locally semiconcave_ if for each $(p_{0},t_{0})\in\Omega$ there is a
neighborhood $\Omega^{\prime}$ and $\lambda\in\mathbb{R}$ such that the
restriction of $f_{t}$ to $\Omega^{\prime}$ is $\lambda$-concave.

Note that one cannot expect that a direct generalization of equation ➋ ‣ A
holds for any family of functions $f_{t}$.

For example, consider a $1$-Lipschitz curve $\alpha$ in the real line. It is
reasonable to assume that $\alpha$ is an $f_{t}$-gradient curve for the family
$f_{t}(x)=-|x-\alpha(t)|$. (Indeed $\alpha$ can be realized as a limit of
gradient curves for a family of functions obtained by smoothing $f_{t}$.) On
the other hand, $\alpha^{+}(t)$ might be undefined, but even if it is defined,
$\alpha^{+}(t)\neq 0$ in general, while $\nabla_{\alpha(t)}f_{t}\equiv 0$.

Instead we define _$f_{t}$ -gradient curve_ as a Lipschitz curve $\alpha$ that
satisfies the following inequality for any point $p$, time $t$, and small
$\varepsilon>0$:

$\mathop{\rm dist}\nolimits_{p}\circ\alpha(t+\varepsilon)\leqslant\mathop{\rm
dist}\nolimits_{p}\circ\alpha(t)-\varepsilon{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}d_{\alpha(t)}f_{t}({\uparrow}_{\\![{\alpha(t)}{p}]})+o(\varepsilon),$ ➌

where ${\uparrow}_{\\![{q}{p}]}\in\mathrm{T}_{q}$ denotes a unit tangent
vector at $q$ in the direction of $p$ (if there is no geodesic
$[\alpha(t)\,p]$ then we impose no condition).

If $\alpha^{+}(t)=\nabla_{\alpha(t)}f_{t}$ for all $t$, then ➌ ‣ A holds; it
follows from ➊ ‣ A. On the other hand, the example above shows that the
converse does not hold; that is, ➌ ‣ A generalizes the definition ➋ ‣ A. Our
defining inequality ➌ ‣ A is closely related to the so called _evolution
variational inequality_ [27, Thm 4.0.4(iii)].

A.2. Distance estimate. Let $f_{t}$ and $h_{t}$ be two families of
$\lambda$-concave functions on a $\mathrm{CAT}(\kappa)$ space $\mathcal{U}$
and $s\geqslant 0$. Assume $f_{t}$ and $h_{t}$ have common domain
$\Omega\subset{\mathcal{U}}\times\mathbb{R}$ and $|f_{t}(x)-h_{t}(x)|\leqslant
s$ for any $(x,t)\in\Omega$. Assume $t\mapsto\alpha(t)$ and $t\mapsto\beta(t)$
are $f_{t}$\- and $h_{t}$-gradient curves respectively defined on a common
interval $t\in[a,b)$; set
$\ell(t)=\nobreak|\alpha(t)-\nobreak\beta(t)|_{\mathcal{U}}$. If for all $t$ a
minimizing geodesic $[\alpha(t)\,\beta(t)]$ lies in
$\\{\,{x\in{\mathcal{U}}}\,:\,{(x,t)\in\Omega}\,\\}$, then

$\ell^{\prime}(t)\leqslant\lambda{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\ell(t)+2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}s/\ell(t),$ ➍

assuming that the left hand side is defined. Moreover

$\ell(t)^{2}+\tfrac{2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}s}{\lambda}\leqslant(\ell(a)^{2}+\tfrac{2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}s}{\lambda}){\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}e^{2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\lambda{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}(t-a)}.$ ➎

In particular the inequalities hold for any $t\in\mathbb{I}$ if $\Omega\supset
B(p,2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}r)\times\mathbb{I}$ and
$\alpha(t),\beta(t)\in\nobreak B(p,r)$ for any $t\in\mathbb{I}$.

Note that if $f_{t}=h_{t}$ then $s=0$; in this case the second inequality can
be written as

$\ell(t)\leqslant\ell(a){\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}e^{\lambda{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}(t-a)}.$ ➏

In particular it implies uniqueness of the future of gradient curve with given
initial data. This inequality also makes it possible to estimate the distance
between two gradient curves for close functions. In particular, it implies
convergence of $f_{t}^{n}$-gradient curves if a sequence of $L$-Lipschitz and
$\lambda$-concave families $f^{n}_{t}$ converges uniformly as $n\to\infty$.

Proof. Fix a time moment $t$ and set $f=f_{t}$ and $h=h_{t}$. Let $p$ be the
midpoint of the geodesic $[\alpha(t)\beta(t)]$. Let
$\gamma\colon[0,\ell(t)]\to\mathcal{U}$ be an arc length parametrization of
$[\alpha(t)\beta(t)]$ from $\alpha(t)$ to $\beta(t)$. Note that
$d_{\alpha(t)}f({\uparrow}_{\\![{\alpha(t)}{p}]})$ is the right derivative of
$f\circ\gamma$ at $0$ and $-d_{\alpha(t)}h({\uparrow}_{\\![{\beta(t)}{p}]})$
is the left derivative of $h\circ\gamma$ at $\ell(t)$. Since $f$ and $h$ are
$\lambda$-concave,

$\displaystyle f(\beta(t))$ $\displaystyle\leqslant
f(\alpha(t))+\ell(t){\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}d_{\alpha(t)}f({\uparrow}_{\\![{\alpha(t)}{p}]})+\tfrac{1}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}\lambda{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\ell(t)^{2},$ $\displaystyle h(\alpha(t))$ $\displaystyle\leqslant
h(\beta(t))+\ell(t){\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}d_{\alpha(t)}h({\uparrow}_{\\![{\beta(t)}{p}]})+\tfrac{1}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}\lambda{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\ell(t)^{2},$

Adding these inequalities up and taking into account that $|f(x)-h(x)|<s$ for
any $x$, we conclude that

$d_{\alpha(t)}f({\uparrow}_{\\![{\alpha(t)}{p}]})+d_{\alpha(t)}h({\uparrow}_{\\![{\beta(t)}{p}]})\geqslant\lambda{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}\ell(t)+2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}s/\ell(t).$

Applying the triangle inequality and the definition of gradient curve at $p$,
we get that

$\displaystyle\ell(t+\varepsilon)$
$\displaystyle=|\alpha(t+\varepsilon)-\beta(t+\varepsilon)|\leqslant$
$\displaystyle\leqslant|\alpha(t+\varepsilon)-p|+|\beta(t+\varepsilon)-p|\leqslant$
$\displaystyle\leqslant|\alpha(t)-p|-\varepsilon{\hskip
0.5pt\cdot\nobreak\hskip
0.5pt}d_{\alpha(t)}f({\uparrow}_{\\![{\alpha(t)}{p}]})+|\beta(t+\varepsilon)-p|-\varepsilon{\hskip
0.5pt\cdot\nobreak\hskip
0.5pt}d_{\beta(t)}h({\uparrow}_{\\![{\beta(t)}{p}]})+o(\varepsilon)=$
$\displaystyle=\ell(t)-\varepsilon{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}(\lambda{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\ell(t)+2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}s/\ell(t))+o(\varepsilon)$

for $\varepsilon>0$; hence the statement.

Since $\alpha$ and $\beta$ are Lipschitz, $t\mapsto\ell(t)$ is a Lipschitz
function. By Rademacher’s theorem, its derivative $\ell^{\prime}$ is defined
almost everywhere and it satisfies the fundamental theorem of calculus.
Therefore ➍ ‣ A implies ➎ ‣ A. ∎

A.3. Proposition. Let $\mathcal{U}$ be a complete length
$\mathrm{CAT}(\kappa)$ space. Suppose $f_{t}$ is a family of $\lambda$-concave
functions for $t\in[a,b)$ and $\mathop{\rm Dom}\nolimits f_{t}\supset
B(z,2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}r)$ for some fixed
$z\in\mathcal{U}$, $r>0$ and any $t$.

Let $\alpha\colon[a,b)\to B(z,r)$ be Lipschitz. Then $\alpha$ is an
$f_{t}$-gradient curve if and only if

$\mathop{\rm dist}\nolimits_{p}\circ\alpha(t+\varepsilon)\leqslant\mathop{\rm
dist}\nolimits_{p}\circ\alpha(t)-\varepsilon{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\left[\frac{f_{t}(p)-f_{t}\circ\alpha(t)}{|p-\alpha(t)|}-\tfrac{\lambda}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|p-\alpha(t)|\right]+o(\varepsilon)$ ➐

for any $t\in[a,b)$ and $p\in B(z,r)\setminus\\{\alpha(t)\\}$.

Proof. Note that geodesics $[\alpha(t)p]$ lie in $\mathop{\rm Dom}\nolimits
f_{t}$ for any $t$.

Since $f_{t}$ is $\lambda$-concave, we have

$d_{\alpha(t)}f_{t}({\uparrow}_{\\![{\alpha(t)}{p}]})\geqslant\frac{f(p)-f\circ\alpha(t)}{|p-\alpha(t)|}-\tfrac{\lambda}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|p-\alpha(t)|.$

Hence the only-if part follows.

Given a point $p\in\mathcal{U}$ and $t$, consider a point
$\bar{p}\in[\alpha(t)p]$. Applying ➐ ‣ A for $\bar{p}$ and the triangle
inequality, we get

$\mathop{\rm dist}\nolimits_{p}\circ\alpha(t+\varepsilon)\leqslant\mathop{\rm
dist}\nolimits_{p}\circ\alpha(t)-\varepsilon{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\left[\frac{f(\bar{p})-f\circ\alpha(t)}{|\bar{p}-\alpha(t)|}-\tfrac{\lambda}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|\bar{p}-\alpha(t)|\right]+o(\varepsilon).$

By taking $\bar{p}$ close to $\alpha(t)$, the value
$\tfrac{f(\bar{p})-f\circ\alpha(t)}{|\bar{p}-\alpha(t)|}-\tfrac{\lambda}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|\bar{p}-\alpha(t)|$ can be made arbitrary
close to $d_{\alpha(t)}f_{t}({\uparrow}_{\\![{\alpha(t)}{p}]})$. Therefore,
given $\delta>0$, the following inequality

$\mathop{\rm dist}\nolimits_{p}\circ\alpha(t+\varepsilon)\leqslant\mathop{\rm
dist}\nolimits_{p}\circ\alpha(t)-\varepsilon{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}d_{\alpha(t)}f_{t}({\uparrow}_{\\![{\alpha(t)}{p}]})+\varepsilon{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}\delta$

holds for all sufficiently small positive values $\varepsilon$. Therefore ➌ ‣
A holds. ∎

Now we are ready to formulate and prove an analog of Proposition A for time-
dependent family.

A.4. Theorem. Let $\mathcal{U}$ be a complete length $\mathrm{CAT}(\kappa)$
space and $\\{f_{t}\\}$ a family of function defined on an open set
$\Omega=\\{\,{(x,t)\in\mathcal{U}\times\mathbb{R}}\,:\,{x\in\mathop{\rm
Dom}\nolimits f_{t}}\,\\}$. Suppose that $f_{t}$ is Lipschitz and locally
semiconcave. Then for any time moment $a$ and initial point $p\in\mathop{\rm
Dom}\nolimits f_{a}$ there is a unique $f_{t}$-gradient curve
$t\mapsto\alpha(t)$ defined on a maximal semiopen interval $[a,b)$. Moreover
if $b<\infty$, then $(\alpha(t),t)$ escapes from any closed set
$K\subset\Omega$.

Proof. Let $L$ be a Lipschitz constant of $f_{t}$. Fix $b>a$ sufficiently
small so that $\mathop{\rm Dom}\nolimits f_{t}\supset\nobreak
B(p,\varepsilon{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}L)$ for any $t\in[a,b)$.
Consider sequence $a=t_{0}<t_{1}\dots<t_{n}=\nobreak b$ and a piecewise
constant family of functions on $B(p,\varepsilon{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}L)$ defined by $\hat{f}_{t}=f_{t_{i}}$ if
$t_{i}\leqslant t<t_{i+1}$.

Note that $\hat{f}_{t}$ is time-independent on each interval
$[t_{i},t_{i+1})$. Applying A recursively on each interval $[t_{i},t_{i+1})$,
we get that the proposition holds for $\hat{f}_{t}$. That is, there is a
unique $\hat{f}_{t}$-gradient curve $\hat{\alpha}$ that starts at $p$ and
defined on the interval $[a,b)$.

The distance estimates (A) show that as the partition gets finer, the gradient
curves $\hat{\alpha}$ form a Cauchy sequence; denote its limit by $\alpha$.
Then

$\displaystyle\mathop{\rm dist}\nolimits_{p}\circ\hat{\alpha}(t+\varepsilon)$
$\displaystyle\leqslant\mathop{\rm
dist}\nolimits_{p}\circ\hat{\alpha}(t)-\varepsilon{\hskip
0.5pt\cdot\nobreak\hskip
0.5pt}\left[\frac{\hat{f}_{t}(p)-\hat{f}_{t}\circ\hat{\alpha}(t)}{|p-\alpha(t)|}-\tfrac{\lambda}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|p-\hat{\alpha}(t)|\right]+o(\varepsilon)$
$\displaystyle\leqslant\mathop{\rm
dist}\nolimits_{p}\circ\hat{\alpha}(t)-\varepsilon{\hskip
0.5pt\cdot\nobreak\hskip
0.5pt}\left[\frac{f_{t}(p)-f_{t}\circ\hat{\alpha}(t)-2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}s}{|p-\alpha(t)|}-\tfrac{\lambda}{2}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}|p-\hat{\alpha}(t)|\right]+o(\varepsilon)$

where

$s=\sup_{t,x}\\{|f_{t}(x)-\hat{f}_{t}(x)|\\}.$

Since $s\to 0$ as $\hat{\alpha}\to\alpha$, we get that ➐ ‣ A holds for
$\alpha$; that is, $\alpha$ is an $f_{t}$-gradient curve.

It proves a short time existence. Applying this argument recursively we can
find a gradient curve defined on a maximal interval $[a,b)$. Uniqueness of
this curve follows from the distance estimate ➏ ‣ A.

Note that $\alpha$ is $L$-Lipschitz. In particular, if $b<\infty$, then
$\alpha(t)\to p^{\prime}$ as $t\to b$. If $(p^{\prime},b)\in\Omega$, then we
can repeat the procedure, otherwise $\alpha$ escapes from any closed set in
$\Omega$. ∎

##  Appendix B Another way

Here we indicate an alternative way to prove Theorem 1. The idea is taken from
the proof of Kirszbraun’s theorem; see [28, 5.1] or [9, 9.4.1 and 9.6.5].

Proof of 1. Set $\mathring{\mathcal{U}}=\mathop{\rm
Cone}\nolimits\mathcal{U}$. Denote by $\mathring{K}$ the subcone of
$\mathring{\mathcal{U}}$ spanned by $K$. The space $\mathcal{U}$ is the unit
sphere in $\mathring{\mathcal{U}}$ with angle metric; that is,
$\mathcal{U}=\\{\,{z\in\mathring{\mathcal{U}}}\,:\,{|z|=1}\,\\}$ and
$|u-v|_{\mathcal{U}}=\measuredangle[o\,{}^{u}_{v}]$, where $o$ denotes the tip
of the cone $\mathring{\mathcal{U}}$.

Note that $\mathring{\mathcal{U}}$ is a $\mathrm{CAT}(0)$ space and
$\mathring{K}$ forms a convex closed subset of $\mathring{\mathcal{U}}$. In
particular, for any point $x$ there is unique point $\hat{x}\in\mathring{K}$
that minimize the distance to $x$; that is, $|\hat{x}-x|=\mathop{\rm
dist}\nolimits_{K}(x)$.

Consider the ray $\alpha_{o}\colon t\mapsto t{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}p$ in $\mathring{\mathcal{U}}$. Note that given
$s\in\mathring{\mathcal{U}}$ the geodesics $[s\ t{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}p]$ converge as $t\to\infty$ to a ray, say
$\alpha_{s}\colon[0,\infty)\to\mathring{\mathcal{U}}$ that is parallel to
$\alpha_{o}$.

Note that if $|x|=1$, then $|\hat{x}|\leqslant 1$. By assumption for any
$k\in\mathring{K}$ the function $t\mapsto|\alpha_{k}(t)|$ is monotonically
increasing. Therefore there is unique value $t_{x}\geqslant 0$ such that
$|\alpha_{\hat{x}}(t_{x})|=1$; set $x^{\prime}=\alpha_{\hat{x}}(t_{x})$ and
define the map $\Phi$ as $x\mapsto x^{\prime}$.

Evidently $x\mapsto x^{\prime}$ is a retraction of $\mathcal{U}$ to $K$; that
is, $\Phi(x)\in K$ for any $x\in\mathcal{U}$ and $\Phi(k)=k$ for any $k\in K$.

It remains to show that $x\mapsto x^{\prime}$ is short which can be done by
straightforward lengthy computations. We leave it as an advanced exercise to
the reader. ∎

## References

  * [1] W. Kendall “Probability, convexity, and harmonic maps with small image. I. Uniqueness and fine existence” In _Proc. London Math. Soc. (3)_ 61.2, 1990, pp. 371–406 DOI: 10.1112/plms/s3-61.2.371
  * [2] T. Yokota “Convex functions and barycenter on CAT(1)-spaces of small radii” In _J. Math. Soc. Japan_ 68.3, 2016, pp. 1297–1323 DOI: 10.2969/jmsj/06831297
  * [3] C. Breiner et al. “Regularity of harmonic maps from polyhedra to CAT(1) spaces” In _Calc. Var. Partial Differential Equations_ 57.1, 2018, pp. Art. 1235 DOI: 10.1007/s00526-017-1279-5
  * [4] B. Fuglede “Harmonic maps from Riemannian polyhedra to geodesic spaces with curvature bounded from above” In _Calc. Var. Partial Differential Equations_ 31.1, 2008, pp. 99–136 DOI: 10.1007/s00526-007-0107-8
  * [5] T. Serbinowski “Harmonic maps into metric spaces of curvature bounded from above” In _Thesis, University of Utah_ , 1996
  * [6] A. Lytchak and S. Stadler “Improvements of upper curvature bounds” to appear in Trans. Amer. Math. Soc., 2019 arXiv:1910.05287 [math.DG]
  * [7] S. Wenger “Plateau’s problem for integral currents in locally non-compact metric spaces” In _Adv. Calc. Var._ 7.2, 2014, pp. 227–240 DOI: 10.1515/acv-2012-0018
  * [8] C. Guo and S. Wenger “Area minimizing discs in locally non-compact metric spaces” to appear in Comm. Anal. Geom. arXiv:1701.06736 [math.MG]
  * [9] S. Alexander, V. Kapovitch and A. Petrunin “Alexandrov geometry: preliminary version no. 1” arXiv:1903.08539v1 [math.DG]
  * [10] N. Korevaar and R. Schoen “Sobolev spaces and harmonic maps for metric space targets” In _Comm. Anal. Geom._ 1.3-4, 1993, pp. 561–659
  * [11] L. Ambrosio and B. Kirchheim “Currents in metric spaces” In _Acta Math._ 185.1, 2000, pp. 1–80 DOI: 10.1007/BF02392711
  * [12] A. Lytchak and S. Wenger “Area minimizing discs in metric spaces” In _Arch. Ration. Mech. Anal._ 223.3, 2017, pp. 1123–1182 DOI: 10.1007/s00205-016-1054-3
  * [13] K.. Sturm “Probability measures on metric spaces of nonpositive curvature” In _Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002)_ 338, Contemp. Math. Amer. Math. Soc., Providence, RI, 2003, pp. 357–390 DOI: 10.1090/conm/338/06080
  * [14] D. Burago, S. Ferleger and A. Kononenko “Uniform estimates on the number of collisions in semi-dispersing billiards” In _Ann. of Math. (2)_ 147.3, 1998, pp. 695–708 DOI: 10.2307/120962
  * [15] P. Creutz “Plateau’s problem for singular curves” arXiv:1904.12567 [math.DG]
  * [16] S. Stadler “The structure of minimal surfaces in CAT(0) spaces” to appear in J. Eur. Math. Soc. arXiv:1808.06410 [math.DG]
  * [17] В.. Шарафутдинов “О выпуклых множествах в многообразии неотрицательной кривизны” In _Матем. заметки_ 26.1, 1979, pp. 129–136
  * [18] S. Alexander, R. Bishop and R. Ghrist “Total curvature and simple pursuit on domains of curvature bounded above” In _Geom. Dedicata_ 149, 2010, pp. 275–290 DOI: 10.1007/s10711-010-9481-z
  * [19] C. Jun “Pursuit-evasion and time-dependent gradient flow in singular spaces” Thesis (Ph.D.)–University of Illinois at Urbana-Champaign, 2012 URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:3570501
  * [20] C. Jun “Continuous pursuit curves on ${\rm CAT}(K)$ spaces” In _Geom. Dedicata_ 173, 2014, pp. 309–330 DOI: 10.1007/s10711-013-9944-0
  * [21] C. Jun “Time-dependent gradient curves on CAT(0) spaces” arXiv:1801.04583 [math.MG]
  * [22] L. Ferreira and J.. Valencia-Guevara “Gradient flows of time-dependent functionals in metric spaces and applications to PDEs” In _Monatsh. Math._ 185.2, 2018, pp. 231–268 DOI: 10.1007/s00605-017-1037-y
  * [23] A. Mielke, R. Rossi and G. Savaré “Nonsmooth analysis of doubly nonlinear evolution equations” In _Calc. Var. Partial Differential Equations_ 46.1-2, 2013, pp. 253–310 DOI: 10.1007/s00526-011-0482-z
  * [24] M.. Bridson and A. Haefliger “Metric spaces of non-positive curvature” 319, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 1999 DOI: 10.1007/978-3-662-12494-9
  * [25] A. Lytchak “Open map theorem for metric spaces” In _Algebra i Analiz_ 17.3, 2005, pp. 139–159 DOI: 10.1090/S1061-0022-06-00916-2
  * [26] S. Ohta and M. Pálfia “Gradient flows and a Trotter-Kato formula of semi-convex functions on ${\rm CAT}(1)$-spaces” In _Amer. J. Math._ 139.4, 2017, pp. 937–965 DOI: 10.1353/ajm.2017.0025
  * [27] L. Ambrosio, N. Gigli and G. Savaré “Gradient flows in metric spaces and in the space of probability measures”, Lectures in Mathematics ETH Zürich, 2008
  * [28] S. Alexander, V. Kapovitch and A. Petrunin “Alexandrov meets Kirszbraun” In _Proceedings of the Gökova Geometry-Topology Conference 2010_ Int. Press, Somerville, MA, 2011, pp. 88–109