\section{Introduction}
This article studies optimal transportation in Lorentz-Finsler manifolds from a geometric point of view. Geometric in this context denotes, among others things taking the perspective of
spacetimes according to the idea, basic to the theory of relativity, that there is no canonical isochronicity. Considering a transport problem on a space $N$ and the interval $[0,1]$
is in geometric terms studying a problem on the product space $N\times [0,1]$ with boundary values on $N\times \{0\}$ and $N\times \{1\}$ and the canonical projection $N\times
[0,1]\mapsto [0,1]$ as the time parameter. The surfaces $N\times \{t\}$ are thus surfaces of isochronicity. In Lorentzian geometry this amounts to a special case since measures can be
for example concentrated on achronal or nonsmooth sets, e.g. $\partial J^-(p)$. Seen the other way around one can say that measures relevant in Lorentzian
geometry might not only be distributed in space, but in time as well.

The first one to take notice of the problem of optimal transportation in Lorentzian geometry was \cite{brenier1}. Therein a transportation problem is proposed,
which only weakly disguised is the problem of transportation between parallel spacelike hyperplanes in Minkowski space with respect to the Lorentzian
distance extended by $\infty$. Here a strong form of isochronicity is assumed for the support of each measure.
Following this formulation \cite{berpue} generalized the problem to a wider class of functions called {\it relativistic costs},
and gave inter alia a solution to the Monge problem while staying in the same basic geometric frame.

The {\it early universe reconstruction problem}, studied in \cite{br2} and \cite{fr} with methods of optimal transportation, asks whether one can construct
the trajectories of masses from the big bang to their present day positions in Robertson-Walker spacetimes. A mathematical formulation for general
globaly hyperbolic spacetimes would read as follows: Given two measures, one concentrated on a Cauchy hypersurface, the other on the past cone
of a point. Then what can be said about the trajectories of the minimizers in a dynamical optimal coupling of the two measure?
\cite{fr} gives a justification to why the problem can be studied with methods from optimal transportation.

The results in this article generalize the previous approaches to the problem of Lorentzian optimal transportation. Further new results on the structure
of minimal couplings are given. In section \ref{results} the setting and the theorems are described. Proofs are given in section \ref{proofs}.

{\it Acknowledgement:}
The author would like to thank Victor Bangert for suggesting the problem of optimal transportation in the context of Lorentzian geometry and Albert
Fathi for encouraging the pursuit of the project. The author would further like to thank Patrick Bernard for providing the opportunity to carry out the ideas
for this article and making numerous suggestions which helped to shape the exposition of the present results. Valentine Roos and Rodolfo R\'ios-Zertuche
are kindly thanked for many helpful discussions in the process of this research.

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme
(FP/2007-2013) /ERC Grant Agreement  307062.

\section{The results}\label{results}

Let $M$ be a smooth manifold. Throughout the article a fixed choice of a complete Riemannian metric $h$ on $M$ is made.
Consider a smooth and function $\mathbb{L}\colon TM\setminus \overline{0}\to \mathbb R$ (here $\overline{0}$ denotes the zero section in $TM$)
positive homogenous of degree $2$ such that the second fiber derivative is nondegenerate with index $\dim M-1$. A cone structure $\mathcal{C}$ on $M$ is a subset of $TM$
such that $\pi_{TM}(\mathcal{C}) =M$, $\mathbb R_+\cdot \mathcal{C}=\mathcal{C}$  and $\mathcal{C}_p:=\mathcal{C}\cap TM_p$ convex for all $p\in M$. A {\it causal structure}
$\mathcal{C}$ of $(M,\mathbb{L})$ is then a choice of a cone structure $\mathcal{C}$ such that $\mathbb{L}|_{\inte\mathcal{C}}>0$ and $\partial\mathcal{C}\setminus\overline{0}$
is a connected component of $\{\mathbb{L}=0\}$. Causal strutures are known to exist up to a finite cover, see \cite{minguzzi141}. Actually more is true:
Every tangent space $TM_p$ is intersected by $\{\mathbb{L}>0\}$ in a nonempty set. Further every connected component of $TM_p\cap \{\mathbb{L}>0\}$ is a strictly convex cone
and belongs to a unique causal structure up to a finite covering of $M$.

Fix a causal structure $\mathcal{C}$ for $(M,\mathbb{L})$. Define a new Lagrangian $L$ on $\mathcal{C}$ by setting
$$L(v):=\begin{cases}
-\sqrt{\mathbb{L}(v)},& \text{ for }v\in \mathcal{C},\\
\infty,&\text{ otherwise.}
\end{cases}$$
$L$ is a fiberwise convex function, finite on its domain and positive homogeneous of degree one. Note that $L$ is smooth on $\inte\mathcal{C}$. The function $L$ has the features
of a Finsler metric of Lorentzian type. This justifies to call the pair $(M,L)$ a {\it Lorentz-Finsler manifold}.  The generality of Lorentz-Finsler
geometry is chosen in view of recent developments in the area, see e.g. \cite{jasa}, \cite{minguzzi141}, \cite{minguzzi142}, \cite{minguzzi143}, and the goal
to achieve a scope comparable to the one of Tonelli-Lagrangian systems, see e.g. \cite{bebu1}, \cite{bebu2} and \cite{fafi}.

One calls an absolutely continuous curve $\gamma\colon I\to M$ {\it ($\mathcal{C}$-)causal} if $\dot\gamma\in \mathcal{C}$ whenever the tangent vector exists. A causal curve
$\gamma\colon I\to M$ is {\it timelike} if for all $s\in I$ there exists $\e,\delta>0$ such that $\dist(\dot\gamma(t),\partial\mathcal{C})\ge \e |\dot\gamma(t)|$,  for every $t\in I$
for which $\dot\gamma(t)$ exists and $|s-t|<\delta$. Define the Lagrangian action relative to $L$:
$$\mathcal{A}(\gamma):=\begin{cases}
\int L(\dot\gamma)dt,&\text{ if $\gamma$ is $\mathcal{C}$-causal,}\\
\infty,&\text{ else.}
\end{cases}$$

Denote with $J^+(p)$ the set of points $q\in M$ such that there exists a causal curve with initial and terminal point $p$ and $q$, respectively.
$J^-(p)$ is defined with the roles of $p$ and $q$ exchanged as initial and terminal point. $I^+(p)$ and $I^-(p)$ have the same definition as $J^\pm(p)$ with causal replaced by
timelike. Define the set
$$J^+:=\{(p,q)\in M\times M|\; q\in J^+(p)\}.$$
For an open set $U\subseteq M$ define $J^\pm_U$ and $I^\pm_U$ as before for the restriction $(U,\mathcal{C}|_U)$.

A Lorentz-Finsler manifold is said to be {\it causal} if it does not admit a closed causal curve.

\begin{definition}
A causal Lorentz-Finsler manifold $(M,L)$ is {\it globally hyperbolic} if the sets $J^+(p)\cap J^-(q)$ are compact for all $p,q\in M$.
\end{definition}

From \cite{suhr1} it follows that for globally hyperbolic Lorentz-Finsler spacetimes there exists a diffeomorphism (called a {\it splitting}) $M\cong \mathbb R\times N$ such that the projection
$\tau\colon \mathbb R\times N\to \mathbb R$, $(\theta,v)\mapsto \theta$ satisfies $-d\tau \le L$. Note that this diffeomorphism is by far not unique. In the spirit of the present approach all results are
formulated with as ittle reference to a splitting as possible. Note that for compactly supported measures all results are indeed independent of the splitting.

The following result is proven in the same fashion as in the Lorentzian case (see \cite{minguzzi142} for the results on local minimizers).

\begin{prop}
Let $(M,L)$ be globally hyperbolic. Then for every pair of points $p,q$ with $q\in J^+(p)$ there exists a minimizer of $\mathcal{A}$ with finite action connecting
the two points. The minimizer $\gamma$ solves the Euler-Lagrange equation of $\mathbb{L}$ up to monotone reparameterization and one has $\dot\gamma\in\mathcal{C}$ everywhere.
\end{prop}

For a globally hyperbolic Lorentz-Finsler manifold define the cost function relative to $L$:
$$c_L(x,y):=\min\left\{\left.\mathcal{A}(\gamma)\right|\; \gamma\text{ connects $x$ and $y$}\right\}\in \mathbb R\cup \{\infty\}$$
The following proposition is a direct consequence of \cite{villani}, Theorem 4.1.

\begin{prop}\label{P1}
Let $\mu,\nu$ be probability measures on $M$ such that there exists a splitting with $\tau\in L^1(\mu)\cap L^1(\nu)$. Then there exists a coupling $\pi$ of $\mu$
and $\nu$ which minimizes the total cost $\int c_L d\pi\in\mathbb R\cup\{\infty\}$.
\end{prop}

Denote with $C_{L}(\mu,\nu)$ the minimal costs relative to $c_L$ of couplings between $\mu$ and $\nu$, i.e.
$$C_{L}(\mu,\nu):=\inf\left\{\left.\int c_{L}d\pi\right|\pi\in\Pi(\mu,\nu)\right\}\in \mathbb R\cup\{\infty\}.$$

The abstract existence result in Proposition \ref{P1} immediately raises the question: Under what assumptions does a finite coupling exists? The simplest case is that of two
Dirac measures $\mu=\delta_x$ and $\nu=\delta_y$. Then a finite coupling exists iff $y\in J^+(x)$ iff $\nu(J^+(A))\ge \mu(A)$ and $\mu(J^-(A))\ge \nu(A)$
for all measurable $A\subseteq M$ where $J^\pm (A):=\{y|\; y\in J^\pm(x)\text{ for some }x\in A\}$. The necessity of the condition was noticed in \cite{berpue} for relativistic cost
functions and general measures.

The problem though can be formulated in a more abstract setting. Let $(\mathcal{X},d_\mathcal{X})$ and $(\mathcal{Y},d_\mathcal{Y})$ be locally compact Polish spaces.
Denote with $\pi_1\colon \mathcal{X}\times \mathcal{Y}\to \mathcal{X}$ and $\pi_2\colon \mathcal{X}\times \mathcal{Y}\to \mathcal{Y}$ the canonical projections
and consider a closed set $J\subseteq \mathcal{X}\times \mathcal{Y}$. For $x\in \mathcal{X}$ define $J^+(x):= \pi_2(\pi_1^{-1}(x)\cap J)$ and
for $y\in \mathcal{Y}$ define $J^-(y):= \pi_1(\pi_2^{-1}(y)\cap J)$. Further set $J^+(A):= \pi_2(\pi_1^{-1}(A)\cap J)$ for $A\subseteq \mathcal{X}$
and $J^-(B):= \pi_1(\pi_2^{-1}(B)\cap J)$ for $B\subseteq \mathcal{Y}$.

\begin{definition}\label{defcaurel}
Two probability measures are {\it $J$-related} if there exists a coupling $\pi$ with $\pi(J)=1$.
\end{definition}

For $\mathcal{X}=\mathcal{Y}=M$, $J:=J^+$ and two probability measures $\mu,\nu\in \mathcal{P}(M)$ such that there exists a splitting with $\tau\in L^1(\mu)\cap L^1(\nu)$
the $J$-relation is equivalent to the finiteness of the minimal cost, i.e. $C_{L}(\mu,\nu)<\infty$.

\begin{theorem}\label{P2}
Let $(\mathcal{X},d_\mathcal{X})$ and $(\mathcal{Y},d_\mathcal{Y})$ be Polish spaces and $J\subseteq \mathcal{X}\times \mathcal{Y}$ closed. Further let $\mu\in
 \mathcal{P}(\mathcal{X}),\nu\in \mathcal{P}(\mathcal{Y})$ be probability measures. Then the following are equivalent:
\begin{itemize}
\item[(1)] $\mu$ and $\nu$ are $J$-related.
\item[(2)] $\nu(J^+(A))\ge \mu(A)$ and $\mu(J^-(B))\ge \nu(B)$ for all measurable $A\subseteq \mathcal{X}$ and $B\subseteq \mathcal{Y}$.
\end{itemize}
\end{theorem}

After adressing the existence problem of minimal couplings attention turns towards the structure of the minimal couplings. Recall that a set $A\subseteq M\times M$
is {\it $c_L$-cyclically monotone} if for all $\{(x_i,y_i)\}_{1\le i\le n} \subseteq A$ one has
$$\sum c_L(x_i,y_i)\le \sum c_L(x_i,y_{\sigma(i)})$$
for all $\sigma \in S(n)$. From \cite{ap} then follows:

\begin{prop}\label{propcycmon}
Let $\mu,\nu$ be two $J^+$-related probability measures on $M$ such that there exists a splitting with $\tau\in L^1(\mu)\cap L^1(\nu)$.
\begin{enumerate}
\item[(1)] One has
$$C_L(\mu,\nu)= \sup\left(\int_{M} \phi(y) d\nu(y)-\int_M \psi(x)d\mu(x)\right)$$
where the supremum is taken over the functions $\psi\in L^1(\mu),\phi\in L^1(\nu)$ with $\phi(y)-\psi(x)\le c_L(x,y)$.
\item[(2)] Every optimal transport plan $\pi$ is concentrated on a $c_L$-cyclic monotone Borel subset of $M\times M$.
\end{enumerate}
\end{prop}

Denote denote with $\Gamma(\tau)$ the set of minimizers $\gamma$ of $\mathcal{A}$ such that $d\tau(\dot\gamma)\equiv \text{const}(\gamma)$.
For $(x,y)\in J^+$ consider the subspace
$$\Gamma_{x\to y}:=\{\gamma\in \Gamma(\tau)|\; \ev\nolimits_0(\gamma)=x,\; \ev\nolimits_1(\gamma)=y\}$$
and $\Gamma:=\cup_{(x,y)\in J^+} \Gamma_{x\rightarrow y}$. Set $\EV\colon \Gamma\times [0,1]\to M$, $(\gamma,t)\mapsto \gamma(t)$ and
$\ev_t:=\ev(.,t)$. Recall the definition of optimal dynamical coupling from \cite{villani}.

\begin{definition}
A {\it dynamical optimal coupling} is a probability measure $\Pi$ on $\Gamma$ such that $\pi:=(\ev_0,\ev_1)_\sharp \Pi$ is a minimal coupling between
$\mu_0:=(\ev_0)_\sharp\Pi$ and $\mu_1:=(\ev_1)_\sharp \Pi$.
\end{definition}

\begin{prop}\label{dynoptcou}
Let $\mu_0$ and $\mu_1$ be $J^+$-related probability measures with $\tau\in L^1(\mu_0)\cap L^1(\mu_1)$ for some splitting. Then there exists a dynamical optimal coupling $\Pi$
for $\mu_0$ and $\mu_1$ with $\supp\Pi\subseteq \Gamma$.
\end{prop}

Define the map $\tev\colon \Gamma\times [0,1]\to PTM$, $(\gamma,t)\mapsto [\dot\gamma(t)]\in PTM_{\gamma(t)}$ where $PTM$ denotes the projective tangent bundle.
For the canonical projection $P\colon PTM\to M$ one has $\EV =P\circ \tev$.

\begin{theorem}\label{intermediateregularity}
Let $\mu,\nu\in \mathcal{P}(M)$ be $J^+$-related with disjoint supports such that $\tau\in L^1(\mu)\cap L^1(\nu)$ for some splitting. Then every dynamical optimal coupling
$\Pi$ has the following property: The canonical projection $P$ restricted to the image of $T:=\tev(\supp\Pi\times ]0,1[)$ is injective. Further the inverse $(P|_{T})^{-1}$ is locally H\"older
continuous with exponent $1/2$.
\end{theorem}

\begin{examp}
It is not difficult to construct examples that show the optimality of the H\"older continuity in the claim. Consider Minkowski space $(\mathbb R^3,\langle.,.\rangle_1)$, i.e.
the Lorentz-Finsler metric $L|_\mathcal{C}=-\sqrt{z^2-x^2-y^2}$ on the cone structure
$$\mathcal{C}:=\{x^2+y^2-z^2\le 0, z\ge 0\}.$$
The intersection of $J^+(x,0,0)\cap \{z=1\}$ for $(x,0,0)$ are discs of radius $1$ around $(x,0,1)$. The union
of the boundaries of these discs form a foliation near $\{(x+1,0,1)|\;0\le x\le 1\}$ transverse to $\{(x+1,0,1)|\;0\le x\le 1\}$. In other words there exists a map
$\Phi\colon [0,1]\times (-\e,\e)\to  \{z=1\}$, a diffeomorphism onto its image, with $\Phi(x,0)=(x+1,0,1)$ and $\Phi(x,.)$ traces the boundary of $J^+(x,0,0)\cap \{z=1\}$
near $(x+1,0,1)$.

Consider $\mu$ to be the $1$-dimensional Lebesgue measure concentrated on $[0,1]\times \{0\}\times \{0\}$. Choose any measureable map $f\colon [0,1]\to (-\e,\e)$ and consider
$\nu:=(\Phi\circ (\id,f,0)_\sharp \mu$.
It is easy to see that $\mu$ and $\nu$ are causally related by the obvious coupling. Further the coupling is unique. For $f$ chosen appropriately one sees that
the intermediate regularity is at most $1/2$-H\"older.
\end{examp}

The map $P^{-1}$ in the theorem is always Lipschitz for $\dim M=2$, i.e. $M$ is a surface. This is a well know fact for positive definite Lagrangians relying on the fact that trajectories
(1) solve a differential equation with smooth coefficients and (2) have codimension $1$ in a surface. These facts carry over readily to this case.

\begin{theorem}\label{lipreg}
Let $\mu,\nu\in \mathcal{P}(M)$ be $J^+$-related with disjoint supports and $\tau\in L^1(\mu)\cap L^1(\nu)$ for some splitting. Further let $K$ be a compact subset of $\inte\mathcal{C}$.
Then the canonical projection $P$ restricted to the image of $\tev(\supp\Pi\times ]0,1[)\cap K$ is Lipschitz for every dynamical optimal coupling $\Pi$.
\end{theorem}

Recall that a set $X$ is called {\it achronal} if every timelike curve meets it at most once. Using a splitting one sees that $X$ can be written as the graph of a function $f_X$ over a subset of $N$.
With the same proof as for Proposition 14.25 in \cite{oneill}, one sees that $f_X$ is locally Lipschitz. Now one can use a Lipschitz-continuous extension of $f_X$ to $N$ to say that $X$ is the subset of a
locally Lipschitz hypersurface.

A locally Lipschitz hypersurface $X$ has a tangent  space almost everywhere and with the induced Riemannian metric defines a Lebesgue measure $\mathcal{L}_X$ on $X$. A measure
concentrated on $X$ is called {\textit absolutely continuous} with respect to the Lebesgue measure if it is absolutely continuous with respect to $\mathcal{L}_X$. Note that this definition is
independent of the chosen Riemannian metric since any pair of Lebesgue measures induced by Riemannian metrics are absolutely continuous with respect to each other.

Call a hypersurface $Y$ {\it locally uniformly spacelike} if for one (hence every) splitting there exists a locally Lipschitz continuous function $f_Y\colon N\to \mathbb R$ with $Y$ being the graph
of $f_Y$ and for all compact $K\subseteq M$ there exists $\varepsilon >0$, such that the Hausdorff distance between $TY_y\cap T^1 M$ and $\mathcal{C}^1=\mathcal{C}
\cap T^1M$ is bounded below by $\varepsilon$ for all $y\in K\cap \Gamma$ such that $TY_y$ exists. $T^1M$ denotes the unit tangent bundle of $h$.
With these notions the following generalization of Theorem 4.3 in \cite{berpue} can be proven.

\begin{theorem}\label{Thmmonge}
Let $\mu,\nu\in\mathcal{P}(M)$ be $J^+$-related such that $\tau\in L^1(\mu)\cap L^1(\nu)$ for some splitting. Assume that $\mu$ and $\nu$ are concentrated
on a locally uniformly spacelike hypersurface $A$ and an achronal set $B$ respectively. Further assume that $\mu$ is
absolutely continuous with respect to the Lebesgue measure on $A$. Then there exists a unique optimal coupling $\pi$ and a
Borel map $F\colon M\to M$ such that $\pi=(\id,F)_\sharp \mu$.
\end{theorem}

The theorem becomes false if both $A$ and $B$ are allowed to be achronal only. E.g. consider subsets of
$\partial J^-(p)$ in Minkowski space for some $p\in \mathbb R^{n+1}$. For suitable choices of $A$ and $B$ not every minimal coupling is
supported on a graph. More precisely every causal coupling has vanishing cost, but not every causal coupling is supported on a graph.
Further the theorem is in general not true if $\mu$ is assumed to be absolutely continuous with respect to the Lebesgue measure on $M$. Again examples can
be constructed in Minkowski space. Note that in the present formulation the problem bears greater resemblance to the classical Monge
problem for distance functions.

\section{The proofs}\label{proofs}

\subsection{Proof of Theorem \ref{P2}}

(1)$\Rightarrow$(2):  For any (measurable) set $B\subseteq \mathcal{Y}$ one has
$$\pi_2^{-1}(B)\cap J\subseteq \pi_1^{-1}(J^-(B)).$$
Since $\nu(B)=\pi(\pi_2^{-1}(B))=\pi(\pi_2^{-1}(B)\cap J)$ and $\mu(J^-(B))=\pi(\pi_1^{-1}(J^-(B)))$, the claim follows. The other inclusion is analogous.

(2)$\Rightarrow$(1): For this part of the proof one needs two lemmata.

\begin{lemma}\label{L2}
Let $\mu$ and $\nu$ be $J$-related. If there exists a measurable set $A\subseteq \mathcal{X}$ such that $0<\mu(A)= \nu(J^+(A))<1$ then the pairs
$$(\mu_A,\nu_A):=\left(\frac{1}{\mu(A)}\mu|_{A}, \frac{1}{\mu(A)}\nu|_{J^+(A)}\right)$$
and
$$(\mu_{A^c},\nu_{A^c}):=\left(\frac{1}{\mu(A^c)}\mu|_{A^c}, \frac{1}{\mu(A^c)}\nu|_{J^+(A)^c}\right)$$
satisfy the condition in Theorem \ref{P2} (2).

If $0<\nu(B)= \mu(J^-(B))<1$ for $B\subseteq \mathcal{Y}$ measureable the pairs
$$(\mu_B,\nu_B):=\left(\frac{1}{\nu(B)}\mu|_{J^-(B)}, \frac{1}{\nu(B)}\nu|_{B}\right)$$
and
$$(\mu_{B^c},\nu_{B^c}):=\left(\frac{1}{\nu(B^c)}\mu|_{J^-(B)^c}, \frac{1}{\nu(B^c)}\nu|_{B^c}\right)$$
satisfy the condition in Theorem \ref{P2} (2).
\end{lemma}

\begin{proof}
It suffices to consider the first case. The second case follows by exchange of $\mathcal{X}$ and $\mathcal{Y}$.
So assume $\mu(A)= \nu(J^+(A))$ for some measurable set $A\subseteq \mathcal{X}$ with
$\mu(A)\in (0,1)$. First note that all four measures $\mu_A$, $\nu_A$, $\mu_{A^c}$ and $\nu_{A^c}$ are probability measures by the assumption. One has
\begin{align*}
\mu_A(B)=\frac{1}{\mu(A)} \mu(B\cap A)&\le \frac{1}{\mu(A)} \nu(J^+(B\cap A))\\
&= \frac{1}{\mu(A)} \nu(J^+(B)\cap J^+(A))= \nu_A(J^+(B))
\end{align*}
which shows $\mu_A(B)\le \nu_A(J^+(B))$.

Next note that $\mu(A^c)=\nu(J^+(A)^c)$. Assume that there exists a measurable set $C\subseteq \mathcal{X}$ with $\nu_{A^c}(J^+(C))<\mu_{A^c}(C)$, i.e.
$$\nu(J^+(C)\cap J^+(A)^c)=\nu|_{J^+(A)^c}(J^+(C)) < \mu|_{A^c}(C)=\mu(C\cap A^c).$$
Then a contradiction follows from
$$\mu(C\cup A)=\mu(C\cap A^c)+\mu(A)>\nu(J^+(C)\cap J^+(A)^c)+\nu(J^+(A))=\nu(J^+(C\cup A))$$
since $J^+(C)\cup J^+(A)=J^+(C\cup A)$. Therefore one has $\mu_{A^c}(C)\le \nu_{A^c}(J^+(C))$ for all measurable $C\subseteq \mathcal{X}$. This shows the
first set of inequalities.

It remains to show $\mu_A(J^-(D))\ge \nu_A(D)$ and $\mu_{A^c}(J^-(D))\ge \nu_{A^c}(D)$ for $D\subseteq \mathcal{Y}$ measureable.
If $\mu_A(J^-(D))< \nu_A(D)$ one has
$$\mu_A(J^-(D)^c)= 1-\mu_A(J^-(D)) >1- \nu_A(D)\ge \nu_A(J^+(J^-(D)^c))$$
since $J^+(J^-(D)^c)$ and $D$ are disjoint. This contradicts the first part. The inequality $\mu_{A^c}(J^-(D))\ge \nu_{A^c}(D)$ follows analogously.
\end{proof}

\begin{lemma}\label{L3}
Consider the product $\{1,\ldots,N\}\times \{1,\ldots,N\}$ with the canonical projections $\pi_{1,2}$ onto the first and second factor, respectively.
Let $J\subseteq \{1,\ldots,N\}\times \{1,\ldots,N\}$ have the property that
\begin{equation}
\sharp \pi_1(\pi_2^{-1}(A)\cap J)\ge \sharp A \text{ and } \sharp \pi_2(\pi_1^{-1}(A)\cap J)\ge \sharp A
\end{equation}
for all $A\subseteq \{1,\ldots,N\}$.
Then $J$ contains the graph of a permutation $\sigma \in S(N)$.
\end{lemma}

\begin{proof}
The proof is carried out by induction over $N$. If $N=1$ the claim is trivial since $J= \{1\}\times\{1\}$. Now assume that the claim has been shown for
numbers less than $N$. First assume that $\sharp \pi_1(\pi_2^{-1}(A)\cap J)> \sharp A$ and $\sharp \pi_2(\pi_1^{-1}(A)\cap J)> \sharp A$ for all nonempty
proper subsets $A$. Choose
$1\le j\le N$ with $(N,j)\in J$. By renumbering one can 	assume $j=N$. Now consider $I:= J\cap  \{1,\ldots,N-1\}\times \{1,\ldots,N-1\}$. Define $\rho_{1}$ and
$\rho_{2}$ to be the canonical projections from $I$ onto the first and second factor, respectively. Since
$$ {\rho}_1({\rho}_2^{-1}(A)\cap J')\ge  \pi_1(\pi_2^{-1}(A)\cap J)-1\ge \sharp A$$
and vice versa for all $A\subseteq \{1,\ldots,N-1\}$ one obtains a permutation $o\in S(N-1)$ whose graph is contained
in $I$. $o$ extends to a permutation $\sigma \in S(N)$ whose graph is a subset of $J$ by setting $\sigma(N):= N$ and $\sigma|_{\{1,\ldots, N-1\}}\equiv o$.

If there exist a nonempty proper subset $A$ of $\{1,\ldots ,N\}$ with $\sharp \pi_1(\pi_2^{-1}(A)\cap J)= \sharp A$ or $\sharp \pi_2(\pi_1^{-1}(A)\cap J)= \sharp A$
the idea of the previous lemma (see below) reduces the problem to constructing two separate permutations on $A$ and $A^c$. Thus again the induction gives
separate permutations on $A$ and $A^c$ which together form a permutation $\sigma$ whose graph is contained in $J$.

One only needs to consider the case $\sharp \pi_1(\pi_2^{-1}(A)\cap J)= \sharp A$. The other case follows by exchanging the order. Further by renumbering
one can assume that $A= \pi_1(\pi_2^{-1}(A)\cap J)$. Set $J_A:= J\cap  A\times A$,  $J_{A^c}:= J\cap  A^c\times A^c$ and denote with $\pi_{i,A}$ and $\pi_{i,A^c}$
the canonical projections onto $A$ and $A^c$ for $i=1,2$. The goal is to show that $J_A$ and $J_{A^c}$ satisfy the assumptions of the lemma.

It is clear that
$$\sharp \pi_{1,A}(\pi_{2,A}^{-1}(B)\cap J_A)= \sharp \pi_{1}(\pi_{2}^{-1}(B)\cap J)\ge  \sharp B$$
for all $B\subseteq A$ since $\pi_1(\pi_2^{-1}(B)\cap J)\subseteq A$.
If however there exists $C\subseteq A^c$ with $\sharp \pi_{1,A^c}(\pi_{2,A^c}^{-1}(C)\cap J_{A^c})< \sharp C$ then
$\sharp \pi_1(\pi_2^{-1}(A\cup C)\cap J)< \sharp (A\cup C)$ which contradicts the initial assumption.

Assume now that there exists a set $D\subseteq A$ with $\sharp \pi_{2,A}(\pi_{1,A}^{-1}(D)\cap J_A)< \sharp D$.
Set $E:= A\setminus \pi_{2,A}(\pi_{1,A}^{-1}(D)\cap J_A)$. Then $D$ and $\pi_{1,A}(\pi_{2,A}^{-1}(E)\cap J_A)$ are disjoint. This can be seen as follows.
If $i\in \pi_{1,A}(\pi_{2,A}^{-1}(E)\cap J_A)$ then there exists $j\in E$ such that $(i,j)\in J_A$. If $i\in D$ then for all $(i,j)\in J_A$ one has $j\in \pi_{2,A}(\pi_{1,A}^{-1}(D)\cap J_A)$.
Thus the sets are disjoint. It follows that
$$\sharp E=\sharp A-\sharp \pi_{2,A}(\pi_{1,A}^{-1}(D)\cap J_A)>\sharp A-\sharp D\ge \sharp \pi_{1,A}(\pi_{2,A}^{-1}(E)\cap J_A)$$
which clearly contradicts the first part  of the argument. Now the same argument applies to subsets of $A^c$.
\end{proof}

Without loss of generality one can assume that the support of both $\mu$ and $\nu$ are finite. By covering $\supp \mu$ and $\supp \nu$ with
sequences of locally finite, disjoint and measurable coverings one can
approximate both measures in the weak-$*$ topology by finite measures whose support is contained in a given neighborhood of the
supports of $\mu$ and $\nu$. By considering $\overline{B_\varepsilon(J)}$ for $\varepsilon >0$ instead of $J$ gives at every step of the
approximation a pair of finite measures satisfying the assumptions in (2). Below it will be shown how to construct a finite coupling in this case.
By construction the approximations of $\mu$ and $\nu$ form precompact sets in the weak-$*$ topology. This implies that the set of couplings
is precompact in the weak-$*$ topology as well, see \cite{villani}, ch. 4. The claim follows when passing to the limit using that
$J\cap \supp \mu \times \supp \nu$ is closed.

So far the problem has been reduced to the case of measures $\mu$ and $\nu$ having finite support, i.e. are a finite sum of weighted Dirac measures.
Using an inductive argument one can assume by the Lemma \ref{L2} that $\nu(J^+(A))> \mu(A)$ and $\mu(J^-(B))> \nu(B)$ for all nonempty proper subsets $A$ of $\supp \mu$ and
$B$ of $\supp \nu$ respectively. Thus one can assume by a slight perturbation that
the weights for the points in the support of the measures are rational and still one has $\nu(J^+(A))> \mu(A)$ and $\mu(J^-(A))> \nu(A)$ for all $A$. Thus there exist
$N, \alpha_i,\beta_i\in \mathbb N$ such that $\mu=\frac{1}{N}\sum_{i=1}^m \alpha_i \delta_{x_i}$ and $\nu=\frac{1}{N}\sum_{j=1}^n \beta_j\delta_{y_j}$. Counting
the points $x_i$ and $y_j$ multiple times the measures take the form $\mu=\frac{1}{N}\sum_{i=1}^N \delta_{x_i}$ and $\nu=\frac{1}{N}\sum_{j=1}^N \delta_{y_j}$.

Identify $\{x_1,\ldots,x_N\}$ and $\{y_1,\ldots,y_N\}$ with $\{1,\ldots,N\}$. Define the set
$$J:=\{(i,j)|(x_i,y_j)\in J\}\subseteq \{1,\ldots,N\}\times \{1,\ldots,N\}.$$
Denote with $\pi_{1}$ and $\pi_{2}$ the canonical projections from $\{1,\ldots,N\}\times \{1,\ldots,N\}$ onto the first and second factor,
respectively. Then the assumptions become
\begin{equation*}
\sharp \pi_1(\pi_2^{-1}(A)\cap J)\ge \sharp A \text{ and } \sharp \pi_2(\pi_1^{-1}(A)\cap J)\ge \sharp A
\end{equation*}
for all $A\subseteq \{1,\ldots,N\}$.
Lemma \ref{L3} now gives a permutation $\sigma$ whose graph is contained in $J$. Reversing the identifications one obtains (by abuse of notation) a bijective map
$\sigma\colon \{x_1,\ldots ,x_N\}\to \{y_1,\ldots ,y_N\}$ with $(x_i,\sigma(x_i))\in J$ for all $i$. Since $\mu$ and $\nu$ are counting measures the
measure concentrated on the graph of $\sigma$ is the desired coupling.

\subsection{Dynamical Optimal Coupling}

\begin{prop}
There exists a Borel map $S\colon J^+ \to C^0([0,1],M)$ such that $S(x,y)\in \Gamma_{x\to y}$.
\end{prop}

\begin{proof}
The argument is a slight modification of the proof to Proposition 7.16 (vi) in \cite{villani}. For every $(x,y)\in J^+$ the set
$\Gamma_{x\rightarrow y}$ is nonempty and compact in every $C^k$-topology, i.e. nonempty and closed. The evaluation map $\ev_0\times \ev_1$
is Lipschitz. This implies that the correspondence (for the definition see \cite{alibor}, page 4)
$$(\ev\nolimits_0\times \ev\nolimits_1)^{-1}\colon J^+\twoheadrightarrow  \Gamma$$
is weakly measurable in the sense of Definition 18.1. in \cite{alibor}. Now Theorem 8.13 in \cite{alibor} implies that $(\ev_0\times \ev_1)^{-1}$ has a measurable
selection $S$, i.e. $(\ev_0\times \ev_1)\circ S\equiv \id|_{J^+}$.
\end{proof}

\begin{proof}[Proof of Proposition \ref{dynoptcou}]
The argument is taken from the proof of Theorem 7.21 in \cite{villani}. Let $\pi$ be an optimal coupling with marginals $\mu_0$
and $\mu_1$ for the cost $c_L$. Consider $\Pi:=S_\sharp \pi$. Since $(\ev_0,\ev_1)\circ S\equiv \id$, the claim follows from the definition of optimal
dynamical couplings.
\end{proof}

\begin{cor}\label{intermcoup}
Let $\Pi$ be a dynamical optimal coupling between causally related measures $\mu_0$ and $\mu_1$ and $\sigma_{1,2}\colon \Gamma\to [0,1]$ measurable
functions with $\sigma_1\le \sigma_2$. Then the restriction
$$\pi_{\sigma_1,\sigma_2}:=(\EV\circ (\id\times \sigma_1),\EV\circ (\id\times \sigma_2))_\sharp\Pi$$
is an optimal coupling of $\mu_{\sigma_1}:= (\EV\circ (\id\times \sigma_1))_\sharp\Pi$ and $\mu_{\sigma_2}:= (\EV\circ
(\id\times \sigma_2))_\sharp\Pi$. If furthermore $(\sigma_1,\sigma_2)\neq(0,1)$ $\Pi$-almost everywhere then $\pi_{\sigma_1,\sigma_2}$ is
the unique optimal coupling of $\mu_{\sigma_1}$ and $\mu_{\sigma_2}$.
\end{cor}

\begin{proof}
By the triangle inequality for $c_L$ and the parameterization invariance of $\mathcal{A}$ one has
$$C_L(\mu_0,\mu_1)\le C_L(\mu_0,\mu_{\sigma_1})+C_L(\mu_{\sigma_1},\mu_{\sigma_2})+C_L(\mu_{\sigma_2},\mu_1)$$
and
$$\int c_L d\pi_{0,1}=\int c_L d\pi_{0,\sigma_1}+\int c_L d\pi_{\sigma_1,\sigma_2}+\int c_L d\pi_{\sigma_2,1}.$$
Since $\int c_L d\pi_{0,1}=C_L(\mu_0,\mu_1)$ and $C_L$ is the minimal action, the three terms on the right hand sides must individually coincide.
The second statement follows directly from the triangle inequality for $c_L$.
\end{proof}

Theorem 7.30 in \cite{villani} reformulates to the present case as the following statement.

\begin{cor}\label{cor_interpolation}
Let $\mu_{0}$ and $\mu_1$ be finitely separated and causally related probability measures. Further let $\Pi$ be a dynamical optimal coupling.
If $\Xi$ is a measure on $\Gamma^{0,1}$, such that $\Xi\le \Pi$ and $\Xi(\Gamma)>0$, set
$$\Xi':=\frac{\Xi}{\Xi(\Gamma)} \text{ and } \nu_{0,1}:=(\ev\nolimits_{0,1})_\sharp\Xi'.$$
Then $\Xi'$ is a dynamical optimal coupling between $\nu_{0}$ and $\nu_{1}$.
\end{cor}

\subsection{Intermediate regularity of dynamical optimal couplings}\label{intermregu}

For the splitting $M\cong \mathbb R\times N$ choose a smooth vector field $X_\tau$ with $d\tau(X_\tau)\equiv 1$. Define a Lagrange function
$$L_\tau \colon \mathbb R\times TN\to \mathbb R\cup \{\infty\},\; L_\tau(t,v):=L(X_\tau+v).$$
Denote with $\mathcal{D}_\tau\subseteq \mathbb R\times TN$ the domain of $L_\tau$. $L_\tau$ is continuous on $\mathcal{D}_\tau$ and smooth
on $\inte \mathcal{D}_\tau$.

\begin{lemma}\label{strictconvexity}
\begin{itemize}
\item[(i)] $\mathcal{D}_{(t,x)}:=\mathcal{D}_\tau\cap \{t\}\times TN_x$ is a compact strictly convex domain with smooth boundary for all $(t,x)\in\mathbb R\times N$.
\item[(ii)] For all $K\subseteq \mathbb R\times N$ compact there exists $\delta>0$ such that
$$(\partial_v^2 L_\tau)_{(t,v)}\ge \frac{\delta}{|L_\tau(t,v)|}\cdot \id$$
for all $(t,x)\in K$ and $v\in \inte\mathcal{D}_{(t,x)}$.
\end{itemize}
\end{lemma}

\begin{proof}
(i) $\mathcal{D}_{(t,x)}$ is compact since $d\tau_{(t,x)} \in \inte \mathcal{C}_{(t,x)}^*$. It is further smooth since $\partial \mathcal{C}_{(t,x)}$ is smooth and
$\ker d\tau\cap \mathcal{C}=\{0\}$. Finally the strict convexity follows from the fact that $\partial_v^2 \mathbb{L}$ is semidefinite at a nonzero boundary point with kernel
equal to the radial direction, i.e. definite on any hyperplane transversal to the radial direction.

(ii) Recall the formula for the second fibre derivative of $L$
$$\partial^2_v L=\frac{1}{2\sqrt{\mathbb{L}}}\left(\frac{1}{2}\frac{\partial_v\mathbb{L}\otimes\partial_v\mathbb{L}}{\mathbb{L}}-\partial^2_v\mathbb{L}\right).$$
As before one has
$$\partial^2_v \mathbb{L}|_{T\partial\mathcal{D}\times T\partial\mathcal{D}}>0.$$
Thus one can choose $N<\infty$ and $\delta_1 >0$ such that
$$\left.\left(\frac{N}{2}\partial_v\mathbb{L}\otimes\partial_v\mathbb{L}-\partial^2_v \mathbb{L}\right)\right|_{T\mathcal{D}\times T\mathcal{D}}>\delta_1\cdot \id$$
on a neighborhood $U$ of $\partial\mathcal{D}$ over $K$. This implies the claim on the i.g. smaller neighborhood $U\cap\{\mathbb{L}<1/N\}$.

For the remaining points outside of $U\cap\{\mathbb{L}<1/N\}$ note that
$$\frac{1}{2}\frac{\partial_v\mathbb{L}\otimes\partial_v\mathbb{L}}{\mathbb{L}}-\partial^2_v\mathbb{L}\ge 0$$
with kernel equal to the radial direction. Thus one can find $\delta_2>0$ such that on $\mathcal{D}\setminus U\cap\{\mathbb{L}<1/N\}$ over $K$ one has
$$\frac{1}{2}\frac{\partial_v\mathbb{L}\otimes\partial_v\mathbb{L}}{\mathbb{L}}-\partial^2_v\mathbb{L}> \delta_2\cdot \id.$$
\end{proof}

\begin{lemma}\label{phitau}
A curve $\eta\colon I\to N$ is a trajectory of the Euler-Lagrange flow $\Phi_\tau$ of $L_\tau$ if, and only if its graph $\eta_\Gamma\colon t\mapsto (t,\eta(t))$
solves the Euler-Lagrange equations of $L$.
\end{lemma}

\begin{proof}
Let $\eta\colon I\to N$ be a $\Phi_\tau$-trajectory. Consider a smooth variation $\mathrm{H}_\Gamma\colon I\times (-\e,\e)\to \mathbb R\times N$ of $\eta_\Gamma$
with fixed endpoints. Since $\mathrm{H}_\Gamma$ is smooth one can assume, by diminishing $\e$ if necessary, that $\partial_t(\tau
\circ\mathrm{H}_\Gamma)>0$ everywhere. Thus one can smoothly reparameterize $\mathrm{H}_\Gamma$ to satisfy $\partial_t(\tau
\circ\mathrm{H}_\Gamma)=1$, i.e. $\mathrm{H}_\Gamma$ consists of graphs of curves in $N$ over the same interval $I$. This does not affect the value of
$\mathcal{A}$ on the variation. Since any variation by graphs is a variation of the underlying curve, it follows that the first variation of $\eta_\Gamma$ vanishes,
i.e. $\eta_\Gamma$ solves the Euler-Lagrange equations of $L$. The converse is obvious since any variation of $\eta$ lifts to a variation of $\eta_\Gamma$.
\end{proof}

\begin{prop}
$\Phi_\tau$ extends unique smoothly to the boundary $\partial \mathcal{D}_\tau$ and the extension is complete. Further $\inte\mathcal{D}_\tau$ and
$\partial\mathcal{D}_\tau$ are $\Phi_\tau$-invariant.
\end{prop}

\begin{proof}
By the previous lemma the graphs of $\Phi_\tau$-trajectories solve the Euler-Lagrange equation of $L$. Reparameterizing to preserve $\mathbb{L}$ yields
solutions to the Euler-Lagrange equations of $\mathbb{L}$. The local Euler-Lagrange flow of $\mathbb{L}$ extends beyond the boundary
$\mathcal{C}\setminus \overline{0}$. Parameterizing those trajectories to satisfy $d\tau \equiv 1$ yields the unique smooth extension.

The completeness follows since $(M,L)$ is globally hyperbolic and $-d\tau \le L$. The invariance follows from the fact that
$\mathbb{L}$ is preserved along its local Euler-Lagrange flow and $\Phi_\tau$ is induced by a reparameterization of its trajectories.
\end{proof}

Denote with $\mathcal{A}_\tau$ the action of $L_\tau$, i.e. for $\eta\colon [s,t]\to N$ set
$$\mathcal{A}_\tau(\eta):=\int_s^t L_\tau(\sigma,\dot\eta(\sigma))d\sigma\in \mathbb R\cup\{\infty\}.$$
Call a pair $(t,y)\in \mathbb R\times N$ {\it reachable from} $(s,x)$ if there exists an absolutely continuous curve $\eta\colon[s,t]\to N$ from $x$ to $y$ with
$\dot\eta\in \mathcal{D}_\tau$ whenever the tangent exists. Note that $(t,y)$ is reachable from $(s,x)$ if, and only if $(t,y)\in J^+(s,x)$ for the cone structure
$\mathcal{C}$. With this analogy one defines $J^\pm (s,x)$ and $I^\pm (s,x)$ according to the definitions for cone structures.

\begin{lemma}\label{normaltau}
For every $(s,x)\in \mathbb R\times N$ exists a neighborhood $U\subseteq \mathbb R\times N$ such that for every $(t,y)\in U\cap J^+(s,x)$ the unique $\Phi_\tau$-trajectory
$\gamma\colon [s,t]\to N$ from $x$ to $y$ strictly minimizes $\mathcal{A}_\tau$ among all curves $\eta\colon [s,t]\to N$ from $x$ to $y$.
\end{lemma}

\begin{proof}
This follows from Lemma \ref{phitau} and the observation that solutions to the Euler-Lagrange equations of $L$ reparameterize to solutions of the Euler-Lagrange equations
of $\mathbb{L}$, which minimize $\mathcal{A}$ among all causal curves, see \cite{minguzzi142}.
\end{proof}

\begin{remark}\label{localL}
Under the identification $M\cong \mathbb R\times N$ follows: For $(s,x)$, $(t,y)\in U\cap J^+(s,x)$ as in Lemma \ref{normaltau} and $\gamma\colon [s,t]\to N$ the unique
$\Phi_\tau$-trajectory from $x$ to $y$ one has
$$A_\tau(\gamma)=L(v),$$
where $v=\left(\exp_{(s,x)}^\mathbb{L}\right)^{-1}(t,y)$ where $\exp_{(s,x)}^\mathbb{L}$ denotes the exponential map with respect to $\mathbb{L}$. Further denote with
$\mathcal{S}_s^t(x,y)$ the minimal action of a curve $\eta\colon [s,t]\to N$ from $x$ to $y$. Then the previous equalities and Lemma \ref{normaltau} imply
$$\mathcal{S}_s^t(x,y)=L\left(v\right)$$
with $v$ as before.
\end{remark}

\begin{prop}\label{mathershortening}
Let $\varepsilon >0$ and $I\times K\subseteq \mathbb R\times N$ a compact subset. Then there exist $\delta,\kappa >0$ and $C<\infty$ such that for $a\le b\le c\in I$ with $b-a,c-b\ge \e$ and
$\Phi_\tau$-trajectories $x_i\colon (a,c)\to N$, $i=1,2$, with $\dist(x_1(b),x_2(b))\le \delta$, $x_i(b)\in K$ and
$$\dist(\dot{x}_1(b),\dot{x}_2(b))^{2}\ge C\dist(x_1(b),x_2(b))$$
there exist minimizers $y_i\colon (a,c)\to N$ with $y_1(a)=x_1(a)$, $y_1(c)=x_2(c)$, $y_2(a)=x_2(a)$, $y_2(c)=x_1(c)$ and
$$\mathcal{A}_\tau(y_1)+\mathcal{A}_\tau(y_2)-\mathcal{A}_\tau(x_1)-\mathcal{A}_\tau(x_2)\le -\kappa \dist(\dot{x}_1(b),\dot{x}_2(b))^2.$$
\end{prop}

\begin{lemma}\label{actionestimate}
Let $I\times K\subseteq \mathbb R\times N$ be compact and $\e>0$. Then there exists $\delta >0$ such that for all $a\le b\le c\in I$ with $b-a,c-b \ge \e$ and causal
minimizers $\eta\colon [a,b]\rightarrow N$, $\gamma \colon [b,c]\rightarrow N$ with $\eta (b)=\gamma (b)$ and $\dot \eta (b)\neq \dot\gamma (b)$ one has
$$\mathcal{S}_{a}^{c}(\eta(a),\gamma(c))-\mathcal{A}_\tau(\eta)-\mathcal{A}_\tau(\gamma)
\le -\frac{\delta}{|\mathcal{S}_{a}^{c}(\eta(a),\gamma(c))|} |\dot\eta (b)-\dot\gamma(b)|^2.$$
\end{lemma}

\begin{proof}
Choose $\delta>0$ such that
$$(\partial^2_v L_\tau)_{(s,v)}\ge \frac{\delta}{|L_\tau(s,v)|}\id$$
for all $(s,v)\in \inte \mathcal{D}\cap \pi^{-1}(I\times K)$ according to Lemma \ref{strictconvexity} (ii). For $v\neq w \in \inte \mathcal{D}_{(s,x)}$ with $(s,x)\in I\times K$ consider
the convex hull $\conv\{v,w\}$. Note that the relative interior of $\conv\{v,w\}$ is contained in $\inte \mathcal{D}_{(s,x)}$. Parameterize $\conv\{v,w\}$ by
$$c\colon \lambda \in [0, |v-w|]\mapsto \left(1-\frac{\lambda}{|v-w|}\right) v+ \frac{\lambda}{|v-w|}w.$$
Next denote with $L_\text{min}$ the minimum of $L\circ c$ and $0\le \lambda_0\le |v-w|$ the parameter achiving this minimum. Let $Y$ be any point in the relative interior of $\conv\{v,w\}$.
Denote with $L_Y' :=\left.\frac{d}{d\lambda}\right|_{\lambda=\lambda_1}(L\circ c)(\lambda)$ where $c(\lambda_1)=Y$. Then one has
\begin{align*}
(L_Y')^2&= |L_Y'||0-L_Y'|= |L_Y'|\cdot \left| \int_{\lambda_1}^{\lambda_0} (L\circ c)''(\lambda)d\lambda\right|\ge |L_Y'|\cdot\delta\left|\int_{\lambda_1}^{\lambda_0}\frac{1}{|L\circ c(\lambda)|}d\lambda\right|\\
&\ge \delta \int_{\lambda_1}^{\lambda_0} \frac{(L\circ c)'(\lambda)}{|L\circ c (\lambda)|} d\lambda =\delta \log \left| \frac{L_\text{min}}{L_Y} \right|
\end{align*}
where the last two manupilations follow from the convexity of $L\circ c$.

Cover $I\times K$ with finitely many neighborhoods $U\subset \mathbb R\times N$ according to Lemma \ref{normaltau}. Choose $\e>\e'>0$ such that for every
$(s,x)\in I\times K$ the open set $V:=(s-\e',s+\e')\times B_{\e'}(x)$ is contained in at least one $U$. It suffices to prove the claim for $a'\le b \le c'$ with $b-a'=c'-b=\e'$
since concatenating a minimizer from $\eta(a')$ to $\gamma(c')$ with $\eta|_{[a,a']}$ and $\gamma|_{[c',c]}$ only decreases the left hand side as well as
increases the right hand side. The proof continues to use $a$ and $c$ instead of $a'$ and $c'$ though.

For $(t,y)\in I^+(a,\eta(a))\cap V$ denote with $Y_{t,y}$ the tangent at $t$ to the unique $\Phi_\tau$-orbit from $\eta(a)$ to $y$. Then one has
$$\mathcal{S}_{a}^t(\eta(a),\gamma(t))\le \mathcal{A}_\tau(\gamma|_{[b,t]})+\mathcal{S}_{a}^b(\eta(a),\eta(b))$$
for every $b\le t\le c$. This implies
$$\partial_t|_{t=s} \left[\mathcal{S}_{a}^t(\eta(a),\gamma(t))\right]\le L_\tau(s,\dot\gamma(s))$$
with equality if, and only if $\dot\gamma(s)= Y_{s,\gamma(s)}$. Since the former is an affine function on $TN_{\gamma(s)}$ it must coincide
with the tangent to $L_\tau$ at $Y_{s,\gamma(s)}$, i.e.
$$\partial_s\left|_{t=s} \left[\mathcal{S}_{a}^t(\eta(a),\gamma(t))\right]\right.=L_\tau(s,Y_{s,\gamma(s)})
+(\partial_v L_\tau)_{Y_{s,\gamma(s)}}(\dot\gamma(s)-Y_{s,\gamma(s)}).$$
Denote with $L_\text{min}(s)$ the minimum of $L_\tau$ on the convex hull of $\dot\gamma(s)$ and $Y_{s,\gamma(s)}$. Then one has
\begin{align*}
L_\tau(s,\dot\gamma(s))&\ge L_\tau(s,Y_{s,\gamma(s)})+\partial_v L_\tau(\dot\gamma(s)-Y_{s,\gamma(s)}) +\frac{\delta}{2|L_\text{min}(s)|}|\dot\gamma(s)-Y_{s,\gamma(s)}|^2\\
&= \partial_s \left[\mathcal{S}_{a}^s(\eta(a),\gamma(s))\right]+\frac{\delta}{2|L_\text{min}(s)|}|\dot\gamma(s)-Y_{s,\gamma(s)}|^2.
\end{align*}

Assume that $|L_\text{min}(s)|\ge C|L_{Y_{s,\gamma(s)}}|$ for $C<\infty$ sufficiently large on a set $B\subseteq [b,c]$ of measure at least $\e/2$. Then from the first paragraph one has
$|L_{Y_{s,\gamma(s)}}'|\ge \sqrt{\delta \log C}$ on $B$. Note that this implies $L_{Y_{s,\gamma(s)}}'\le 0$
for $C$ sufficiently large since
$$0\ge \partial_s \mathcal{S}_{a}^s(\eta(a),\gamma(s))= L_\tau(s,Y_{s,\gamma(s)})+L_{Y_{s,\gamma(s)}}'$$
implies $L_{Y_{s,\gamma(s)}}'\le -L_\tau(s,Y_{s,\gamma(s)})$ which is uniformly bounded from above on $K$. Consequently
$$\partial_s \mathcal{S}_{a}^s(\eta(a),\gamma(s))= L_\tau(s,Y_{s,\gamma(s)})+L_{Y_{s,\gamma(s)}}'\le L_{Y_{s,\gamma(s)}}' <-\sqrt{\delta \log C}$$
which implies
$$\mathcal{S}_{a}^{c}(\eta(a),\gamma(c))- \mathcal{S}_{a}^b(\eta(a),\gamma(b))
\le \int_B \partial_s \mathcal{S}_{a}^s(\eta(a),\gamma(s)) ds \le -\frac{\e}{2} \sqrt{\delta \log C}.$$
This constitutes a contradiction for $C$ sufficiently large. Therefore there exists a constant $C_1<\infty$ and a subset $B$ of $[0,\e]$ of measure at least $\e/2$ such that
$|L_\text{min}(s)|\le C_1|L_{Y_{s,\gamma(s)}}|$ for all $s\in B$. Consequently one has
\begin{align*}
\mathcal{S}_{a}^{c}(\eta(a),\gamma(c))- &\mathcal{S}_{a}^b(\eta(a),\gamma(b))\le \mathcal{A}_\tau (\gamma)-
\frac{\delta}{2}\int_b^{c} \frac{|\dot\gamma(s)-Y_{s,\gamma(s)}|^2}{|L_\text{min}(s)|}ds\\
&\le \mathcal{A}_\tau (\gamma)-\frac{\delta}{2C_1}\int_B \frac{|\dot\gamma(s)-Y_{s,\gamma(s)}|^2}{|L_{Y_{s,\gamma(s)}}|} ds.
\end{align*}
Next note that the continuity of $\Phi_\tau$ and the invariance of $\partial \mathcal{D} =L_\tau^{-1}(0)$ under $\Phi_\tau$ implies the existence of a
$C_2<\infty$ depending only on $I\times K$ such that $(s-a)|L_{Y_{s,\gamma(s)}}|\le C_2 |S_{a}^s(\eta(a),\gamma(s))|$ for all $b\le t\le c$. Thus one has
\begin{align*}
\mathcal{S}_{a}^{c}(\eta(a),\gamma(c))- &\mathcal{S}_{a}^b(\eta(a),\gamma(b))
\le \mathcal{A}_\tau (\gamma)-\delta_1\int_B \frac{|\dot\gamma(s)-Y_{s,\gamma(s)}|^2}{|S_{a}^s(\eta(a),\gamma(s))|}ds\\
&\le \mathcal{A}_\tau (\gamma)-\frac{\delta_1}{{|S_{a}^{c}(\eta(a),\gamma(c))|}}\int_B |\dot\gamma(s)-Y_{s,\gamma(s)}|^2 ds.
\end{align*}
Note that again due to the continuity of $\Phi_\tau$ there exists $C_3<\infty$ depending only on $I\times K$ such that for  all $b\le t\le c$
one has $|\dot\gamma(t)-Y_{t,\gamma(t)}|\le C_3 |\dot\gamma(b)-Y_{b,\gamma(b)}|$. Thus there exists $\delta_3>0$ such that
$$S_{a}^{c}(\eta(a),\gamma(c))- S_{a}^b(\eta(a),\gamma(b))
\le \mathcal{A}_\tau (\gamma)-\frac{\delta_3}{{|S_{a}^{c}(\eta(a),\gamma(c))|}} |\dot\gamma(b)-Y_{b,\gamma(b)}|^2.$$
Finally notice that $Y_{b,\gamma(b)}=\dot\eta(b)$. This finishes the proof.
\end{proof}

\begin{proof}[Proof of Proposition \ref{mathershortening}]
Like in the preceeding proof one can assume that the curves are contained in a normal neighborhood.

(i) The first step is to show that
$$(c,x_2(c))\in J^+(a,x_1(a))$$
for $0<C<\infty$ sufficiently large.
Using the local Lipschitz continuity of $(s,x)\mapsto \mathcal{D}_{(s,x)}$, which follows directly from local Lipschitz continuity of $\mathcal{C}$, there exists
$C_0<\infty$ only depending on $I\times K$ such that one can choose $\dot\chi_2(b)\in \mathcal{D}_{(b,x_1(b))}$ with
\begin{align}\label{Etang}
\dist(\dot\chi_2(b),\dot x_2(b))\le C_0\dist(\chi_2(b),x_2(b))=C_0\dist(x_1(b),x_2(b)).
\end{align}
With the smoothness of $\Phi_\tau$ this then implies
$$\dist(\chi_2(c),x_2(c))\le C_1\dist(x_1(b),x_2(b))$$
for some $C_1<\infty$ only depending on $I\times K$ and $\e$. Now the triangle inequality yields
\begin{align*}
\dist((c,x_2(c)), &\partial J^+(a,x_1(a)))\\
&\ge \dist((c,\chi_2(c)), \partial J^+(a,x_1(a)))-C_1 \dist(x_1(b),x_2(b)).
\end{align*}

Recall from Remark \ref{localL} that
$$\mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))^2=L((\exp^\mathbb{L}_{x_1(a)})^{-1}(\chi_2(c))^2$$
and that $L^2$ is smooth up to and beyond $\partial\mathcal{D}$. Thus there exists $\delta_0>0$, only depending on $I\times K$ and $\e$, such that
$$\dist((c,\chi_2(c)), \partial J^+(a,x_1(a)))\ge \delta_0 \mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))^2.$$
Now Lemma \ref{actionestimate} implies $\mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))^2\ge \delta_2 \dist(\dot{x}_1(b),\dot{\chi}_2(b))^2$
as a special case. With \eqref{Etang} one then obtains
$$\mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))^2\ge \delta_3 \dist(\dot{x}_1(b),\dot{x}_2(b))^2$$
for some $\delta_3>0$ if $C$ is sufficiently large. Consequently one has
$$\dist((c,x_2(c)), \partial J^+(a,x_1(a)))\ge \frac{1}{2}\dist((c,\chi_2(c)), \partial J^+(a,x_1(a)))$$
for $\dist(\dot{x}_1(b),\dot{x}_2(b))^{2}\ge C\dist(x_1(b),x_2(b))$ with $C$ sufficiently large. Thus one concludes $(c,x_2(c))\in J^+(a,x_1(a))$.

(ii) Remark \ref{localL} implies that
$$\mathcal{S}_{a}^{c}(x_1(a),x_2(c))^2\ge \delta_4 \dist((c,x_2(c)),J^+(a,x_1(a)))$$
for some $\delta_4>0$ depending only on $I\times K$ and $\e$, since the fibre derivative of $L_\tau^2$ does not vanish anywhere on $\partial \mathcal{D}$.
Thus one has
$$\mathcal{S}_{a}^{c}(x_1(a),x_2(c))^2\ge \frac{\delta_4\delta_0}{2} \mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))^2.$$
With the convexity of $\mathcal{S}$ one then concludes
\begin{equation}\label{actionerror}
\begin{split}
|\mathcal{S}_{a}^{c}(x_1(a),x_2(c))-\mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))|\le
 \frac{C_2}{|\mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))|}\dist(x_1(b),x_2(b))
\end{split}
\end{equation}
for some $C_2<\infty$ depending only on $I\times K$ and $\e$. Finally one has
\begin{align*}
\mathcal{S}_{a}^{c}(x_1(a),x_2(c))-&\mathcal{S}_{a}^{b}(x_1(a),x_1(b))-\mathcal{S}_{b}^{c}(x_2(b),x_2(c))\\
\le&\; \mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))-\mathcal{S}_{a}^{b}(x_1(a),x_1(b))-\mathcal{S}_{b}^{c}(\chi_2(b),\chi_2(c))\\
&+|\mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))-\mathcal{S}_{a}^{c}(x_1(a),x_2(c))|\\
&+|\mathcal{A}_\tau(x_2|_{[b,c]})-\mathcal{A}_\tau(\chi_2)|.
\end{align*}
The first term on the right hand side is bounded from above by
$$-\frac{\delta}{|\mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))|}\dist(\dot{x}_1(b),\dot{x}_2(b))^2$$
according to Lemma \ref{actionestimate} and the choice of $\chi_2$ for some $\delta>0$. The second term is bounded from above by
$$\frac{C_2}{|\mathcal{S}_{a}^{c}(x_1(a),\chi_2(c))|}\dist(x_1(b),x_2(b))$$
according \eqref{actionerror}. Finally the third term is bounded from above by $C_3\dist(x_1(b),x_2(b))$ according to \eqref{Etang} for some $C_3<\infty$.
Now note that
$$\dist(\dot{x}_1(b),\dot{\chi}_2(b))\ge \dist(\dot{x}_1(b),\dot{x}_2(b))-C_0\dist(x_1(b),x_2(b))$$
by the triangle inequality and \eqref{Etang}. This implies that
\begin{align*}
\mathcal{S}_{a}^{c}(x_1(a),x_2(c))-\mathcal{S}_{a}^{b}(x_1(a),x_1(b))-\mathcal{S}_{b}^{c}(x_2(b),x_2(c))
\le -\frac{\delta}{2}\dist(\dot{x}_1(b),\dot{x}_2(b))
\end{align*}
for $C<\infty$ sufficiently large.

Repeating the arguments for $\mathcal{S}_{a}^{c}(x_2(a),.)$, $x_2|_{[a,b]}$ and $x_1|_{[b,c]}$ one obtains
\begin{align*}
\mathcal{S}_{a}^{c}(x_1(a),x_1{c})+\mathcal{S}_{a}^{c}(x_2(a),x_2(c))-\mathcal{S}_{a}^c(x_1(a),x_2(c))&-\mathcal{S}_{a}^c(x_2(a),x_1(c))\\
&\le -\delta \dist(\dot{x}_1(b),\dot{x}_2(b))^2
\end{align*}
for $C<\infty$ sufficiently large. The claim is now immediate for $y_1\colon [a,c]\to N$ the
minimizer from $x_1(a)$ to $x_2(c)$ and $y_2\colon [a,c]\to N$ the minimizer from $x_2(a)$ to $x_1(c)$.
\end{proof}

\begin{proof}[Proof of Theorem \ref{intermediateregularity}]
Let $\Pi$ be a dynamical optimal coupling. For $k\in\mathbb N$ consider the subcoupling
$$\Pi_k:= \Pi|_{\{\gamma|\; \dist(\gamma(0),\gamma(1))\ge 1/k\}}.$$
Since the supports of $\mu$ and $\nu$ are disjoint one knows that for every compact set $I\times K\subseteq \mathbb R\times N\cong M$ there exists
$k$ with
$$(\ev\nolimits_t)_\sharp \Pi|_{I\times K}\equiv (\ev\nolimits_t)_\sharp \Pi_k|_{I\times K}$$
for all $t\in [0,1]$. Therefore one can assume that there exists $\e_0>0$ such
that for every $\gamma\in \supp \Pi\subseteq \Gamma^{0,1}$ one has $\e_0\le |\dot{\gamma}|$. Consider the reparameterization
$\eta\colon [\alpha,\omega]\to M$ of $\gamma\in \supp \Pi$ such that $\tau\circ \eta(s)=s$. Then there exists
$\e_1>0$ only depending on $\e_0$ such that $\omega- \alpha>\e_1$ for all $\gamma\in \supp\Pi$.

Next let $\e_2>0$ be given and consider the dynamical optimal coupling restricted to $[\e_2,1-\e_2]$.
Then there exists $\e_3>0$ only depending on $\e_0$ and $\e_2$ such that $|t-\alpha|,|t-\omega|\ge 2\e_3$ for all $\gamma\in \supp\Pi$,
$\eta$ as above and $\eta(t)=\gamma(s)$ for $s\in [\e_2,1-\e_2]$.

Let $(\gamma_1,t_1),(\gamma_2,t_2)\in \supp\Pi\times[\e_2,1-\e_2]$.
Since $\tau$ is Lipschitz on $I\times K$ with constant $L<\infty$ one has
$$|b_2-b_1|=|\tau(\gamma_1(t_1))-\tau(\gamma_2(t_2))|\le L\dist(\gamma_1(t_1),\gamma_2(t_2)).$$
For $\dist(\gamma_1(t_1),\gamma_2(t_2))$ smaller than $\e_3/L$ one has thus $|b_1-\alpha_2|,|b_1-\omega_2|\ge \e_3$.
Therefore $\eta_2$ is well defined on $[b_1-\e_3,b_1+\e_3]$.
With the smoothness of $\Phi_\tau$ one concludes that there exists a constant $C_0<\infty$ depending only on $\e_0$ and $\e_2$ such that
$$\dist(\dot\eta_2(b_1),\dot\eta_2(b_2))\le C_0 \dist(\gamma_1(t_1),\gamma_2(t_2)).$$
Further the triangle inequality implies that
$$\dist(\dot\eta_2(b_1),\dot\eta_1(b_1))\ge \dist(\dot\eta_1(b_1),\dot\eta_2(b_2))-C_0\dist(\gamma_1(t_1),\gamma(t_2))$$
and
$$\dist(\eta_2(b_1),\eta_1(b_1))\le C_1\dist(\gamma_1(t_1),\gamma_2(t_2))$$
for some $C_1<\infty$ depending only on $I\times K$.

Now choose $\delta,\kappa>0$ and $C<\infty$ for $\e:=\e_3$ and $I\times K$ according to Proposition \ref{mathershortening}.
For $C_4<\infty$ sufficiently large assuming that
$$C_4\dist(\gamma_1(t_1),\gamma_2(t_2))< \dist([\dot{\gamma}_1(t_1)],[\dot{\gamma}_2(t_2)])^2$$
and $\dist(\gamma_1(t_1),\gamma_2(t_2))\le \min\{\delta/C_1,\e_3/L\}$ one has
$$C \dist(\eta_2(b_1),\eta_1(b_1))< \dist(\dot\eta_2(b_1),\dot\eta_1(b_1))^2.$$
Then Proposition \ref{mathershortening} implies that
\begin{align*}
&c_L(\eta_1(b_1-\e_3),\eta_2(b_1+\e_3))+c_L(\eta_2(b_1-\e_3),\eta_1(b_1+\e_3))\\
&-c_L(\eta_1(b_1-\e_3),\eta_1(b_1+\e_3))-c_L(\eta_2(b_1-\e_3),\eta_2(b_1+\e_3))<0.
\end{align*}
With the triangle inequality for $c_L$ follows
$$c_L(\gamma_1(0),\gamma_2(1))+c_L(\gamma_2(0),\gamma_1(1))-c_L(\gamma_1(0),\gamma_1(1))-c_L(\gamma_2(0),\gamma_2(1))<0$$
clearly contradicting the cyclic monotonicity of the optimal coupling.
Thus there exists $D<\infty$ with
$$ \dist([\dot{\gamma}_1(t_1)],[\dot{\gamma}_2(t_2)])^2\le D\dist(\gamma_1(t_1),\gamma_2(t_2))$$
showing the injectivity of the projection and the H\"older continuity of the inverse.
\end{proof}

\begin{proof}[Proof of Theorem \ref{lipreg}]
Choose a compact set $\overline{K}\subseteq \inte\mathcal{D}_\tau$ such that $K\subseteq \pos \overline{K}$. Next construct a Tonelli-Lagrangian
$L_0\colon\mathbb R\times TN\to \mathbb R$ with $L_0\ge L_\tau$ and $L_0|_{\overline{K}}\equiv L_\tau|_{\overline{K}}$. Then every $L_\tau$-minimizer $\gamma$ with
$\dot\gamma\in \overline{K}$ is also a $L_0$-minimizer. Now the claim follows from the classical regularity result for Tonelli-Lagrangians.
\end{proof}

\subsection{Proof of Theorem \ref{Thmmonge}}\label{secmonge}

The proof is essentially carried out via two propositions.
\begin{prop}\label{mongeprop1}
Let $\mu,\nu\in \mathcal{P}(M)$ be as in the assumptions of Theorem \ref{Thmmonge} and $\supp\mu$ is $\nu$-neglectable. Then for
every minimal coupling $\pi$ of $\mu$ and $\nu$ there exists a set $R$ of full $\pi$-measure such that for all $(x,y_1),(x,y_2)\in R$ there
exists a minimizer $\gamma$ containing $x,y_1,y_2$ in its trace.
\end{prop}

The proof of Proposition \ref{mongeprop1} needs a lemma proven in \cite{chpa} for the case $M= \mathbb R^n$. The proof carries over mutatis mutandis to the
present situation of manifolds. Recall that $x$ is a {\it Lebesgue point} of a set $C$ if
$$\lim_{\delta\to 0} \frac{\mathcal{L}^n(C\cap B_\delta(x))}{\mathcal{L}^n(B_\delta(x))}=1.$$

\begin{lemma}\label{lemleb}
Let $N$ be a manifold, $\mu,\nu\in \mathcal{P}_1(N)$, $\pi\in \Pi(\mu,\nu)$ and $\Sigma$ a $\sigma$-compact set such that $\pi(\Sigma)=1$.
Assume that $\mu$ is absolutely continuous w.r.t. to the Lebesgue measure on $N$. Then $\pi$ is concentrated on a $\sigma$-compact set $R(\Sigma)$
such that for all $(x,y)\in R(\Sigma)$ the point $x$ is a Lebesgue point of $\pi_1(\Sigma\cap (N\times \overline{B(y,r)}))$ for all $r>0$.
\end{lemma}

\begin{proof}[Proof of Proposition \ref{mongeprop1}]
Let $\pi$ be a minimal coupling of $\mu$ and $\nu$. One can assume that minimizers between points in $\supp\mu$
and $\supp \nu$ are unique up to parameterization. This can be seen as follows. By passing to a subtransport plan, according to Corollary
\ref{cor_interpolation}, one can first assume that $\supp\mu$ and hence $\supp \nu$ is compact. Second choose a dynamical optimal coupling
$\Pi$ for $\pi$, i.e. $\pi =(\ev_0,\ev_1)_\sharp \Pi$. Then by Corollary \ref{intermcoup} one can assume that the
minimizers in $\supp \Pi$ are unique up to parmeterization by considering the transport between $0$ and $t>0$
for $t$ sufficiently small. Note that
$$0=\nu(\supp \mu)=\pi(\supp\mu\times \supp\nu \cap \triangle)$$
where $\triangle$ denotes the diagonal in $M\times M$. Thus $\Pi$-almost every minimizer is nonconstant.
Therefore $\supp\mu$ is $(\ev_t)_\sharp \Pi$-neglectable for all $t>0$.

Note that since $\mu$ and $\nu$ are supported on Lipschitz graphs over $N$ one can consider both measures to be supported on $N$ without losing the absolute continuity
of $\mu$ with respect to the Lebesgue measure. Therefore one can apply Lemma \ref{lemleb} to $\mu$ and $\nu$ seen as measures on $N$ and obtain a set $R\subseteq A\times B$
by revoking the identification via the graphs. Hence choose a set $R=R(\Sigma)\subseteq A\times B$ according to Lemma \ref{lemleb}. Assume that there exist $(x,y_1)$ and $(x,y_2)\in R$ such that
$y_i$ is not on the minimizer between $x$ and $y_j$ for $i\neq j$.
Then one knows that the tangent vectors at $x$ to the minimizers $\gamma_i\in \Gamma(\tau)$ between $x$ and $y_i$ are not parallel.

Next choose a diffeomorphism $\psi$ from $B_1(0)\subseteq\mathbb R^n$ to a neighborhood $U$ of $x$ with $\psi(0)=x$. For $\delta >0$ define $\psi_\delta\colon B_1(0)\rightarrow U$,
$v\mapsto \psi(\delta v)$. It is obvious that $L_\delta := \frac{1}{\delta}\psi^*(L)$ converges to $L|_{\mathcal{C}_x}$ uniformly on compact subsets of $\inte \mathcal{C}$ in any $C^k$-topology
for $\delta \rightarrow 0$. Especially the minimizers of $L_\delta$ converge uniformly to straight lines in $B_1(0)$.

Next choose sequences $\delta_n,r_n\downarrow 0$ such that
\begin{align}\label{lemleb2}
\lim_{n\to\infty} \frac{\mathcal{L}_A(\pi_1(\Sigma \cap (A\times \overline{B_{r_n}(y_2)}))\cap \text{im}(\psi_{\delta_n}))}{\mathcal{L}_A(A\cap \text{im}(\psi_{\delta_n}))}=1.
\end{align}
Since the distance from $x$ to $y_2$ can be bounded from below and due to the structure of the $\psi_\delta$'s one concludes that the tangents $\dot\eta$ at $x$ converge to $\dot\gamma_2$ at $x$
for minimizers $\eta\colon [0,1]\to M$
in $\Gamma(\tau)$ connecting a point in $\text{im}\psi_{\delta_n}$ with a point $B_{r_n}(y_2)$. Further by \eqref{lemleb2} one can choose points $(w_n,z_n)
\in \text{im}\psi_{\delta_n}\times B_{r_n}(y_2)$ with $(w_n,z_n)\in \supp\pi$, $\dist(\psi_{\delta_n}^{-1}(x),\psi_{\delta_n}^{-1}(w_n))\ge \frac{1}{2}$ and $\psi_{\delta_n}^{-1}(w_n)\to v\in
\mathbb R\cdot\dot{\gamma}_1+\mathbb R_{<0}\cdot\dot{\gamma}_2$. Thus the $L_x$-minimizer $t\mapsto t\cdot \dot{\gamma}_1$ and $t\mapsto v+ t\cdot \dot{\gamma}_2$ intersect for some positive
value of $t$. A simplified version of Proposition \ref{mathershortening} now shows that this crossing can be shortenened by nonzero amount. Since the converges is uniform a fraction
of this shortening survives when passing to $L_{\delta_n}$ for $n$ sufficiently large. This now contradicts the cyclic monotonicity of the optimal transport plan.
\end{proof}

Consider the set $I_B$ of minimizers $\gamma\in \Gamma(\tau)$ with
$\tau\circ \gamma=\id$ which intersect $B$ in more than one points. Identify $M$ with $\mathbb R\times N$ via the temporal function $\tau$ as in Section
\ref{intermregu}. Then the curves in $I_B$ correspond one-to-one with $\Phi_\tau$-orbits in $N$. Denote the set of these $\Phi_\tau$-orbits also
with $I_B$.

\begin{prop}\label{mongeprop2}
The set formed by the intersections of orbits in $I_B$ with $A$ is $\mathcal{L}_A$-neglectable.
\end{prop}

\begin{proof}
Since a countable union of neglectable sets is neglectable one can make a few simplifying assumptions. First one can assume that $A$ is uniformly spacelike. Second one can assume that $B$
is precompact. And third one can assume that the distance between the first and the last intersections of minimizers with $B$ is uniformly bounded from below.

Let $(y_1,y_2)\in J^+ \cap B\times B$ and $\gamma\in I_B$ a minimizer between $y_1$ and $y_2$. Choose $\delta>0$ such that
$\tau(B_\delta(y_1))$ and $\tau(B_\delta(y_2))$ are disjoint. Choose $b\in \mathbb R$ between $\tau(B_\delta(y_1))$ and $\tau(B_\delta(y_2))$. Denote with $S_B$ the set of intersection
of the $\gamma\in I_B$ with $\{b\}\times N$.

\begin{lemma}\label{mongeNeg}
$S_B$ is a $\mathcal{L}_{\{b\}\times N}$-neglectable set.
\end{lemma}

\begin{proof}
Consider $\eta\in \Gamma(\tau)$ with endpoints in $B_{\delta}(y_1)\cap B$ and $B_{\delta}(y_2)\cap B$. Denote the intersection of $\eta$ with $\{b\}\times N$ by $z$.
Choose a convex neighborhood $U$ around $z$ disjoint from $B_{\delta}(y_1)\cap B$ and $B_{\delta}(y_2)\cap B$. Denote with $\eta_\alpha$ and
$\eta_\omega$ the initial and the terminal point on $\eta$ in $U$ respectively. Then one has
$$S_B\cap U \subseteq J^-(\eta_\omega)^c\cap J^+(\eta_\alpha)^c=(J^-(\eta_\omega)\cup J^+(\eta_\alpha))^c.$$
Thus there exists $r>0$ such that for every point $p\in S_B$  there exist two balls $B_r$ and $B_r'$ in $\{b\}\times N$ with $B_r\cap B_r'=\{p\}$.
Therefore for every $\e>0$ $S_B$ can be covered by at most $\e^n$ disjoint sets with volume less than $\e^{n+1}$. This shows that $S_B$ is $\mathcal{L}_{\{b\}\times N}$-neglectable.
\end{proof}

\begin{lemma}\label{mongeLip}
The map $S_B\to TN$ mapping $z\in S_B$ to the tangent vector in $\mathcal{D}_z$ of a minimizer in $I_B$ intersecting $z$ is well defined and Lipschitz.
\end{lemma}

\begin{proof}
The well-definedness is easy to see since if two minimizers $\gamma_1$ and $\gamma_2$ between points $y_1, y_2, y_3, y_4\in B$ such that $y_2\in J^+(y_1)$ and
$y_4\in J^+(y_3)$ meet at an intermediate point $z$ with different tangent vectors then $y_2\in I^+(y_3)$ and $y_4\in I^+(y_1)$. Both induces a contradiction to the achronality of $B$.

Now let $x,z\in S_B$ and $\gamma_x,\gamma_z\in I_B$ containing $x$ and $z$ in their traces respectively. Choose $y_1,y_2\in B$ such that $\gamma_z$ connects
$y_1$ and $y_2$. Then one has $x\in I^+(y_1)^c\cap I^-(y_2)^c$ by the achronality of $B$. Therefore
$$\dist(x,I^+(y_1)),\dist(x,I^-(y_2))\le C_1\dist(x,z)^2$$
for some $C_1<\infty$ depending  only $\supp\mu \cup \supp\nu$.

Choose $w\in \partial J^+(y_1)\cap \{b\}\times N$ the nearest point to $x$ and $\dot\chi(b)\in \mathcal{D}_w$ with
\begin{align}\label{mongelipeq}
\dist(\dot\chi(b),\dot\gamma_x(b))\le C_2\dist(w,z).
\end{align}
Recall that one has assumed that the distance between the intersections of minimizers with $B$ is bounded from below. Therefore
there exists $\e>0$ such that
$$\max \tau|_{B_\delta(y_1)}<b-\e<b+\e<\min\tau|_{B_\delta(y_2)}.$$
Then by Lemma \ref{actionestimate} there exists $\delta_1>0$ only depending on $\supp\mu \cup \supp\nu$ such that
$$c_L(\gamma_z(b-\e),\chi(b+\e))^2\ge \delta_1\dist(\dot\chi(b), Y_w)^2$$
where $Y_w$ denotes the tangent to the unique minimizer $\eta_w\colon [b-\e,b]\to N$ from $\gamma_z(b-\e)$ to $w$.
Further since $c_L(\gamma_z(b-\e),.)^2$ is Lipschitz up to the boundary of its domain there exists $\delta_2>0$ with
$$\dist(\chi(b+\e),\partial J^+(\gamma_z(b-\e)))\ge \delta_2 c_L^2(\gamma_z(b-\e),\chi(b+\e)).$$
By the triangle inequality and \eqref{mongelipeq} one has
\begin{align*}
\dist(\dot\chi(b),Y_w)&\ge \dist(Y_w,\dot\gamma_x(b))-C_2\dist(w,x)\\
&\ge \dist(\dot\gamma_z(b),\dot\gamma_x(b))-C_3\dist(w,z)-C_2\dist(w,x)
\end{align*}
where the last inequality follows from the Lipschitz continuity of the vector field $u\mapsto Y_u$. Since $\dist(w,x)\le \dist(z,x)$
one concludes
$$\dist(\dot\chi(b),Y_w)\ge  \dist(\dot\gamma_z(b),\dot\gamma_x(b))-(2C_3+C_2)\dist(z,x)\ge \frac{1}{2}\dist(\dot\gamma_z(b),\dot\gamma_x(b)).$$
if $\dist(\dot\gamma_z(b),\dot\gamma_x(b))\ge 2(2C_3+C_2) \dist(z,x)$. Now the triangle inequality and the last estimate imply that
\begin{align*}
\dist(\gamma_x(b+\e),&\partial J^+(\gamma_z(b-\e)))\\
&\ge \dist(\chi(b+\e),\partial J^+(\gamma_z(b-\e)))-\dist(\gamma_x(b+\e),\chi(b+\e))\\
&\ge \delta_3 \dist(\dot\gamma_z(b),\dot\gamma_x(b))^2-\dist(\gamma_x(b+\e),\chi(b+\e))
\end{align*}
for some $\delta_3>0$. Next by the continuity of $\Phi_\tau$ one has
\begin{align*}
\dist(\gamma_x(b+\e),\partial J^+(\gamma_z(b-\e)))&\ge \delta_3 \dist(\dot\gamma_z(b),\dot\gamma_x(b))^2-C_4\dist(w,x)\\
&\ge \delta_4 \dist(\dot\gamma_z(b),\dot\gamma_x(b))^2-C_{4}C_1\dist(z,x)^2
\end{align*}
for some $C_4<\infty$. Now if
$$\dist(\dot\gamma_z(b),\dot\gamma_x(b))\ge \max\left\{2(2C_3+C_2),\sqrt{\frac{C_4C_1}{\delta_4}}\right\} \dist(z,x)$$
one concludes $\gamma_x(b+\e)\in I^+(\gamma_z(b-\e))$. This in turn implies that the endpoint of $\gamma_x$ in $B$ is
contained in $I^+(y_2)$, clearly a contradiction to the achronality of $B$.
\end{proof}

By Lemma \ref{mongeNeg} the intersection of the minimizers intersecting $B$ at least twice is $\mathcal{L}_{\{b\}\times N}$-neglectable. Further by Lemma \ref{mongeLip}
the map that assigns to each intersection point the tangent of the minimizer is Lipschitz. Choose a Lipschitz extension of this map to $N$ according to Kirzbraun's Theorem
(cf. Theorem 1.31 in \cite{schwartz}). Then the unique intersection of minimizers in $I_B$ with $A$ is the image under a Lipschitz map of a $\mathcal{L}_{\{b\}\times N}$-neglectable
set. Therefore it is $\mathcal{L}_A$-neglectable.
\end{proof}

\begin{proof}[Proof of Theorem \ref{Thmmonge}]
To prove the theorem all one needs to show is that $\pi$ is concentrated on the graph of a map $F\colon M\to M$. Then $F$ is measurable and unique.
Measurabilty follows from fact that $\pi$ is a Borel measure. Uniqueness follows from the observation that if two optimal plans exists, any convex combination of both is
optimal as well. But any nontrivial convex combination of couplings that are concentrated on graphs is not concentrated on a graph unless they coincide.

Choose a dynamical optimal coupling $\Pi$. Denote with $\Pi_\triangle$ the restriction of $\Pi$ to
the set of constant minimizers and $\Pi_C:=\Pi-\Pi_\triangle$. Further set $\mu_\triangle:=(\ev_0)_\sharp \Pi_\triangle$ and $\mu_C:=(\ev_0)_\sharp \Pi_C$.
Note that by construction one has $\mu =\mu_\triangle +\mu_C$.

First one shows that $\supp\mu_\triangle\cap \supp\mu_C$ is a $\mathcal{L}_A$-neglectable set. To this end note that $\supp\mu_\triangle \subseteq \supp \nu$
since $\mu_\triangle$ is induced by constant curves. Now if $x\in\supp\mu_\triangle\cap
\supp\mu_C$, $x$ is contained in $\supp\nu$ and there exists a $y\in\supp\nu \cap J^+(x)\setminus\{x\}$. So $x$ lies on a minimizer that intersects the support of
$\nu$ at least twice. The set consisting of such points was shown in Proposition \ref{mongeprop2} to be $\mathcal{L}_A$-neglectable which implies the initial claim.

Assume for the moment that $\pi_\triangle :=(\ev_0,\ev_1)_\sharp \Pi_\triangle$ and $\pi_C :=(\ev_0,\ev_1)_\sharp \Pi_C$ are separately concentrated on a graph.
Then $\pi$ is concentrated on the union of these graphs since $\pi =\pi_\triangle+\pi_C$. The overlap of these graphs lies in $\pi_1^{-1}(\supp\mu_\triangle\cap \supp\mu_C)$.
Since $\supp\mu_\triangle\cap \supp\mu_C$ is $\mathcal{L}_A$-neglectable it is also $\mu$-neglectable and therefore $\pi_1^{-1}(\supp\mu_\triangle\cap \supp\mu_C)$
is $\pi$-neglectable. Thus $\pi$ is concentrated on a graph.

It remains to show that $\pi_\triangle$ and $\pi_C$ are concentrated separately on a graph. This claim is trivial for $\pi_\triangle$ since $\pi_\triangle$ is concentrated on the
diagonal of $M\times M$. For $\pi_C$ note that by construction $\pi_C (\triangle)=0$. Since $\pi_C(\triangle)
\ge \nu(\supp\mu)$ one can apply Proposition \ref{mongeprop1} to the situation of $\mu_C$ and $\nu_C:=(\ev_1)_\sharp \Pi_C$ with the coupling $\pi_C$.

Assume first that there exists a set $S$ with $\mu_C(S)>0$ such that for every $x\in S$ there exist
$y_1\neq y_2\in\supp \nu_C$ with $(x,y_i)\in \supp\pi_C$ and no minimizer from $x$ to $y_i$ meets $y_j$ for $i\neq j$. By the martingale property of $\pi_C$ one has
$\pi_C(\pi_1^{-1}(S))=\mu_C(S)>0$. Now for the set $R$ constructed in Proposition \ref{mongeprop1} one has $R\cap \pi_1^{-1}(S)\neq \emptyset$. But this contradicts the property of
$R$ given in Proposition \ref{mongeprop1}. Therefore the set of points transported into two different directions is $\mu_C$-neglectable.

It remains to show that the set transported along one minimizer, but to at least two points in $B$ is $\mathcal{L}_A$-neglectable. But this is the content of Proposition \ref{mongeprop2}
since $\mu_C$ is absolutely continuous with respect to $\mathcal{L}_A$. This follows directly from the assumption that $\mu$ is absolutely continuous with respect to $\mathcal{L}_A$.
\end{proof}


\section*{Introduction}

Existence of gaps in the spectra of operators of mathematical physics plays important role in many areas (e.g., solid state physics \cite{AshcroftMermin_solid}, photonic crystal manufacturing \cite{Joannopoulos_photocrystals,Kuch_pbg}, and in expander graphs construction \cite{WidgZig_anm02}, see also discussion in \cite[Section 6.1]{Kuch_BAMS}).
This also applies to constructions of thin branching structures (e.g., quantum wire circuits), which can be modeled by the so called quantum graphs (see \cite{BerKuc_book,AGA}). One of the standard ways to achieve the band-gap structure of the spectrum is by making the medium periodic, where the gaps may arise due to the Bragg scattering \cite{AshcroftMermin_solid}. However, existence of spectral gaps in periodic media is not guaranteed and is not easy to achieve and manipulate (see, e.g., \cite[Section 6.1]{Kuch_BAMS}). Thus, a different, resonant gaps technique has been explored, where identical resonators are distributed throughout the medium to create spectral gaps (the earliest reference known to the authors is \cite{Pavlov}). This idea was implemented in the discrete situation in \cite{SchAiz_lmp00} by attaching to each vertex $v$ of the graph $\Gamma$ (which is the medium in this case) an identical \emph{decoration} (resonator) $G$ (Fig. \ref{F:decor}).
\begin{figure}[ht!]
\begin{center}
\scalebox{.7}{\includegraphics{decorat}}
\caption{Decorations used by Schenker and Aizenman in \cite{SchAiz_lmp00}.}\label{F:decor}
\end{center
\end{figure}
This technique has been extended to the case of quantum graphs, see \cite[Section 5.1 and references therein]{BerKuc_book}. However, it would be more convenient in many instances (e.g., in photonic crystal theory when considering the so called inverse opal structures) to insert some internal structure into each vertex, rather than attach a decoration (resonator) to it sideways. In other words, one is looking for a \emph{spider decoration} (Fig. \ref{F:spider})\footnote{Compare with the first step of the zig-zag construction of an expander \cite{WidgZig_anm02}.}.
\begin{figure}[ht!]
\begin{center}
\scalebox{1.5}{\includegraphics{spider}}
\caption{A ``spider'' decoration replacing a vertex $V$.}\label{F:spider}
\end{center
\end{figure}

Here one hits a snag. The nice procedure in \cite{SchAiz_lmp00} does not work nearly that well when the common ``boundary'' between $\Gamma$ and $G$ consists of more than one point, as it is the case in the spider decorations.

When the boundary is a single point, by applying a rather standard technique used in considering the transmission problem between two media, one can rewrite the spectral problem on the decorated graph as the one on the original graph $\Gamma$ with an additional energy (spectral parameter) dependent potential (\emph{Dirichlet-to-Neumann operator} of the decoration, see \cite[Section 5.1]{BerKuc_book} for details). Poles of this potential arise at the spectrum of the decoration, which leads to the gap opening.

With the boundary consisting of more than one point, the arising potential term is now a meromorphic matrix function, whose poles may or may not show up, depending on the vector the matrix function is applied to. Thus, it is easy to construct examples when a spider decoration does not lead to spectral gap opening \cite[Chapter 3]{Ong_diss}.

However, as it is shown in \cite[Chapter 3]{Ong_diss}, there are some special decoration constructions that resolve this problem in the case of finite graphs. The goal of this paper is to extend the (unpublished) considerations of \cite[Chapter 3]{Ong_diss}.

We provide necessary notions and notations in Section \ref{S:prel}, the auxiliary study of the Dirichlet-to-Neumann operator of a graph in Section \ref{S:aux}, the main result on gap opening  in Section \ref{S:main}, and conclusions and some remarks in Section \ref{S:remarks}.

\section{Preliminaries}\label{S:prel}

We consider a metric graph $\Gamma_0$, i.e. a graph such that each its edge $e$ is equipped with a finite positive ``length'' $l_e$ and a coordinate $x$ identifying it with the segment $[0,l_e]$ (see more detailed discussion in \cite[Chapter 1]{BerKuc_book}). We will use the standard notations $V(\Gamma_0)$ and $E(\Gamma_0)$ for the sets of vertices and edges of the graph respectively.

We will assume in this text that the following condition on the edge lengths of the graphs $\Gamma_0$ is satisfied:
 \begin{equation}\label{E:uniform}
 \mbox{there exists }l>0\mbox{ such that } l\leq l_e\leq 1/l<\infty, \forall e\in E(\Gamma_0).
  \end{equation}
 In particular, this is true when the graph $\Gamma_0$ is either finite (i.e., has a finitely many edges and vertices) or periodic (i.e. is equipped with the co-finite action of the group $\mathbb{Z}^p$ for some $p>0$, see \cite[Section 4.1]{BerKuc_book}).

Let us also assume that $\Gamma_0$ is a $d$-regular graph (i.e. the degree of each of its vertices is equal to $d$) and $G$ is a finite metric graph with at least $d$ vertices and a singled out subset $B\subset V(G)$ consisting of $d$ vertices. The set $B$ will be called the \emph{boundary} of $G$. For each vertex $v\subset V(\Gamma_0)$ we establish a 1-to-1 correspondence between the edges adjacent to $v$ and the elements of $B$. One can now decorate in a natural way the vertex $v$ with the internal structure, which is a copy of $G$ (see again Fig. \ref{F:spider}). Doing this for all vertices of $\Gamma_0$, we obtain the \emph{decorated graph} $\Gamma$.

All graphs we consider are equipped with the self-adjoint operators\footnote{Usually called Kirchhoff Laplacians.}, $H_0$ in $L^2(\Gamma_0)$ and $H$ in $L^2(\Gamma)$, as follows: on each edge they act as $-d^2/dx^2$, with the domain consisting of functions $f$ such that
\begin{enumerate}
\item $f\in H^2(e)$ for each edge $e$;
\item $f$ is continuous on the whole graph;
\item at each vertex, the sum of the outgoing derivatives of $f$ along all adjacent edges is equal to zero (Kirchhoff condition);
\item the sum $\sum\limits_{e}\|f\|^2_{H^2(e)}$ is finite (automatic for a finite graph).
\end{enumerate}
Here $H^2(e)$ is the standard Sobolev space on the segment $e=[0,l_e]$.

We also denote by $H_G$ the analogous operator on $G$, with the exception that at the boundary vertices $v\in B$, Dirichlet conditions $f(v)=0$ are imposed instead of Kirchhoff ones. The spectrum $\sigma({H_G})$ of this operator is discrete \cite[Theorem 3.1.1]{BerKuc_book}.

We denote by $\Sigma_D$ the (discrete under our conditions of finiteness or periodicity of the graph) set of Dirichlet eigenvalues of all edges of $\Gamma_0$, i.e.
\begin{equation}
\Sigma_D:=\{\left(n\pi l_e^{-1}\right)^2\}_{n\in\mathbb{N}, e\in E(\Gamma_0)}.
\end{equation}

Let us also denote by
\begin{equation}
N: \bigoplus\limits_{e\in E(G)}H^2(e) \rightarrow l^2(B)
\end{equation}
the \emph{Neumann} operator that for any function
$$
f\in \bigoplus\limits_{e\in E(G)}H^2(e)
$$
and a vertex $v\in B$ produces the value at $v$ equal to the sum of the outgoing derivatives of $f$ along the edges of $G$ adjacent to $v$. Here we denote by $l^2(B)$ the $d$-dimensional Hilbert space of functions on $B$.

We can now define, for any $\lambda\notin \sigma(H_G)$, the \emph{Dirichlet-to-Neumann operator} (in fact, a $d\times d$-matrix) $\Lambda(\lambda)$ as follows: for any $\phi\in l^2(B)$ let $u$ be the (existing and unique) solution of the following problem:
\begin{equation}\label{E:inhom}
\begin{cases}
-d^2u/dx^2=\lambda u \mbox{ on each } e\in E(G),\\
u \mbox{ satisfies continuity and Kirchhoff condition at each vertex }v\notin B,\\
u|_B=\phi.
\end{cases}
\end{equation}
Then,
\begin{equation}
\Lambda(\lambda)\phi:=Nu.
\end{equation}
It is clear that $\Lambda(\lambda)$ is a meromorphic function with poles at $\sigma(H_D)$ only (see \cite[Section 3.5]{BerKuc_book} for more detailed consideration of Dirichlet-to-Neumann operator in the quantum graph case and its relation to the resolvent of $H_G$).

\section{Auxiliary statements}\label{S:aux}

Let $\lambda_0\in\sigma(H_G)$. As it was indicated before, and as we will see clearly in the next section, it will be important for us that for any non-zero $\phi\in l^2(B)$ the vector function $\Lambda(\lambda)\phi$ still has a pole at $\lambda_0$. It is clearly sufficient to consider vectors $\phi$ that belong to the unit sphere $S$ of $l^2(G)\approx \mathbb{C}^d$.

The following auxiliary result is crucial for our goal:

\begin{theorem}\label{T:aux}\cite{Ong_diss}
\indent
\begin{enumerate}
\item If for a given $\phi\in S$ and $\lambda=\lambda_0$ the problem \ref{E:inhom} has a solution, then $\Lambda(\lambda)\phi$ does not have singularity at $\lambda_0$.
\item If the problem \ref{E:inhom} has no solution for $\lambda=\lambda_0$ and any $\phi\in S$, then for any $\phi$, the following estimate holds in an (independent of $\phi$) neighborhood of $\lambda_0$:
\begin{equation}\label{E:estim}
\|\Lambda(\lambda)\phi\| \geq \frac{C}{|\lambda-\lambda_0|}\|\phi\|
\end{equation}
with a constant  $C$ independent of $\phi$.
\end{enumerate}
\end{theorem}
Thus, we will be looking at graphs $G$ with boundary $B$ such that the problem \ref{E:inhom} has solution only for zero Dirichlet data $\phi$. Rather than trying to describe all graphs that have this property, we will provide (for any size $d$ of the boundary $B$) constructions when this does happen, which will be sufficient for our purpose of gap opening.
\begin{theorem}\label{T:suffic}
Let $l_0>0$ and $n$ be an odd natural number. Suppose that the pair $G,B$ satisfies the following conditions:
\begin{enumerate}
\item Graph $G$ contains a cycle\footnote{which can be assumed non-self-intersecting.} $Z$ consisting of an odd number of edges of the length $l_0$;
\item Each boundary vertex $v\in B$ either belongs to $Z$, or is connected to a vertex of $Z$ by a path of edges of length $l_0$ each.
\end{enumerate}
Then, for $\lambda_0=(n\pi/l_0)^2$, there exist a neighborhood $U$ of $\lambda_0$ and a constant $C$ such that the inequality (\ref{E:estim}) holds for any $\phi$ and $\lambda\in U$.
\end{theorem}
\begin{proof}
WLOG, let us assume that $Z$ is non-self-intersecting and consider an edge $e\in Z$ (of length $l_0$, as all edges in the cycle). The solution of (\ref{E:inhom}) for $\lambda=\lambda_0$ on this edge has the form $$
u=a\cos\left(\dfrac{n\pi}{l_0}x\right)+b \sin\left(\dfrac{n\pi}{l_0}x\right).
$$
At the endpoints $x=0, l_0$, the second term vanishes. Since $n$ is odd, the first term changes its value from $a$ to $-a$ at these points. Going around an odd cycle, one concludes that this is possible only if $a=0$, and thus $u$ vanishes at all vertices of $Z$. In particular, it vanishes at all boundary vertices that belong to $Z$. For $v\in B\setminus Z$, as there exists a path of edges of length $l_0$ from $v$ to a vertex from $Z$, where we know that $u$ vanishes, the same consideration shows that $u$ vanishes at all vertices of the path. Therefore, the problem (\ref{E:inhom}) does not have solution for non-zero $\phi$, and thus, due to Theorem \ref{T:aux}, the inequality (\ref{E:estim}) follows.

\end{proof}

\section{The main result}\label{S:main}

We are ready now to formulate and sketch the proof of the main result of this article:
\begin{theorem}\label{T:main}
Let $l_0>0$ and $n$ be an odd natural number. Let also the $d$-regular graph $\Gamma_0$ satisfy (\ref{E:uniform}), and finite graph $G$ with boundary $B$, $|B|=d$ and the decorated graph $\Gamma$ are defined as before. Suppose that the following conditions are satisfied:
\begin{enumerate}
\item $\lambda_0=(n\pi/l_0)^2\notin \Sigma_D$, with $dist(\lambda_0,\Sigma_D)=r>0$;
\item The decoration (resonator) $G, B$ satisfies the conditions of Theorem \ref{T:suffic}.
\end{enumerate}
Then there exists a punctured neighborhood of $\lambda_0$, depending on $G$, topology of $\Gamma_0$, and $r$ only, which does not belong to the spectrum $\sigma(H)$.
\end{theorem}
\begin{proof}

To understand the idea of the proof, let us assume first that the graph $\Gamma_0$ (and thus $\Gamma$) is finite. Then the spectrum of $H$ is discrete. Thus, if $\lambda\in\sigma(H)$, there exists a non-zero eigenfunction $u$. Assume that the neighborhood of $\lambda_0$ has radius less than $r_1<r$. Then it contains no elements of $\Sigma_D$.

Removing all internal edges and vertices from each of the decorations in $\Gamma$, one gets a disjoint union of edges of $\Gamma_0$, since each former vertex $v\in \Gamma_0$ is replaced by $d$ vertices $v_1, \dots, v_d$, see Fig \ref{F:dots}.
\begin{figure}[ht!]
\begin{center}
\scalebox{.7}{\includegraphics{removed}}
\caption{Decoration removed from a former vertex of degree $4$.}\label{F:dots}
\end{center
\end{figure}

We denote this new graph $\widetilde{\Gamma}$.

Denoting
$$
\phi_v:=(u(v_1),\dots,u(v_d))^t,\,\phi^\prime_v:=(du/dx_{e_1}(v_1),\dots,du/dx_{e_d}(v_d))^t,
$$
where $e_1,\dots,e_d$ are the edges formerly adjacent to vertex $v$ and coordinates $x_{e_j}$ increase from the value zero at vertex $v$, one can rewrite the equation for $u$ on $\Gamma$ as the following one on $\widetilde{\Gamma}$:
\begin{equation}\label{E:removed}
\begin{cases}
-u^{\prime\prime}
=\lambda u \mbox{ on each edge},\\
\phi^\prime_v=-\Lambda(\lambda)\phi_v \mbox{ at each vertex } v\in V(\Gamma_0).
\end{cases}
\end{equation}
Since $\lambda_0$ is at a qualified distance from the Dirichlet spectrum $\Sigma_D$, the resolvent estimates for self-adjoint operators together with embedding theorems show that
\begin{equation}\label{E:resolvest1}
\sum_e\|\phi\|^2_{H^2(e)}\leq M \sum_v\|\phi_v\|^2,
\end{equation}
\begin{equation}\label{E:resolvest2}
\sum_v\|\phi^\prime_v\|^2\leq M \sum_v\|\phi_v\|^2
\end{equation}
for some constant $M$ depending only on the distance from the Dirichlet spectrum and topology of $\Gamma_0$. On the other hand, if $\lambda$ is sufficiently close to $\lambda_0$ (how close, depends on $M$ and the decoration $G$), according to Theorem \ref{T:aux}, one has
\begin{equation}\label{E:oppositeest}
\sum\limits_v\|\phi^\prime_v\|^2\geq \frac{C^2}{|\lambda-\lambda_0|^2}\sum\limits_v\|\phi_v\|^2> M \sum\limits_v\|\phi_v\|^2.
\end{equation}
This contradiction proves the claim of the theorem for finite graphs.

In the case of infinite graphs, generalized eigenfunctions with control of growth need to be used \cite{Lenz_gener_eig,HislPost}. The details will be provided elsewhere, but so far we illustrate this on the simplest example of periodic graphs,

In the case of a periodic graph, assumption that $\lambda$ belongs to the spectrum of $H$ implies existence of a quasi-periodic Bloch-Floquet generalized eigenfunction $\phi(x)$, which under the $\mathbb{Z}^p$-shifts acquires only a phase shift (see details in \cite[Section 4.2]{BerKuc_book}). Then the above consideration for the finite graph goes smoothly, if the summation over edges and vertices of $\Gamma_0$ is replaced by the same for the compact orbit space graph $\Gamma_0/\mathbb{Z}^p$.

Another option in the periodic case is to use the Floquet-Bloch decomposition and apply the above (finite case) argument for each value of the quasi-momentum\footnote{See \cite[Chapter 4]{BerKuc_book} for these notions and constructions.}.
\end{proof}

\section{Conclusions and final remarks}\label{S:remarks}
\begin{enumerate}
\item Although it is probably not easy to understand the case of a general ``spider'' decoration, the main result of this article allows one to create spectral gaps rather easily at prescribed locations. Indeed, the value $(n\pi l_0^{-1})^2$ involves an arbitrary positive length $l_0$ and odd natural number $n$, which gives one a significant freedom of choosing location. As soon as this is done, one can easily produce a spider decoration $G$ that achieves the goal. For instance, if $d=4$, each degree $4$ vertex can be replaced with the structure shown in Fig. \ref{F:repl}, where we created an odd cycle through three boundary vertices and connected the fourth one to them with a single edge.
\begin{figure}[ht!]
\begin{center}
\scalebox{0.5}{\includegraphics{repl}}
\caption{A degree $4$ vertex replaced by a ``spider'' with edges of lengths $l_0$.}\label{F:repl}
\end{center
\end{figure}
\item It was shown in \cite{Ong_diss} on examples that for even cycles and/or even $n$ the claim of the Theorem \ref{T:main} is incorrect.
\item The regularity condition on the graph $\Gamma_0$ is not truly necessary, at least in the case of finite and periodic graphs. Indeed, one can manage variable degrees by choosing different decorations, adjusted to each particular vertex and such that the corresponding resonant values $\lambda_0$ agree.
\item Besides gap's existence at a given location, its size is of importance. It depends on the value of the constant $C$ in (\ref{E:estim}). Our construction allows for a variety of decorations achieving the gap at the same location. It would be interesting to analyse the dependence of $C$ on the decoration, to pick the most effective designs.
\item More general vertex conditions can be considered and Kirchhoff conditions are used just for simplicity.
\end{enumerate}

\section*{Acknowledgment}
The work of the first two authors was partially supported by the NSF DMS grant \# 1517938. The authors express their gratitude to the NSF for the support. They are also grateful to the referees for useful comments.