M O A El Ghazaly
email: maelghazaly@kacst.edu.sa

J B A Mitchell

J J Jureta

A S Jabr

S M Alshammari

P Defrance

Electron impact induced dissociation of N 2 H + into NH +

. The threshold measured for this channel indicates the presence of excited states in the target beam.

Introduction

Collisions between electrons and molecular ions lead to reactions which differ drastically with increasing energy. At the lowest energy range (from 0 eV), only the exothermic dissociative recombination (DR) process may take place but for higher electron energies, endothermic reactions appear to play a dominant role. Above a few eV, that is, in the energy domain where DR is seen to exhibit a vanishing importance, dissociative excitation (DE) first dominates the electron-molecular ion interaction by producing one ionic fragment. For a diatomic molecular ion DE can be written in the general form:

( 1 )

At slightly higher energies, ionization processes are energetically accessible and single ionisation (SI) may be observed:

e -+ AB + → AB ++ + 2e -.

EPJ Web of Conferences

However, for diatomic systems, the doubly-charged molecule is generally unstable against dissociation so that dissociative ionisation (DI) generally dominates the reaction: e -+ AB + → A + + B + + 2e -.

( 3 )

These three processes (DE, SI, DI) display individual characteristic thresholds since they involve a transition from the initial ion state to an upper excited or ionised state that is dissociative or not. Thus DE, SI and DI are likely to be significant reactions in the chemistry of environments, where high enough electron energies are encountered, for example, in divertor and fusion-wall plasmas or in stellar nebulae. Most of the experimental studies of these reactions have not been performed using single or multiple pass merged beam methods, but using the most appropriate crossed beams method. A review of work performed up to 1998 using these various techniques has been given by Dunn and Djuric [START_REF] Dunn | Electron Impact Dissociation and Excitation of Molecular Ions in Novel Aspects of Electron-Molecule Collisions[END_REF] but there have been a number of studies published since then, especially by the groups of Louvain-la-Neuve and Oak Ridge.

In this paper, we report on new measurements for one of the dissociation channels arising from electron impact on N 2 H + . This ion has great significance in astrophysics, attested, for example, by the recent paper published in Science [START_REF] Qi | [END_REF] describing astronomical measurements of its abundance around solar nebula that allowed the mapping of the so-called "Snow Line". N 2 H + is formed by proton transfer from H + 3 to N 2 but is destroyed by charge transfer to CO which is much more abundant. When CO has condensed out of the gas phase, within the "snow line", then the N 2 H + concentration becomes significant and can be measured, thus serving as a marker for this condensation, which is a precursor for planet formation.

Being protonated nitrogen, it is likely to be present in any plasma where hydrogen and nitrogen co-exist. Thus it is considered to be one of the ions likely to be present in fusion wall plasmas where nitrogen gas will be present either due to leaks or deliberately introduced as a coolant molecule. There is a need therefore for experimental data on its reactions with energetic electrons.

Experimental method

The crossed electron-ion beam apparatus at the Catholic University of Louvain has been used for this measurement. This apparatus has been described in detail elsewhere [4] so only a brief description of the technique will be given. Figure 1 shows the experimental layout.

Ions are formed in an ECR source (1) [5], extracted and accelerated to 8 keV through the focusing Einzel lens system (2), mass selected by a magnet (3), deflected by an electrostatic spherical deflector (4) to remove neutrals formed in transit and then pass through the collision region where they interact with the electron beam produced by the electron gun (5-also shown as an insert). The electron energy can be tuned from a few eV up to 2.5 keV. Collision fragments are separated from the primary beam by a 90 • analyzing magnet (6). The primary beam is dumped and detected into a Faraday cup (7). The analyser slit (8) allows separation of the collision fragments from spurious ions coming from the primary beam. An additional 90 • spherical electrostatic analyzer (9) separates signals according to the kinetic energy and focuses ions onto a channeltron detector (10). The analyzing magnet (6) produces a uniform magnetic field (B), which acts as the standard mass analyzer. Product ions are selected according to the mass over charge ratio, which is related to the field, the radius of the ion trajectory (R B = 0.3 m) and the velocity (v):

m q = B R B v • (4)
In the electrostatic analyzer (9), the electric field (F ) improves the resolution of the system by further selecting dissociation products according to their kinetic energy: In this expression, R E is the radius of the ion trajectory (R E = 0.15 m).

E K = qF R E . ( 5
The experiments make use of the animated crossed Electron-Ion beam method full details of which are given in [6]. In SI experiments, absolute cross-sections are directly determined through the measurements of the total number of events produced during passage of electron beam across the ion beam. However, in dissociation experiments (DE and DI), the fragments are only partially collected, due to both the velocity and angular spread resulting from the kinetic-energy-release (KER) which is transferred to the products. This KER is associated with the shape of the potential surface of the upper state (excited or ionized) involved in the dissociation process. Hence, the velocity distribution of the ionic products is determined and further integrated in order to estimate the transmission factor, for each individual dissociation channel. This is done by scanning the analyser magnet and integrating the resulting product spectrum. This measurement also provides information on the KER distribution of the fragments [7].

In present type experiments, spurious contributions of molecular species formed with isotopes frequently pollute the experiment. In the present case, 14 N 15 N + ions should evidently interfere both with the primary N 2 H + beam and with the NH + fragment, the resolving power of the analyzing magnets being not sufficient to discriminate between the species. For this reason, we have used isotopically pure 14 N 2 as source gas, thus avoiding any contamination issues.

Results and discussion

First of all we did not observe any N 2 H ++ signal and indeed it seems that this ion is not stable. Theoretical calculations [8] did predict the presence of a weak deep well for this ion but also that it would rapidly dissociate. Present negative result indicates that its lifetime is certainly shorter than the transit time between the collision region and the detector (∼9 s).

Electron impact cross sections for NH + formation are shown in Fig. 2 together with the results of Fogle et al. taken using the Oak Ridge apparatus [1]. A general satisfactory agreement is seen for the magnitude of the two sets of data, though the threshold region is better covered in this work. The thermodynamic estimation of the lowest DE threshold for this ion indicates that electrons must have a kinetic energy of at least 11.36 eV in order to produce NH + . However, this value does not take into account the shape of the potential surface of the upper transition state so that this estimation must be considered as a lower limit. Present experimental data show a steep rise at about 12 eV, but the significant signal observed below this value (down to 7 eV) indicates that target ions should have considerable internal excitation. This could be ro-vibrational excitation but populated metastable electronic states could also possibly contribute to the apparent sub-threshold cross-section. Such states have been identified by Moran and co-workers [9] in N + 2 beams where states with lifetimes on the order of tens of microseconds were seen to survive the transit from the ion source to the target region. Such states might also be present in the present experiment. We shall examine this further in a subsequent publication where other measurements will be analysed.

The thermodynamic threshold for DI to produce NH + + H + is at 25.4 eV. As seen in Fig. 2, a peak appears in the data of Fogle with a threshold at about 35 eV. This onset appears at the same energy in our results but the result is rather a plateau. Such an ionisation process must of course pass through a transition to an upper excited state and this would indicate that this state has a steeply descending slope in the Franck-Condon region. To our knowledge, to date there have not been any calculations of potential energy surfaces leading to this channel. The full discussion of the present experiment will appear in a subsequent publication with details of the work performed with the deuterated ion N 2 D + for other reaction channels. Kinetic Energy Release distribution of the collision fragments will also be presented and discussed.

Figure 1 .

 1 Figure 1. Crossed electron-ion beam apparatus at Louvain-la-Neuve.

Figure 2 .

 2 Figure 2. Measured absolute cross section for the electron impact dissociative excitation of N 2 H + leading to NH + formation. The green full circles are our data, inverted triangles, those of Ref. [1].


Erwan Hillion
email: erwan.hillion@uni.lu

W 1,+ -interpolation of probability measures on graphs

We generalize an equation introduced by Benamou and Brenier in [BB00] and characterizing Wasserstein Wp-geodesics for p > 1, from the continuous setting of probability distributions on a Riemannian manifold to the discrete setting of probability distributions on a general graph. Given an initial and a final distributions (f0(x))x∈G, (f1(x))x∈G, we prove the existence of a curve (ft(k)) t∈[0,1],k∈Z satisfying this Benamou-Brenier equation. We also show that such a curve can be described as a mixture of binomial distributions with respect to a coupling that is solution of a certain optimization problem.

Introduction

Given some p ≥ 1, we consider the space P p (X) of probability distributions over a metric space (X, d) having a finite p-th moment. On this space we define the Wasserstein distance W p by W p (µ 0 , µ 1 ) p := inf π∈Π(µ0,µ1) X×X d(x 0 , x 1 ) p dπ(x 0 , x 1 ),

where the set Π(µ 0 , µ 1 ) is the set of couplings of µ 0 and µ 1 , i.e. the set of probability distributions π on X × X having µ 0 and µ 1 as marginals.

An comprehensive study of the minimization problem (1), called Monge-Kantorovitch problem, can be found in Villani's textbooks [START_REF] Villani | Topics in optimal transportation[END_REF] and [START_REF] Villani | Optimal transport: old and new[END_REF]. Let us recall what is important for our purposes: under very general assumptions, it is possible to prove the existence of a minimizer π ∈ Π(µ 0 , µ 1 ) for problem (1), called optimal coupling, and that W p is indeed a metric on P p (X). Moreover, if we suppose that (X, d) is a geodesic space, i.e. if the distance d(x 0 , x 1 ) is exactly the length of the shortest curve joining x 0 to x 1 , then the metric space (P p (X), W p ) is also a geodesic space. In particular, each couple µ 0 , µ 1 ∈ P 2 (X) can be joined curve (µ t ) t∈[0,1] of minimal length for W 2 , called W 2 -Wasserstein geodesic.

In their seminal papers [START_REF] Sturm | On the geometry of metric measure spaces[END_REF], [START_REF] Sturm | On the geometry of metric measure spaces[END_REF] and [START_REF] Lott | Ricci curvature for metric-measure spaces via optimal transport[END_REF], Sturm and independently Lott and Villani studied the links between the geometry of a measured geodesic space (X, d, ν) and the behaviour of the entropy functional along the W 2 -Wasserstein geodesics on P 2 (X). For instance, (X, d, ν) is said to satisfy the curvature condition CD(K, ∞) for some K ∈ R if for each couple of probability distributions µ 0 , µ 1 ∈ P 2 (X) there exists a W 2 -geodesic (µ t ) t∈[0,1] such that

∀t ∈ [0, 1] , H ν (µ t ) ≤ (1 -t)H ν (µ 0 ) + tH ν (µ 1 ) -K t(1 -t) 2 W 2 (µ 0 , µ 1 ) 2 , (2)
where the relative entropy functional H ν (•) is defined by

H ν (ρν) := X ρ(x) log(ρ(x))dν(x) (3)
if µ = ρν for some density ρ, and by H ν (µ) := ∞ otherwise.

If the measured geodesic space (X, d, ν) is a compact Riemannian manifold with its usual distance an normalized volume measure, the curvature condition CD(K, ∞) is shown to be equivalent to the bound Ric ≥ K on the Ricci curvature tensor. Another important property is the stability of the condition CD(K, ∞) under measured Gromov-Hausdorff convergence.

Moreover, if CD(K, ∞) is satisfied for some K > 0, one can prove functional inequalities on (X, d, ν) such as the logarithmic Sobolev inequality, which asserts that

H ν (f dν) ≤ 1 2K X |∇ -f | 2 f dν, (4)
for any Lipschitz probability density f and where |∇ -f | is to be seen as a particular form of the norm of a gradient. As a corollary, it can be shown that under the condition CD(K, ∞) for K > 0 a Poincaré inequality holds: for any Lipschitz funtion h : X → R such that X hdν = 0, we have

X h 2 dν ≤ 1 2K X |∇ -h| 2 dν. (5)
Since the pioneering works of Sturm and Lott-Villani, the theory of measured geodesic spaces satisfying CD(K, ∞) has been thoroughly studied in a large number of papers, among which the most impressive are the works by Ambrosio, Gigli and Savaré (see for instance [START_REF] Ambrosio | Heat flow and calculus on metric measure spaces with Ricci curvature bounded below-the compact case[END_REF]) and by Erbar,Kuwada and Sturm ([EKS13]).

Several obstacles prevent us from a direct generalization of Sturm-Lott-Villani theory to the framework of discrete metric spaces. Indeed, if (X, d) is a graph with its usual distance, equation (1) still defines a metric on the space P p (X), but if p > 1 then the length of non-trivial curves in (P(X), W p ) is +∞, which means that it is not a geodesic space. In particular, Wasserstein W 2 -geodesics do not exist in general.

Several solutions have been proposed to overcome this difficulty, and there are now many different definitions of Ricci curvature bounds on discrete spaces. The most notable of them are the coarse Ricci curvature, defined by Ollivier in [START_REF] Ollivier | Ricci curvature of Markov chains on metric spaces[END_REF], and the Erbar-Maas curvature, defined in [START_REF] Erbar | Ricci curvature of finite Markov chains via convexity of the entropy[END_REF]. The latter is based on the study of the gradient flow of the entropy and present some similarities with our own approach.

In this paper, we place ourselves in the framework of a connected and locally finite graph G, endowed with its usual graph distance and the counting measure as the reference measure. In this framework, a probability distribution will be denoted by its density, i.e. by a function f : G → R + suwh that x∈G f (x) = 1. Given two probability distributions f 0 and f 1 on G, we investigate the question of the generalization of the notion of W p -geodesic joining f 0 to f 1 in a setting where such a curve does not exist. Our goal is to provide a way to chose, among the set of all W 1 -geodesics joining f 0 to f 1 , a curve which shares some properties satisfied by W p -geodesics for p > 1. Such curves will be called W 1,+ geodesics on the graph G.

This article is to be seen as the first of a two-paper research work. A following article will investigate the convexity properties of the entropy functional along those particular W 1 geodesics, in the view of obtaining a discrete version of equation (2) strong enough to imply discrete versions of log-Sobolev or Poincaré inequalities. This ultimate goal has to be kept in mind even in this present paper because it will motivate the definition of a W 1,+ -geodesic between f 0 and f 1 : along such a curve, some technical tools will allow us to give bounds on the second derivative of the entropy.

Our starting point is the article [START_REF] Benamou | A numerical method for the optimal timecontinuous mass transport problem and related problems[END_REF], by Benamou and Brenier. In this paper, the authors reformulate the Monge-Kantorovitch problem in terms of velocity fields and prove the following: Theorem 1.1. Let µ 0 , µ 1 be two probability distributions on a Riemannian manifold (M, g) and p > 1. Then

W p (µ 0 , µ 1 ) p = inf M 1 0 |v t (x)| p dµ t (x)dt, (6)
the infimum being taken over the families of probability distributions (µ t ) := (f t d vol) joining µ 0 to µ 1 and all velocity fields (v t (x)) satisfying

∂ ∂t f t (x) = -∇ • (f t (x)v t (x)),
where ∇• is the divergence operator on M . Moreover the minimizing curve

(µ t ) t∈[0,1] is the W p - geodesic joining µ 0 to µ 1 .
This theorem has been extended to the framework of separable Hilbert spaces by Ambrosio, Gigli and Savré in [AGS].

The strategy used by Erbar and Maas in [START_REF] Erbar | Ricci curvature of finite Markov chains via convexity of the entropy[END_REF] is based on a generalization of the minimization problem (6) in the framework of discrete Markov chains. Our approach will consist in defining a discrete version of a characterization of its solutions. More precisely, as pointed in [START_REF] Benamou | A numerical method for the optimal timecontinuous mass transport problem and related problems[END_REF], the formal optimality condition for the optimization problem (6) can be written:

∂ ∂t v t (x) = -v t (x)∇ • v t (x). ( 7
)
Another point of view on the formal optimality condition (7) is provided by writing the velocity field (v t (x)) as the gradient of a family of convex functions v t := grad Φ t . As explained for instance in [0V00], it can be proven that such a function Φ satisfies the Hamilton-Jacobi equation

∂ ∂t Φ t + 1 2 |∇Φ t | 2 = 0. (8)
It suffices to consider the gradient of equation (8) to recover equation (7).

The links between the convexity of the entropy H(t) of µ t and the Ricci curvature tensor on the manifold M are seen on the following heuristic formula, established by Otto and Villani in [0V00]:

H ′′ (t) = M [Tr((D 2 Φ t ) T D 2 Φ t ) + Ric(grad Φ t , grad Φ t )]dµ t . (9)
In particular, the non-negativity of the tensor Ric easily implies that H ′′ (t) ≥ 0.

The formal optimality condition (7) on velocity fields makes sense only when v is regular enough. The question of the regularity of optimal couplings is a difficult topic, see for instance [AGS]. However, what is important for our purposes is that (7) can be used to construct W 2 -geodesics: if (f t (x)) is a smooth family of probability densities satisfying the transport equation (1.1) for a smooth velocity field (v t (x)) satisfying the condition (7), then the curve

(f t (x)) is a W 2 -geodesic.
In the simpler framework of the real line R with usual distance and Lebesgue reference measure, it is possible to give an equivalent statement of this result without introducing explicitly the velocity field.: Proposition 1.2. Let (f t (x)) be a family of smooth probability densitites on R. We define the families of functions

g t (x) := - x -∞ ∂ ∂t f t (z)dz , h t (x) := - x -∞ ∂ ∂t g t (z)dz. ( 10
)
We suppose that g t (z) > 0 and that the following one-dimensional Benamou-Brenier condition holds:

f t (x)h t (x) = g t (x) 2 . ( 11
)
Then (f t (x)) is a W p -geodesic for any p > 1.

To prove Proposition 1.2, it suffices to realize that equation (11) easily implies equation (7).

Apart from regularity issues, which will not play an important role in a discrete framework, the main restriction made in the statement of Proposition 1.2 is the non-degeneracy condition g t (z) > 0. It is quite easy to prove that such a condition implies that f 0 is stochastically dominated by f 1 . In the setting of graphs, we will introduce the notion of W 1 -orientation (see Paragraph 2.2) in order to force the function g t to stay positive.

The main purpose of this article is to study curves in the space of probability distributions on a graph which satisfy a discrete version of the Benamou-Brenier condition (11).

• The goal of Section 2 is to provide a generalization of equations ( 10) and (11) to this discrete setting. We will first show that these equations can be recovered in a particular form in the case of contraction of measures. Given a couple of probability distributions f 0 , f 1 defined on G, we then endow G with an orientation which will allow us to give a general definition of W 1,+ -geodesics on G. The terminology "W 1,+ -geodesic" will be explained by considering a discrete version of problem (6) when p > 1 is close to 1.

• In Section 3, we are looking for necessary conditions satisfied by W 1,+ -geodesics on G. In particular, we prove in Theorem 3.18 that if f 0 and f 1 are finitely supported, then any W 1,+geodesic (f t ) can be written as a mixture of binomial distributions supported on geodesics of G.

• In Section 4 we prove the existence of W 1,+ -geodesics (f t ) with prescribed initial and final distributions f 0 and f 1 . The construction of such curves suggests us strong links with the "Entropic Interpolations" studied in a recent series of papers by Léonard.

The discrete Benamou-Brenier condition

In this paper, we consider a locally finite and connected graph G. A path γ on G of length n = L(γ) is a collection of vertices γ(0), . . . , γ(n) ∈ G such that γ(i) ∼ γ(i+1) for every i = 0, . . . n-1, where the relation x ∼ y means that (xy) is in the edge set of the graph G. To any path γ : {0, . . . n} → G are associated its endpoints e 0 (γ) := γ(0) and e 1 (γ) := γ(n).

We will use the usual graph distance on G: d(x, y) is the length of the shortest path joining x to y. The set of geodesics joining x to y, denoted by Γ x,y , is the set of paths γ joining x to y such that L(γ) = d(x, y). The set of all geodesics on G is denoted by Γ(G).

A coupling π ∈ Π(f 0 , f 1 ) is said to be a W p -optimal coupling for some p ≥ 1 if it is a minimizer for the functional

I p : π → x,y∈G×G d(x, y) p π(x, y). (12)
We denote by Π p (f 0 , f 1 ) the set of W p -optimal couplings.

Remark 2.1. The equality

I 1 (απ 1 + (1 -α)π 2 ) = αI 1 (π 1 ) + (1 -α)I 1 (π 2 ) proves that the set Π 1 (f 0 , f 1 ) is a convex subset of Π(f 0 , f 1 ).

Contraction of measures and the Benamou-Brenier equation

Among early attempts to generalize particular Wasserstein geodesics to the discrete case, one important example is given by the thinning operation:

Definition 2.2. Let f be a probability distribution finitely supported on Z + . The thinning of f is the family (T t f ) of probability distributions defined by

T t f (k) := l≥0 bin l,t (k)f (l) = l≥0 l k t k (1 -t) l-k f (l), ( 13
)
where by convention l k = 0 if l < 0 or if k / ∈ {0, . . . l}.

The operation f → T t f is often seen as a discrete version of the operation

f (x) → f t (x) := 1 t f x t , (14)
and is for instance used to state a weak law of small numbers (see [START_REF] Harremoës | Thinning, entropy, and the law of thin numbers[END_REF]) about the limit in distribution of T 1/n (f ⋆n ) when n → ∞.

We know that, given a smooth probability density f on R, the family (f t ) defined by equation ( 14) is a W p -geodesic for any p ≥ 1. According to Sturm-Lott-Villani theory, the metric space (R, | • |) satisfies the condition CD(0, ∞), so the entropy H(t) of f t with respect to the Lebesgue measure is a convex function of t. On the other hand, a theorem by Johnson and Yu (see [START_REF] Yu | Concavity of entropy under thinning[END_REF]) asserts that the entropy of the thinning T t f is also a convex function of t. The proof of this theorem given in [START_REF] Hillion | Contraction of measures on graphs[END_REF] relies on the following: Proposition 2.3. Let (f t ) := (T t f ) be the thinning family associated to a probability distribution f = f 1 supported on Z + . We define the families of functions (g t ) and (h t ) by

g t (k) := - l≤k ∂ ∂t f t (l) , h t (k) := - l≤k ∂ ∂t g t (l). ( 15
)
The triple (f t , g t , h t ) then satisfies the discrete Benamou-Brenier equation:

∀k ∈ Z , f t (k)h t (k -1) = g t (k)g t (k -1). (16)
Moreover, g t (k) ≥ 0, and if g t (k) = 0 then either f t (k + 1) = 0 or h t (k) = 0.

Remark 2.4. Denoting by ∇ 1 (resp. ∇ 2 ) the left derivative operator (resp. the left second derivative operator) defined by

∇ 1 u(k) := u(k) -u(k -1) (resp. ∇ 2 u(k) = u(k) -2u(k -1) + u(k -2)), we thus have ∂f t (k) ∂t = -∇ 1 g t (k) , ∂ 2 f t (k) ∂t 2 = ∇ 2 h t (k).
The proof of the convexity of the entropy along thinning families relies so importantly on Proposition 2.3 that this proof can be used verbatim to prove a stronger statement: Proposition 2.5. Let (f t ) be a family of finitely supported probability distributions on Z. We suppose that the families of functions (g t ) and (h t ), defined by equation (15), satisfy the discrete Benamou-Brenier equation (16) and the non-negativity condition g t (k) ≥ 0. Then the entropy H(t) of f t is a convex function of t.

Because the similarities with equation (11), it seems legitimate to consider a family of measures satisfying equation ( 16) and the non-negativity condition g t (k) ≥ 0 as a pseudo W p -geodesic, for p > 1, along which the entropy functional is convex, which is reminiscent of Sturm-Lott-Villani theory.

The notion of thinning has been extended in [START_REF] Hillion | Contraction of measures on graphs[END_REF] to the setting of general graphs in the following way: we consider a probability distribution f 1 defined on G and another probability measure f 0 which is a Dirac mass at a given point o ∈ G. In this case, an interpolating curve (f t ), called contraction of f 1 on o, is defined as a mixture of binomial distributions by

f t := z∈G 1 |Γ o,z | γ∈Γ(o,z) bin γ,t , (17)
where the binomial distribution on γ is related to the classical binomial distribution by

∀p ∈ {0, . . . L(γ)} , bin γ,t (γ(p)) := bin L(γ),t (p) (18)
and where |Γ o,z | denotes the cardinality of the set Γ o,z of geodesics joining o to z.

A couple of initial and final distributions δ o = f 0 and f 1 being given, we define a partial order on the set of vertices of G by writing x 1 ≤ x 2 if the vertex x 1 belongs to a geodesic γ ∈ Γ o,x2 . If x 1 ∼ x 2 and x 1 ≤ x 2 , we say that (x 1 x 2 ) is an oriented edge and we write x 2 ∈ F (x 1 ),

x 1 ∈ E(x 2 ) or x 1 → x 2 .
To the oriented graph (G, →) are associated two other oriented graphs:

Definition 2.6. The oriented edge graph (E(G), →) is the graph of oriented couples x 1 → x 2 ∈ G, oriented itself by the relation (x 1 x 2 ) → (x 2 x 3 ). In particular, for any

(x 1 x 2 ) ∈ (E(G), →) we have E((x 1 x 2 )) = {(x 0 x 1 ) : x 0 ∈ E(x 1 )} , F ((x 1 x 2 )) = {(x 2 x 3 ) : x 3 ∈ F (x 2 )}.
Similarly, we define the graph of oriented triples (T (G), →) := (E(E(G)), →), having as vertices the triples (x 1 x 2 x 3 ) with x 1 → x 2 → x 3 and edges between each couple (x 0 x 1 x 2 ) and (x 1 x 2 x 3 ).

Remark 2.7. The graph G being now oriented, the notations E(G) and T (G) stand for (E(G), →) and (T (G), →), which is a slight abuse of notation. For instance, (xy) ∈ E(G) imply that x → y. This remark will still be valid once introduced the W 1 -orientation on G.

Orienting the graph G allows us to define a divergence operator:

Definition 2.8. The divergence of a function g : E(G) → R is the function ∇g : G → R defined by ∀x 1 ∈ G , ∇g(x 1 ) := x2∈F (x1) g(x 1 x 2 ) - x0∈E(x1) g(x 0 x 1 ).
Similarly, the divergence of a function h :

T (G) → R is the function ∇h : E(G) → R defined by ∇h(x 1 x 2 ) := (x2x3)∈F (x1x2) h(x 1 x 2 x 3 ) - (x0x1)∈E(x1x2) h(x 0 x 1 x 2 ).
We use this orientation to express the function f t as a product of two functions satisfying interesting differential equations: Proposition 2.9. There exists a couple (P t ), (Q t ) of families of non-negative functions on G such that:

1. We have f t (x) = P t (x)Q t (x).

2. The functions P and Q satisfy the equations

∂ ∂t P t (x 1 ) = x0∈E(x1) P t (x 0 ) , ∂ ∂t Q t (x 1 ) = - x2∈F (x1) Q t (x 2 ). ( 19
)
This proposition is proven in [START_REF] Hillion | Contraction of measures on graphs[END_REF]. We can now use Definition 2.8 and 2.9 to state a generalized version of Proposition 2.3: Proposition 2.10. We define the families of functions

(g t ) : E(G) → R and (h t ) : T (G) → R by g t (x 1 x 2 ) := P t (x 1 )Q t (x 2 ) , h t (x 0 x 1 x 2 ) := P t (x 0 )Q t (x 2 ). ( 20
)
1. The functions f , g and h satisfy the differential equations

∂ ∂t f t (x 1 ) = -∇g t (x 1 ) , ∂ ∂t g t (x 1 x 2 ) = -∇h t (x 1 x 2 ). ( 21
)
2. For every oriented triple

(x 0 x 1 x 2 ) ∈ T (G) we have h t (x 0 x 1 x 2 )f t (x 1 ) = g t (x 0 x 1 )g t (x 1 x 2 ). ( 22
)
Remark 2.11. As in the thinning case, Proposition 2.10, and in particular equation ( 22) are used to study the convexity of the entropy functional along contraction families on graphs.

The W 1 -orientation

It is not possible to use directly Proposition 2.10 to propose a general Benamou-Brenier condition because such a definition relies on an orientation of the graph G which has been constructed by using the fact that f 0 is Dirac. As a first necessary step in the construction of general W 1,+geodesics, we thus need to find a nice orientation on G, depending on the initial and final measures f 0 and f 1 .

The term "nice orientation" is vague, but the study of the thinning and of the contraction families suggests that, in order to have interesting consequences on the convexity of the entropy, we should at least require that g t (x 1 x 2 ) ≥ 0 for every x 1 → x 2 ∈ E(G). As we will see at the end of this paragraph, this requirement can be interpreted in the framework of optimal transportation theory.

We first recall some properties of supports of W 1 -optimal couplings: Definition 2.12. Given a couple f 0 , f 1 of finitely supported measures, we associate the set

C(f 0 , f 1 ) := {(x, y) ∈ G × G : ∃π ∈ Π 1 (f 0 , f 1 ), π(x, y) > 0}. ( 23
)
Equivalently, C(f 0 , f 1 ) is the smallest subset of G×G containing the supports of all the W 1 -optimal couplings between f 0 and f 1 .

Proposition 2.13. There exists

π ∈ Π 1 (f 0 , f 1 ) such that Supp(π) = C(f 0 , f 1 ). Proof. For every (x, y) ∈ C(f 0 , f 1 ), there exists a coupling π (x,y) ∈ Π 1 (f 0 , f 1 ) with π (x,y) (x, y) > 0.
As f 0 and f 1 are finitely supported, we can consider the barycenter

π := 1 |C(f 0 , f 1 )| (x,y)∈C(f0,f1) π (x,y) , (24)
which by convexity is in Π 1 (f 0 , f 1 ) and which is clearly fully supported in C(f 0 , f 1 ).

A tool often used when studying the support of optimal couplings is the cyclic monotonicity property:

Lemma 2.14. If (x 0 , y 0 ), . . . (x p , y p ) are in C(f 0 , f 1 ) then p i=0 d(x i , y i ) ≤ d(x 0 , y p ) + p-1 i=0 d(x i+1 , y i ). ( 25
)
Proof. We consider a coupling π ∈ Π 1 (f 0 , f 1 ) as constructed in Proposition 2.13 and a number 0 < a < inf i (π(x i , y i )). We introduce the function h on G × G defined by h(x 0 , y p ) := a, h(x, y) := a if (x, y) = (x i+1 , y i ) for some i ∈ {0, . . . p-1}, h(x, y) := -a if (x, y) = (x i , y i ) for some i ∈ {0, . . . p}, and h(x, y) := 0 elsewhere. Then π + h is a coupling in Π(f 0 , f 1 ) and

I 1 (π + h) -I 1 (π) = a d(x 0 , y p ) + p-1 i=0 d(x i+1 , y i ) - p i=0 d(x i , y i ) , ( 26
) but π ∈ Π 1 (f 0 , f 1 ) implies I 1 (π + h) ≥ I 1 (π), which shows equation (25).
Lemma 2.14 is used to define unambiguously an orientation on some edges of G:

Theorem 2.15. Let γ (1) , γ (2) be two geodesics in G such that (e 0 (γ (i) ), e 1 (γ

(i) )) ∈ C(f 0 , f 1 ) for i = 1, 2. Then for any (k 1 , k 2 ) with k i ≤ L(γ (i) ) -1 we cannot have both identities γ (1) (k 1 ) = γ (2) (k 2 + 1) and γ (1) (k 1 + 1) = γ (2) (k 2 ).
Proof. Suppose that both identities γ (1) (k 1 ) = γ (2) (k 2 + 1) and γ (1) (k 1 + 1) = γ (2) (k 2 ) hold. By considering the path e 0 (γ (1) ),

• • • γ (1) (k 1 ), γ (2) (k 2 + 2), • • • e 1 (γ (2)
), we see that

d(e 0 (γ (1) ), e 1 (γ (2) )) ≤ k 1 + L(γ (2) ) -k 2 -1.
Similarly we have d(e 0 (γ (2) ), e 1 (γ

(1) )) ≤ k 2 + L(γ (1) ) -k 1 -1. Since L(γ (i) ) = d(e 0 (γ (1)
), e 1 (γ (1) )) for i = 1, 2, we have

d(e 0 (γ (1) ), e 1 (γ (1) )) + d(e 0 (γ (2) ), e 1 (γ (2) )) ≥ d(e 0 (γ (1) ), e 1 (γ (2) )) + d(e 0 (γ (2) ), e 1 (γ (1) )) + 2, ( 27
)
which by Lemma 2.14 is a contradiction.

Definition 2.16. Let f 0 , f 1 be two finitely supported probability distributions on G.

• The W 1 -orientation with respect to f 0 , f 1 is defined orienting the edge (x, y) ∈ E(G) by x → y if there exists a geodesic γ on G such that 1. (e 0 (γ), e 1 (γ)) ∈ C(f 0 , f 1 ).

2. γ(k) = x, γ(k + 1) = y for some k ∈ {0, . . . L(γ) -1}.

• An oriented path on the oriented graph (G, →) is an application γ : {0, . . . L} → G such that γ(i) → γ(i + 1) for i = 0, . . . L -1.

• We define a partial order relation on the vertices of G by writing x ≤ y if there exists an oriented path joining x to y.

An important property of the W 1 -orientation is the following:

Theorem 2.17. Every oriented path on (G, →) is a geodesic.

Proof. Let γ be an oriented path on (G, →) of length n. To show that γ is a geodesic, it suffices to prove that d(γ(0), γ(n)) ≥ n. By definition of the W 1 -orientation, for each i ∈ {0, . . . n -1} there exists a geodesic γ (i) of length L i ≥ 1 and k i ∈ {0, . . . L i -1} such that

• (e 0 (γ (i) ), e 1 (γ

(i) )) ∈ C(f 0 , f 1 ), • γ (i) (k i ) = γ(i), • γ (i) (k i + 1) = γ(i + 1).
By Lemma 2.14, setting x i := e 0 (γ (i) ) and y i := e 1 (γ (i) ), we have

n-1 i=0 d(x i , y i ) ≤ d(x 0 , y n-1 ) + n-2 i=0 d(x i+1 , y i ). ( 28
) But, γ (i) being a geodesic of G, we have d(x i , y i ) = d(e 0 (γ (i) ), e 1 (γ (i) )) = L i . Furthermore, for i ∈ {0, . . . n -2} we have d(x i+1 , y i ) ≤ d(x i+1 , γ(i + 1)) + d(γ(i + 1), y i ) = d(γ (i+1) (0), γ (i+1) (k i+1 )) + d(γ (i) (k i + 1), γ (i) (L i )) = k i+1 + L i -k i -1.
We also have the estimation

d(x 0 , y n-1 ) ≤ d(x 0 , γ(0)) + d(γ(0), γ(n)) + d(γ(n), y n-1 ) = d(γ (0) (0), γ (0) (k 0 )) + d(γ(0), γ(n)) +d(γ (n-1) (L n-1 ), γ (n-1) (k n-1 + 1)) = k 0 + L n-1 -k n-1 -1 + d(γ(0), γ(n)).

We finally have

n-1 i=0 L i ≤ k 0 + L n-1 -k n-1 -1 + d(γ(0), γ(n)) + n-2 i=0 k i+1 + L i -k i -1, (29)
which gives 0 ≤ d(γ(0), γ(n)) -n and proves the theorem.

The following shows that the W 1 -orientation is in some sense stable by restriction:

Proposition 2.18. Let (f t ) t∈[0,1] be a W 1 -geodesic on G. For 0 ≤ s ≤ t ≤ 1, let (x, y) in E(G)
such that x → y for the W 1 -orientation with respect to f s , f t . Then x → y for the W 1 -orientation with respect to f 0 , f 1 .

Proof. It suffices to show that, if π ∈ Π 1 (f s , f t ) and π(b, c) > 0 then b ≤ c for the partial order coming from the W 1 -orientation w.r.t. f 0 , f 1 .

The proof of this fact is inspired by the 'gluing lemma' stated and explained in [START_REF] Lott | Ricci curvature for metric-measure spaces via optimal transport[END_REF]: let

π (1) ∈ Π 1 (f 0 , f s ), π (2) ∈ Π 1 (f s , f t ) and π (3) ∈ Π 1 (f t , f 1 )
. We consider the 'gluing' π of these three couplings, defined by:

π(a, d) := b,c∈G π (1) (a, b)π (2) (b, c)π (3) (c, d) f s (b)f t (c) ,
where the quotient is zero when

f s (b) = 0 or f t (c) = 0. It is easily shown that π ∈ Π(f 0 , f 1 ). Moreover, W 1 (f 0 , f 1 ) ≤ a,d∈G d(a, d)π(a, d) ≤ a,b,c,d∈G (d(a, b) + d(b, c) + d(c, d))π(a, d) = a,b,c,d∈G (d(a, b) + d(b, c) + d(c, d)) π (1) (a, b)π (2) (b, c)π (3) (c, d) f s (b)f t (c) = a,b∈G d(a, b)π (1) (a, b) + b,c∈G d(b, c)π (2) (b, c) + c,d∈G d(c, d)π (3) (c, d) = W 1 (f 0 , f s ) + W 1 (f s , f t ) + W 1 (f t , f 1 ) = W 1 (f 0 , f 1 ).
This shows the W 1 -optimality of π and the equality

d(a, d)π(a, d) = (d(a, b) + d(b, c) + d(c, d))π(a, d).
Theorem 2.17 shows that whenever π(a, d) > 0, we have a ≤ b ≤ c ≤ d. On the other hand, if π (2) (b, c) > 0 then there exists a ∈ Supp(f 0 ) and d ∈ Supp(f 1 ) with π (1) (a, b) > 0 and π (3) (c, d) > 0, so π(a, b) = 0 and so b ≤ c.

We now prove:

Theorem 2.19. Let (f t ) be a smooth W 1 -geodesic on G. We endow this graph with the W 1orientation with respect to f 0 , f 1 . There exists a family (g t ) :

E(G) → R such that • ∀x ∈ G, ∂ ∂t f t (x) = -∇g t (x). • ∀(xy) ∈ E(G) , g t (xy) ≥ 0.
Moreover, there exists a family h t : T (G) → R such that

∀(xy) ∈ E(G) , ∂ ∂t g t (xy) = -∇h t (xy).
We first prove a general result implying the existence of a family (g t ) such that ∂ ∂t f t (x) = -∇g t (x):

Lemma 2.20. Let (G, →) be an oriented graph and u : G → R finitely supported such that x∈G u(x) = 0. Then there exists g : (E(G), →) → R with ∇g = u. Proof. We consider two scalar products, on the spaces of functions defined respectively on G and E(G), defined by

< u, v > G := x∈G u(x)v(x) , < a, b > E := x→y a(xy)b(xy).
The adjoint of the divergence operator ∇ is -∂, where ∂ is the linear operator ∂ defined by (∂u)(xy) := u(y) -u(x), in the sense that

< ∇a, u > G = -< a, ∂u > E ( 30
)
for any couple u, a of functions respectively defined on G and E(G). The kernel of ∂ is the one-dimensional space generated by the constant function v = 1. The condition x∈G u(x) = 0 is thus equivalent to < u, v > G = 0 or u ∈ (ker(∂)) ⊥G . We thus want to prove the inclusion (ker(∂)) ⊥G ⊂ im(∇). As the linear spaces we are considering are finite-dimensional, this inclusion is equivalent to (im(∇)) ⊥G ⊂ ker(∂). Let u ∈ (im(∇)) ⊥G . Then for any b : (E(G), →) → R we have < ∇b, u > G = 0, so < b, ∂u > E = 0, which proves that u ∈ ker(∂).

As we have x∈G ∂ ∂t f t (x) = 0, Lemma 2.20 gives the existence of a family (g t ) with ∂ ∂t f t (x) = -∇g t (x). However, this result does not provide an explicit construction of g and in general nothing can be said about its sign.

Proof of Theorem 2.19. Let G ′ be a spanning tree of G, i.e. a tree having the same vertices as G, but with possibly fewer edges. We endow G ′ with the restriction of the orientation on G. According to Lemma 2.20, there exists a family of functions (g t ) :

E(G ′ ) → R + satisfying ∂ ∂t f t (x) = -∇g t (x).
As G ′ is a tree, we know that removing an edge (x 0 y 0 ) from the graph G ′ will cut it into two disjoint subgraphs

G ′ 1 := G ′ 1 (x 0 y 0 ) and G ′ 2 := G ′ 2 (x 0 y 0 ) such that x 0 ∈ G ′ 1 and y 0 ∈ G ′ 2 . Let u (x0y0)
be the indicator function of G ′ 1 . This function satisfies (∂u (x0y0) )(xy) = -1 if (xy) = (x 0 y 0 ) and (∂u (x0y0) )(xy) = 0 otherwise, which implies:

g t (x 0 y 0 ) = - (xy)∈E(G ′ g t (xy)(∂u (x0y0) )(xy) = -< g t , ∂u (x0y0) > E =< ∇g t , u (x0y0) > G = -< ∂ ∂t f t , u (x0y0) >= - z∈G ′ 1 ∂ ∂t f t (z).
We want to prove that g t (x 0 y 0 ) ≥ 0. Actually we will prove that the function t → z∈G ′ 1 f t (z) is strictly decreasing, so we have g t (x 0 y 0 ) > 0. For 0 ≤ s ≤ t ≤ 1, let π ∈ Π 1 (f s , f t ). We have:

z∈G ′ 1 f s (z) = x≤y∈G : x∈G ′ 1 π(x, y) , z∈G ′ 1 f t (z) = x≤y∈G : y∈G ′ 1 π(x, y)
By Proposition 2.18, we know that if π(x, y) > 0 then x ≤ y. In particular, we cannot have x ∈ G ′ 2 and y ∈ G ′ 1 . Equivalently, if x ≤ y, π(x, y) > 0 and y ∈ G 1 then x ∈ G 1 . Consequently, we have

z∈G ′ 1 f s (z) - z∈G ′ 1 f t (z) = - x≤y∈G : x∈G ′ 1 ,y∈G ′ 2 π(x, y) ≤ 0. ( 31
)
Furthermore, as (x 0 y 0 ) is an oriented edge, we know by the definition of W 1 -orientation that there exists (x, y) ∈ C(f 0 , f 1 ) such that x ≤ x 0 ≤ y 0 ≤ y. In particular, x ∈ G ′ 1 , y ∈ G ′ 2 and π(x, y) > 0.

This proves that the inequality (31) is actually strict, which shows the positivity of the family of functions (g t ) on E(G ′ ). The first point of Theorem 2.19 is proven by extending g t to E(G),

setting g t (xy) := 0 if (xy) / ∈ E(G ′ ).
The existence of a family of functions (h t ) such that ∂ ∂t g t = -∇h t is proven by Lemma 2.20. We only need to check that (xy)∈E(G) ∂ ∂t g t (xy) = 0. We are actually going to prove the stronger statement:

(xy)∈E(G) g t (xy) = W 1 (f 0 , f 1 ).
To prove this fact, we consider the function u := (x0y0)∈E(G ′ ) u (x0y0) . The function u satisfies (∂u)(xy) = 1 for every x → y ∈ E(G ′ ). We then have:

t 0 (xy)∈E(G) g s (xy)ds = t 0 (xy)∈E(G) g s (xy)(∂u)(x, y)ds = - t 0 x∈G (∇g s )(x)u(x)dt = t 0 x∈G ∂ ∂s f s (x)u(x)ds = y∈G f t (y)u(y) - x∈G f 0 (x)u(x).
Let π ∈ Π 1 (f 0 , f t ). We know by Proposition 2.18 that if π(x, y) > 0 then x ≤ y. On the other hand, if x ≤ y then there exists a path Differentiating with respect to t shows that the sum (xy)∈E(G) g t (xy) is constant and equal to W 1 (f 0 , f 1 ). To finish the proof of the theorem, we extend (h t ) to T (G) by defining h t (x

x = γ 0 → • • • → γ n = y and we have u(y) -u(x) = (u(γ n ) -u(γ n-1 )) + • • • + (u(γ 1 ) -u(γ 0 )) = n = d(x,
0 x 1 x 2 ) := 0 if (x 0 x 1 x 2 ) / ∈ T (G ′ ).
Actually, Theorem 2.19 can be strengthened in the following way:

Proposition 2.21. In Theorem 2.19, we can replace the assertion ∀(xy) ∈ E(G) , g t (xy) ≥ 0 by ∀(xy) ∈ E(G) , g t (xy) > 0.

Proof. The proof of Theorem 2.19 allowed us to construct, given a spanning tree G ′ ⊂ G, a family of functions (g

G ′ t ) such that g G ′ t (xy) > 0 when (xy) ∈ E(G ′ ) and g G ′ t (xy) = 0 when (xy) / ∈ E(G ′
). But for each edge (x 0 y 0 ) ∈ E(G) there exists a spanning tree G ′ ⊂ G with (x 0 y 0 ) ∈ E(G ′ ). We define a family (g t ) : E(G) → R as the barycenter

∀(xy) ∈ E(G) , g t (xy) := 1 |T | G ′ ∈T g G ′ t (xy),
where T is the (finite) set of spanning trees for G. Then g t > 0 and satisfies the conditions of Theorem 2.19. We finally construct a suitable family (h t ) by defining h

t := 1 T G ′ ∈|T | h G ′ t , where (h G ′ t ) is constructed from (g G ′ t
) as in the proof of Theorem 2.19.

Definition of W 1,+ -geodesics

Having now constructed an orientation of G associated to each couple of finitely supported probability distributions f 0 , f 1 ∈ P(G), we propose a definition of W 1,+ -geodesic inspired by Proposition 2.10: Definition 2.22. Let G be a graph, W 1 -oriented with respect to a couple of finitely supported probability distributions f 0 , f 1 . A family (f t ) is said to be a W 1,+ -geodesic if:

1. The curve (f t ) is a W 1 -geodesic.

2. There exists two families (g t ) and (h t ) defined respectively on E(G) and T (G) such that

∂ ∂t f t = -∇g t , ∂ ∂t g t = -∇h t .
3. For every (xy) ∈ E(G) we have g t (xy) > 0.

4. The triple (f t , g t , h t ) satisfies the Benamou-Brenier equation

∀(x 0 x 1 x 2 ) ∈ T (G) , f t (x 1 )h t (x 0 x 1 x 2 ) = g t (x 0 x 1 )g t (x 1 x 2 ). ( 32
)
Remark 2.23. In the sequel,the assertion "let (f t ) be a W 1,+ -geodesic" means "let ((f t ), (g t ), (h t )) be a triple of families of functions satisfying the conditions of Definition 2.22". This is an abuse because nothing is a priori known about the uniqueness of the families (g t ) and (h t ) associated to a W 1,+ -geodesic.

Remark 2.24. We can check that any contraction of measure on a graph is also a W 1,+ -geodesic: if f 0 = δ o is a Dirac measure, then the set Π 1 (f 0 , f 1 ) has only one element, and it easy to prove that the W 1 -orientation with respect to f 0 , f 1 coincide with the orientation used for contraction of measures. Proposition 2.10 shows that the other points of Definition 2.22 are satisfied by contraction families.

It is possible to state (32) in terms of two different velocity fields:

Proposition 2.25. Let (f t ) t∈[0,1] be a W 1,+ -geodesic on G. We define the velocity fields v +,t and v -,t by v +,t (x 0 x 1 ) := g t (x 0 x 1 ) f t (x 0 ) , v -,t (x 0 x 1 ) := g t (x 0 x 1 ) f t (x 1 ) (33)

and the velocity functions V +,t and V -,t by

V +,t (x 1 ) := x2∈F (x1) v +,t (x 1 x 2 ) , V -,t (x 1 ) := x0∈E(x1) v -,t (x 0 x 1 ). ( 34
)
The following differential equations then hold:

∂ ∂t v +,t (x 0 x 1 ) = -v +,t (x 0 x 1 ) [V +,t (x 1 ) -V +,t (x 0 )] , (35)
∂ ∂t v -,t (x 0 x 1 ) = -v -,t (x 0 x 1 ) [V -,t (x 1 ) -V -,t (x 0 )] . (36)
Proof. We use the definitions of g t and h t and then apply the Benamou-Brenier equation (32) to write:

∂ ∂t v +,t (x 0 x 1 ) = g t (x 0 x 1 ) f t (x 0 ) 2   x1∈F (x0) g t (x 0 x1 ) - x-1∈E(x0) g t (x -1 x 0 )   + 1 f t (x 0 )   - x2∈F (x1) g t (x 0 x 1 )g t (x 1 x 2 ) f t (x 1 ) + x-1∈E(x0) g t (x -1 x 0 )g t (x 0 x 1 ) f t (x 0 )   = v +,t (x 0 x 1 )   x1∈F (x0) g t (x 0 x1 ) f t (x 0 ) - x2∈F (x1) g t (x 1 x 2 ) f t (x 1 )   = v +,t (x 0 x 1 ) [V +,t (x 0 ) -V +,t (x 1 )] .
The second formula is proven by similar methods.

We now give some heuristic arguments explaining the terminology 'W 1,+ -geodesic'. Let us consider the minimization problem described by equation (6) of Theorem 1.1, when the paramater p = 1 + ε is close to 1. We use the expansion a 1+ε = a exp(ε log(a)) = a + ε a log(a) + O(ε 2 ), valid for a > 0, to write

M 1 0 |v t (x)| p dµ t (x)dt = M 1 0 |v t (x)|dµ t (x)dt + ε M 1 0 |v t (x)| log(|v t (x)|)dµ t (x)dt + O(ε 2 ).
The integral M 1 0 |v t (x)|dµ t (x)dt is exactly equation (6) for p = 1. We thus know, by Theorem 1.1 that the minimizers of this integral over the set of families (f t ) of probability measures with f 0 , f 1 prescribed and ∂ ∂t f t (x) + ∇ • (v t (x)f t (x)) = 0 are exaclty the W 1 -geodesics joining f 0 to f 1 . This suggests the following: Definition 2.26. We say that a curve (f t ) of probability measures on a Riemannian manifold M is a W 1,+ -geodesic on M if it is solution to the minimization problem

inf M 1 0 |v t (x)| log(|v t (x)|)dµ t (x)dt,
where the infimum is taken over the set of all W 1 -geodesics between f 0 and f 1 and where the velocity field (v t ) is defined by the continuity equation

∂ ∂t f t (x) + ∇ • (v t (x)f t (x)) = 0.
The formal optimality condition on (v t ) obtained by applying Euler-Lagrange equations is the same as for W p -geodesics:

∂ ∂t v t (x) = -v t (x)∇v t (x).
The next proposition shows that W 1,+ -geodesics on a graph can be related to a minimization problem similar to the continuous one described in Definition 2.26: Proposition 2.27. Let G be a W 1 -orientated with respect to f 0 , f 1 finitely supported. We consider the problem

inf I + (f, g) := inf 1 0 x→y v +,t (xy) log(v +,t (xy))f t (x), ( 37
)
where the infimum is taken over the set of W 1 -geodesics (f t ) between f 0 and f 1 such that the velocity v +,t (xy) is defined by equation (33) from a positive family (g t ) with ∂ ∂t f t (x) = -∇g t (x). We suppose that there exists a W 1,+ -geodesic (f t ) joining f 0 to f 1 . Then (f t ) is a critical point for I + in the following sense: if (u t ) is a family of functions defined on E(G) satisfying the boundary conditions u 0 (xy) = u 1 (xy) = 0, then

I + f + η∇u, g -η ∂u ∂t = I + (f, g) + O(η 2 ). ( 38
)
Remark.Recall that, given a W 1 -geodesic (f t ), the continuity equation ∂ ∂t f t (x) = -∇g t (x) may be solved by a family (g t ) which is not necessarily always positive. We restrict ourselves to the families of positive (g t ), which always exist by Proposition 2.21, in order to write |v +,t (xy)| = v +,t (xy).

Proof of Proposition 2.27. When η is small, we have the expansion

I + f + η∇u, g -η ∂u ∂t -I + (f, g) = -η 1 0 x→y ∂ ∂t u t (x, y) (1 + log(v +,t (xy))) + (∇u t )(x)v t (xy)dt + O(η 2 ).
On the other hand, we use the boundary conditions u 0 = u 1 = 0 to write:

1 0 x→y ∂ ∂t u t (x, y) (1 + log(v +,t (xy))) dt = - 1 0 x→y u t (x, y) ∂ ∂t (1 + log(v +,t (xy))) dt = - 1 0 x→y u t (xy) 1 v t (xy) ∂ ∂t v t (xy)dt = 1 0 x→y u t (xy)[V +,t (y) -V +,t (x)]dt = - 1 0 x∈G (∇u t )(x)V +,t (x)dt = 1 0 x→y (∇u t )(x)v t (xy)dt, which proves that I + f + η∇u, g -η ∂u ∂t = I + (f, g) + O(η 2 ).
Remark. Similarly, it can be proven that a W 1,+ -geodesic is also critical for the functional inf

I -(f, g) := inf 1 0 x→y v -,t (xy) log(v -,t (xy))f t (x). ( 39
)
3 W 1,+ -geodesics as mixtures of binomial distributions W 1,+ -geodesics have been constructed as generalizations of contraction families, which have been defined as mixture of binomial distributions. In this section, we fix a W 1,+ -geodesic (f t ) on G, joining two finitely supported probability distributions f 0 , f 1 ∈ P(G). It will always be assumed that the graph G is W 1 -oriented with respect to f 0 , f 1 and that every path is an oriented path, thus a geodesic, by Theorem 2.17.

The main purpose of this section is to prove Theorem 3.18: (f t ) can also be expressed as a mixture of binomial measures, with respect to a coupling π ∈ Π(f 0 , f 1 ) solution to a certain minimization problem. The key ingredients to the proof of this theorem are the study of the behaviour of (f t ) along particular geodesics of G, called extremal and semi-extremal geodesics, and the construction of two sub-Markov kernels K, K ⋆ on G associated to (f t ).

Extremal geodesics

Recall that we write x 2 ∈ F (x 1 ) and

x 1 ∈ E(x 2 ) if x 1 ≤ x 2 and d(x 1 , x 2 ) = 1 or equivalently if (x 1 x 2 ) is an oriented edge of G.
If γ is a geodesic of G, it will be sometimes convenient to use the notation γ i := γ(i).

Definition 3.1. Let γ be a geodesic on G.

• If L(γ) = n ≥ 2, we associate to γ the positive function

C γ (t) := g t (γ 0 γ 1 ) • • • g t (γ n-1 γ n ) f t (γ 1 ) • • • f t (γ n-1 ) . ( 40
)
• If L(γ) = 1, we define C γ (t) := g t (γ 0 γ 1 ).

• If L(γ) = 0, we define C γ (t) := f t (γ 0 ). Proposition 3.2. The function C γ (t) satisfy ∂ ∂t C γ (t) = x0∈E(γ0) C x0∪γ (t) - x2∈F (γn) C γ∪x2 (t), (41)
where x 0 ∪ γ (resp. γ n ∪ x 2 ) is the geodesic x 0 , γ 0 , . . . γ n (resp. γ 0 , . . . γ n , x 2 ).

Proof. If L(γ) = 0, equation ( 41) is equivalent to ∂ ∂t f t (γ 0 ) = -(∇g t )(x 0 ), which is true by the definition of (g t ). If L(γ) ≥ 1, we notice that

C γ (t) = f t (γ 0 )v +,t (γ 0 γ 1 ) • • • v +,t (γ n-1 γ n ). ( 42
)
Proposition 2.25 gives:

1 C γ (t) ∂ ∂t C γ (t) = 1 f t (γ 0 ) ∂ ∂t f t (γ 0 ) + n-1 i=0 1 v +,t (γ i γ i+1 ) ∂ ∂t v +,t (γ i γ i+1 ) = (-V +,t (γ 0 ) + V -,t (γ 0 )) - n-1 i=0 [V +,t (γ i+1 ) -V +,t (γ i )] = -V +,t (γ n + V -,t (γ 0 ) = - x2∈F (γn) v +,t (γ n x 2 ) + x0∈E(γ0) v -,t (x 0 γ).
Multiplying by C γ (t) and applying equation (42) leads to the result.

Equation (41) takes a simpler form in the case where the set E(e 0 (γ)) (or F (e 1 (γ)), or both) is empty. This motivates the following: Definition 3.3. We define the particular subsets of vertices of G:

• The set of initial vertices A ⊂ G contains every x 1 ∈ G such that E(x 1 ) is empty.

• The set of final vertices B ⊂ G contains every x 1 ∈ G such that F (x 1 ) is empty.

We also define the particular subsets of geodesics f G:

• The set EΓ of extremal geodesics contains every γ ∈ Γ(G) with e 0 (γ) ∈ A, e 1 (γ) ∈ B.

• The set SEΓ 1,x contains every γ ∈ Γ(G) with e 0 (γ) ∈ A, e 1 (γ) = x.

• The set SEΓ 1,x contains every γ ∈ Γ(G) with e 0 (γ) = x, e 1 (γ) ∈ B.

If e 0 (γ) ∈ A or e 1 (γ) ∈ B, the geodesic γ is said to be semi-extremal.

Remark 3.4. The sets A and B are both non empty. If we suppose for instance that B is empty, then we can construct an infinite sequence (x n ) n≥0 in G such that x n+1 ∈ F (x n ). But, f 0 and f 1 being finitely supported and G being locally finite, the set of oriented edges of G is finite so x p = x q for a couple of indices q > p. This means that there exists a non-trivial oriented path γ joining x p to itself, which is a contradiction because γ is a geodesic of G by Proposition 2.17.

An immediate corollary of Proposition 3.2 is the following: Proposition 3.5. Let γ be a geodesic of G.

• If γ ∈ EΓ, then C γ (t) = C γ is a constant function of t. • If γ ∈ SEΓ 1,x then C γ (t) is polynomial in t and deg(C γ (t)) ≤ sup{L(γ) : γ ∈ SEΓ 2,x }. • If γ ∈ SEΓ 2,x then C γ (t) is polynomial in t and deg(C γ (t)) ≤ sup{L(γ) : γ ∈ SEΓ 1,x }.
Proof. If γ ∈ EΓ, then the sets E(e 0 (γ)) and F (e 1 (γ)) are empty, which by Proposition 3.2 shows that C γ is a constant function of t. We prove the second point by induction on m = m(γ) := sup{L(γ) : γ ∈ SEΓ 2,x }, which only depends on the endpoint e 1 (γ) = x . If m = 0 then γ ∈ EΓ and this case has been considered in the first point. We now fix a geodesic γ ∈ SEΓ 1,x such that m(γ) ≥ 1. We apply Proposition 3.2 and use the fact that e 0 (γ) ∈ A to write:

∂ ∂t C γ (t) = - x2∈F (x) C γ∪x2 (t). (43)
It is easily shown that, for z ∈ F (x), m(γ ∪ {z}) = m(γ) -1, which proves by induction on m that C γ (t) is polynomial in t of degree less than m(γ).

Sub-Markov kernels associated to a W 1,+ -geodesic

The fact that the function C γ is constant and positive on extremal geodesics allows us to introduce a useful function on ordered subsets of G:

Definition 3.6. Given an ordered p-uple z 1 ≤ z 2 ≤ . . . z p of vertices of G, we define

m(z 1 , . . . z p ) := γ∈E(z1,...zp) C γ , (44)
where E(z 1 , . . . z p ) ⊂ EΓ is defined by:

γ ∈ E(z 1 , . . . z p ) ⇐⇒ ∃ k 1 ≤ • • • ≤ k p , γ(k i ) = z i . ( 45
)
If γ is a geodesic of G, we denote by m(γ) the number m(e 0 (γ(0)),

• • • e 1 (γ)).
Proposition 3.7. For any family of vertices

x 0 ≤ • • • ≤ x m we have m(x 0 , . . . x m ) = m(x 0 , x 1 ) • • • m(x m-1, x m ) m(x 1 ) • • • m(x m-1 ) . Proof. Let γ ∈ E(x 0 , • • • x m ) and γ (i) ∈ E(x i ) for i = 1, . . . m -1.
To these geodesics we associate the geodesics γ(0) • • • γ(m-1) such that, for i = 1, . . . m -1, γ(i) is constructed by concatenating the begining of γ (i) , a mid-part of γ and the end of γ (i+1) in the following way:

γ(i) : e 0 (γ (i) ) → • • • x i → • • • x i+1 → • • • e 1 (γ (i+1) ). (46)
The geodesic γ(0) is constructed by concatenating the begining of γ and the end of γ (1) and γ(m-1) is contructed by concatenating the begining of γ (m-1) and the end of γ. It is clear that

γ (i) ∈ E(x i , x i+1 ). Moreover, the application (γ, γ (1) , • • • γ (m-1) ) → (γ (0) , • • • γ(m-1) ) is easily proven to be a bijection between E(x 0 , . . . x m ) × E(x 1 ) × • • • E(x m-1 ) and E(x 0 , x 1 ) × • • • E(x m-1 , x m ).
Writing that both sets have same cardinality gives the result.

Definition 3.8. The sub-Markov kernels K and K * associated to a W 1,+ -geodesic (f t ) on G are defined by

∀x 1 ∈ G , ∀x 0 ∈ E(x 1 ) , K(x 1 , x 0 ) := m(x 1 , x 0 ) m(x 1 ) , ( 47
)
∀x 0 ∈ G , ∀x 1 ∈ F (x 0 ) , K * (x 0 , x 1 ) := m(x 0 , x 1 ) m(x 0 ) . ( 48
)
We also define Kf (x 1 ) := x0 K(x 1 , x 0 )f (x 0 ) and K * f (x 0 ) := x1 K * (x 0 , x 1 )f (x 1 ).

Proposition 3.9. The kernels K and K * satisfy the following:

• If x 1 / ∈ A then x0∈E(x1) K(x 1 , x 0 ) = 1. • If x 0 / ∈ B then x1∈F (x0) K * (x 0 , x 1 ) = 1.
• The operators K and K * are adjoint for the scalar product < f, g >:= x∈G f (x)g(x)m(x).

• The iterated kernel K n is supported on the set of couples (x n , x 0 ) such that x 0 ∈ E n (x n ), i.e. such that x 0 ≤ x n and d(x n , x 0 ) = n. For such a couple we have

K n (x n , x 0 ) = m(x n , x 0 ) m(x n ) .
• Similarly, for x n ∈ F n (x 0 ), i.e. for x n ≤ x 0 such that d(x n , x 0 ) = n we have

(K * ) n (x 0 , x n ) = m(x 0 , x n ) m(x 0
) .

• The operators K and K * are nilpotent.

Proof. The first point comes from the fact that, if x 0 / ∈ B, there exists a bijection between the set E(x 0 ) and the disjoint union x1∈F (x0) E(x 0 , x 1 ). The second point is proven similarly. The third point is proven by noticing that both scalar products < Kf, g > and < f, K * g > are equal to x0→x1 m(x 0 , x 1 )f (x 0 )g(x 1 ).

To prove the fourth point, we write the general formula for the iterated kernel for some n ≥ 2:

∀x 0 , x n ∈ G , K n (x n , x 0 ) := xn-1,...x1 K(x n , x n-1 ) • • • K(x 1 , x 0 ).
The product K(x n , x n-1 ) • • • K(x 1 , x 0 ) is non-zero if and only if x 0 → • • • → x n , i.e. if (x 0 , . . . , x n ) is a geodesic. This proves that K n (x n , x 0 ) > 0 implies that x 0 ∈ E n (x n ). Moreover we have:

K n (x n , x 0 ) = γ∈Γx 0 ,xn m(x n , γ n-1 ) m(x n ) • • • m(γ 1 , x 0 ) m(γ 1 ) = m(x n , x 0 ) m(x n )
by Proposition 3.7. The fifth point is proven similarly. The nilpotency of K and K * comes from the fact that (G, →) has a finite diameter: if n > Diam(G) then K n = 0 and (K * ) n = 0.

Remark 3.10. The first point of Proposition 3.9 shows that K can easily be transformed into a Markov kernel: it suffices to add a vertex ω (often called "cemetery") to G and oriented edges ω → x for every x ∈ A. The sub-Markov kernel K is extended into a Markov kernel on G ∪ ω by defining K(ω, ω) = 1 and K(ω, x) = 1 for every x ∈ A. The kernel K * can be treated similarly, by considering the oriented edges (x, ω) for x ∈ B.

Polynomial structure of W 1,+ -geodesics

In this paragraph we use properties of the functions C γ (t) and of the sub-Markovian kernels K, K ⋆ to give expression of (f t ) as a mixture of binomial distributions on geodesics of G.

A direct calculation proves the following fundamental result:

Proposition 3.11. Let x ∈ G be a vertex and γ, γ be two geodesics on G with γ ∈ SEΓ 1,x and γ ∈ SEΓ 2,x . Then

f t (x) = C γ (t)C γ (t) C γ∪γ , (49)
where γ ∪ γ is the concatenation of γ and γ.

Remark 3.12. A first consequence of Propositions 3.5 and 3.11 is the fact that, for any x ∈ G, f t (x) is a polynomial function of t such that deg(f t (x)) ≤ Diam(G).

We also use Proposition 3.11 to show the following:

Proposition 3.13. For x ∈ G, we consider two semi-extremal curves γ (1) , γ (2) ∈ SEΓ 1,x . The quotient

C γ (1) (t)
C γ (2) (t) does not depend on t and is equal to m(γ (1) ) m(γ (2) ) . Furthemore, we have

C γ (1) (t) = m(γ (1) ) m(x) γ∈SEΓ1,x(G) C γ (t). ( 50
)
Proof. Let γ be in SEΓ 2,x (G). Then Proposition (3.11) shows that

C γ (1) (t) C γ (2) (t) = C(γ (1) ∪ γ) C(γ (2) ∪ γ) .
We use the fact that this quotient does not depend on γ to write

C γ (1) (t) C γ (2) (t) = γ∈SEΓ2,x(G) C(γ (1) ∪ γ) γ∈SEΓ2,x(G) C(γ (2) ∪ γ) = m(γ (1) ) m(γ (2)
) .

The second point is proven by writing

γ∈SEΓ1,x(G) C γ (t) C γ (1) (t) = γ∈SEΓ1,x(G) m(γ) m(γ (1) ) = m(x) m(γ (1) ) . (51)
We now introduce two families of functions which play the same role as in the case of contraction of measures: Definition 3.14. We define the functions P t (x) and Q t (x) by

P t (x) := 1 m(x) γ (2) ∈SEΓ2,x C t (γ (2) ) , Q t (x) := 1 m(x) γ (1) ∈SEΓ1,x C t (γ (1) ). ( 52
)
Proposition 3.15. The functions f t , g t and h t are related to P t , Q t and m by 1.

f t (x 0 ) = m(x 0 )P t (x 0 )Q t (x 0 ), 2. g t (x 0 x 1 ) = m(x 0 x 1 )P t (x 0 )Q t (x 1 ), 3. h t (x 0 x 1 x 2 ) = m(x 0 x 1 x 2 )P t (x 0 )Q t (x 2 ).
Proof. To prove the first point, we notice that the concatenation map γ (1) , γ (2) → γ (1) ∪ γ (2) is a bijection between the sets SEΓ 1,x0 × SEΓ 2,x0 and E(x 0 ). We then use Proposition 3.11 to write:

(γ (1) ,γ (2) )∈SEΓ1,x 0 × SEΓ2,x 0 C γ (1) (t)C γ (2) (t) = γ∈E(x0) C γ f t (x 0 ) = f t (x 0 )m(x 0 ).
To prove the second point, given of vertices x 0 → x 1 we consider the bijection between the sets SEΓ 1,x0 × SEΓ 2,x1 and E(x 0 , x 1 ) given by the concatenation γ (1) , γ (2) → γ (1) ∪ γ (2) . Moreover, if γ (1) ∈ SEΓ 1,x0 and γ (2) ∈ SEΓ 2,x1 have length L 1 ≥ 2 and L 2 ≥ 2 we have:

C γ (1) (t)C γ (2) (t) = g(γ (1) 0 γ
(1)

1 ) • • • g(γ (1) L1-1 x 0 ) f (γ (1) 1 ) • • • f (γ (1) L1-1 ) g(x 1 γ (2) 1 ) • • • g(γ (2) L2-1 γ (2) L2 ) f (γ (2) 1 ) • • • f (γ (2) L2-1 ) = C γ (1) ∪γ (2) (t) f t (x 0 )f t (x 1 ) g t (x 0 x 1 ) .
Summing over all γ (1) , γ (2) gives 1 m(x 0 ) P t (x 1 ) 1 m(x 1 ) Q t (x 0 ) = m(x 0 , x 1 ) f t (x 0 )f t (x 1 ) g t (x 0 x 1 ) .

Replacing f t (x 0 ) and f t (x 1 ) by their expressions in terms of P t , Q t proves the second point. The third point is simply proven by using the Benamou-Brenier equation:

h t (x 0 x 1 x 2 ) = g t (x 0 x 1 )g t (x 1 x 2 ) f t (x 1 ) = m(x 0 , x 1 )m(x 1 , x 2 ) m(x 1 ) P t (x 0 )Q t (x 2 ) = m(x 0 , x 1 , x 2 )P t (x 0 )Q t (x 2 ).
Proposition 3.16. The functions P t and Q t satisfy the differential equations

∂ ∂t P t (x) = KP t (x) , ∂ ∂t Q t (x) = -K * Q t (x). (53)
Proof: When applied to semi-extremal geodesics, Proposition 3.2 takes a simpler form. More precisely, if γ (2) ∈ SEΓ 2,x0 , we have

∂ ∂t C γ (2) (t) = x-1∈E(x0) C x-1∪γ (2) (t). (54)
On the other hand, by Proposition 3.13, we have:

γ (2) ∈SEΓ2,x 0 C t (x -1 ∪ γ (2) ) = γ2∈SEΓ2,x 0 m(x -1 ∪ γ (2) ) m(x -1 ) γ(2) ∈SEΓ2,x -1 C γ(2) (t) = m(x -1 , x 0 ) m(x -1 ) P t (x -1 ).
Summing this last equation over x -1 ∈ E(x 0 ) gives the result. The differential equation for Q t (x 0 ) is proven similarly.

Proposition 3.17. There exist two functions a, b : G → R such that

P t (z) = 1 m(z) x≤z m(x, z)a(x) t d(x,z) d(x, z)! , Q t (z) = 1 m(z) y≥z m(z, y)b(y) (1 -t) d(z,y) d(z, y)! . (55)
Proof. For x ∈ G, let a(x) := P 0 (x) be the constant term of the polynomial t → P t (x). Using Proposition 3.16 and Proposition 3.9, we have

P t (z) = [exp(tK)P 0 ](x) = [exp(tK)a](z) = l≥0 t l l! (K l a)(z) = l≥0 x∈E l (z) t l l! m(x, z) m(z) a(x) = 1 m(z) x≤z m(x, z)a(x) t d(x,z) d(x, z)! .
The proof of the second point is quite similar: define Qt (z) := Q 1-t (z) and b(y) := Q0 (y) = Q 1 (y).

As we have ∂ Qt(z) ∂t = (K * Qt )(z), we use again Proposition 3.9 to conlude.

We are now ready to write the W 1,+ -geodesic (f t ) as a mixture of binomial distributions:

Theorem 3.18. For any couple of vertices x ≤ y ∈ G we define the binomial probability distribution on bin (x,y),t on G, associated to the application m, supported on the set of vertices z ∈ G such that x ≤ z ≤ y, by bin (x,y),t (z) := m(x, z, y) m(x, y)

d(x, y)! d(x, z)!d(z, y)! t d(x,z) (1 -t) d(x,y) . (56)
The W 1,+ -geodesic (f t ) t∈[0,1] is a mixture of such binomial distributions:

f t (•) = x≤y m(x, y) d(x, y)! a(x)b(y) bin (x,y),t (•). ( 57
)
Proof. The theorem follows from the calculation:

f t (z) = m(z)P t (z)Q t (z) = 1 m(z) x,y:x≤z≤y m(x, z)a(x) t d(x,z) d(x, z)! m(z, y)b(y) (1 -t) d(z,y) d(z, y)! = x,y:x≤z≤y m(x, z)m(z, y) m(z) m(x, y) d(x, y)! a(x)b(y) bin (x,y),t (z),
and from the fact that m(x,z)m(z,y) m(z)

= m(x, z, y) (by Proposition 3.7).

Existence of W 1,+ -geodesics

In the previous section, we showed that any W 1,+ -geodesic (f t ) can be expressed a mixture of binomial distributions with respect to a certain coupling between f 0 and f 1 . We now turn to the question of the existence of a W 1,+ -geodesic (f t ) joining two fixed probability distributions f 0 , f 1 . Through this section, we fix such a couple and endow the underlying graph G with the W 1 -orientation associated to f 0 , f 1 .

Definition 4.1. Let m : E(G) → R * + be satisfying ∇m(x) = 0 for every x / ∈ A, B. Let p ≥ 0 be an integer. We extend m as a function on ordered (p + 1) -uples in G by defining:

• If p = 0, m(x) := y∈F (x) m(x, y). • If p ≥ 2 and γ : {0, . . . p} → G is a geodesic, then m(γ) := m(γ 0 , . . . γ p ) := p-1 i=0 m(x i , x i+1 ) p-1 j=1 m(x j ) (58) • If p ≥ 2 and x 0 ≤ • • • ≤ x p then m(x 0 , . . . x p ) = 1 p-1 j=1 m(x j ) p-1 i=1 γ∈Γx i ,x i+1 m(γ).
Remark 4.2. The assumption ∇m(x) = 0 for x / ∈ A, B allows us to write

y∈F (x) m(x, y) = m(x) = y ′ ∈E(x)
m(y ′ , x).

Remark 4.3. An equivalent way to define the extension of m is to define m(γ) on extremal geodesics using equation (58) and to extend it to general (p + 1)-uples as in Definition 3.6, the quantity m(γ) playing the role of C γ .

Theorem 4.4. A W 1 -geodesic (f t ) is a W 1,+ -geodesic if and only if there exists:

• A function m : E(G) → R * + satisfying ∇m(x) = 0 for x / ∈ A, B, extended to ordered families of G.

• A couple of non-negative functions a, b : G → R + , such that equations (56) and (57) hold.

Proof. The "only if" part of Theorem 4.4 is exactly Theorem 3.18. Indeed, the restriction to E(G) of the function m constructed from a W 1,+ -geodesic (f t ) satisfies ∇m = 0 outside of A ∪ B, and using Definition 4.1 to extend this restriction to ordered families allows us to recover the original m. Moreover, the functions a and b introduced in Proposition 3.17 are non-negative: a(x) is the constant term of the polynomial P t (x), which is non-negative for every t ∈ [0, 1], and the same goes for b(x).

Conversely, let (f t ) be a curve satisfying the assumptions of Theorem 4.4. We define the polynomial functions

P t (z) := 1 m(z) x≤z m(x, z)a(x) t d(x,z) d(x, z)! , Q t (z) := 1 m(z) y≥z m(z, y)b(y) t d(z,y) d(z, y)! .
Direct calculations show that f t (z) = m(z)P t (z)Q 1-t (z). Moreover, using the definition of m(x, z) and m(z, y), one can prove easily that P t and Q t satisfy the differential equations

∂ ∂t P t (z) = z0∈E(z) m(z 0 , z) m(z 0 ) P t (z 0 ) , ∂ ∂t Q t (z) = z1∈F (z)
m(z, z 1 ) m(z 1 ) Q t (z 1 ).

This allows us to write ∂ ∂t f t (z) = -∇g t (z) where we define g t (x 0 x 1 ) := m(x 0 , x 1 )P t (x 0 )Q 1-t (x 1 ).

Similarly, defining h t (x 0 x 1 x 2 ) := m(x 0 , x 1 , 2 )P t (x 0 )Q 1-t (x 2 ) we have ∂ ∂t g t (x 0 x 1 ) = -∇h t (x 0 x 1 ). The positivity of P t and Q 1-t implies the positivity of g t (x 0 x 1 ). Moreover, the formula m(x 1 )m(x 0 , x 1 , x 2 ) = m(x 0 , x 1 )m(x 1 , x 2 ) implies f t (x 1 )h t (x 0 x 1 x 2 ) = g t (x 0 x 1 )g t (x 1 x 2 ), which shows that (f t ) is a W 1,+ -geodesic.

The task of finding a W 1,+ -geodesic joining f 0 to f 1 is simplified by Theorem 4.4 because it turns it into the static problem of finding a coupling π between f 0 and f 1 such that π(x, y) := This method can be used to prove the existence of W 1,+ -geodesics with prescribed initial and final distributions: Theorem 4.5. Let f 0 , f 1 ∈ P(G) be finitely supported. Then there exists a W 1,+ -geodesic between f 0 and f 1 .

The Hessian of J is thus a diagonal matrix with positive coefficients The set Π 1 (f 0 , f 1 ) being compact, the infimum of J on Π 1 (f 0 , f 1 ) is attained for some coupling π. As J is striclty convex and Π 1 (f 0 , f 1 ) is a convex subset of R D , we know that π is unique and that we have either π ∈ ∂Π 1 (f 0 , f 1 ) or π ∈ Π 1 (f 0 , f 1 ) • and in this second case π is a critical point for the restriction to Π 1 (f 0 , f 1 ) of the application J.

Let us prove that π ∈ Π 1 (f 0 , f 1 ) • : we consider a segment π t := (1 -t)π 0 + tπ 1 , where π 0 ∈ ∂Π 1 (f 0 , f 1 ) and π 1 ∈ Π 1 (f 0 , f 1 ) • . Each π t is in Π 1 (f 0 , f 1 ), by convexity. The function J(t) := J(π t ) is continuous on [0, 1], smooth on ]0, 1[ and we have:

J ′ (t) = (x,y)∈D
(π 1 (x, y) -π 0 (x, y)) log π t (x, y) d(x, y)! m(x, y) .

As π 0 ∈ ∂Π + , there exists (x 0 , y 0 ) ∈ D such that π 0 (x 0 , y 0 ) = 0 and we have lim t→0 (π 1 (x 0 , y 0 ) -π 0 (x 0 , y 0 )) log π t (x 0 , y 0 ) d(x 0 , y 0 )! m(x 0 , y 0 ) = -∞, so we have lim t→0 J ′ (t) = -∞. The infimum of J on Π 1 (f 0 , f 1 ) is thus not attained on ∂Π 1 (f 0 , f 1 ).

We have proven the existence of a unique critical point π ∈ Π(f 0 , f 1 ) • for the restriction to Π 1 (f 0 , f 1 ) of J. As Π 1 (f 0 , f 1 ) is a subset of an affine space directed by a vector subspace V ⊥ , we know that grad π J ∈ V.

In other terms, grad π0 (J) =

for a couple of functions A, B : G → R. Due to the particular form taken by j 0,x and j 1,y , Equation (61) can be rewritten in a simple way:

∀(x, y) ∈ D , grad π0 (J)(x, y) = A(x) + B(y).

But equation (60) gives an explixcit formula for grad π0 (J)(x, y), which allows us to write, for (x, y) ∈ D: Remark 4.6. The particular form taken by W 1,+ -geodesics (see Equation (57)) and the minimisation problems associated by the functionals (59) and (37), are reminiscent of the theory of Entropic Interpolations, constructed in a recent series of articles by Léonard. A survey of the main results of this theory is found in [START_REF] Léonard | A survey of the Schrdinger problem and some of its connections with optimal transport[END_REF]. A construction of entropic interpolations and a discussion of the cases where they can be described as mixtures of binomials is found in [START_REF] Léonard | Lazy random walks and optimal transport on graphs[END_REF]. Another paper, see [START_REF] Léonard | On the convexity of the entropy along entropic interpolations[END_REF], addresses the question of the convexity of entropy along such interpolations.

A major difference between these two kinds of interpolations lies in their construction: in order to define an entropic interpolation on a graph G, one requires an underlying Markov chain to which is canonically associated a positive measure R 01 on the set of couples of vertices x, y ∈ G. On the other hand, the definition of a W 1,+ -interpolation does not require an underlying Markov chain. It only relies on the "metric-measure" properties of the graph G, endowed with its counting measure. However, to each W 1,+ -geodesic is associated a function m on the ordered subsets of G, which is used to construct sub-Markov kernels.

A complete understanding of the links between entropic interpolations and W 1,+ -geodesics, and more especially between the measure R 01 of entropic interpolations and the function m of W 1,+geodesics, is still under investigation.

  y), so we have t 0 (xy)∈E(G) g s (xy)ds = x≤y π(x, y)d(x, y) = W 1 (f 0 , f t ) = tW 1 (f 0 , f 1 ).

  ,y)! a(x)b(y)1 x≤y for a couple of functions a(x), b(y) defined on G and for a function m constructed in Definition 4.1.

  where the variables are denoted by π(x, y), for x ≤ y. The function J is clearly continuous on R D + and smooth on R * + D . Moreover, we have:∂J ∂π(x, y)= log π(x, y) c(x, y) .

1

  π(x,y) (x,y)∈D , so J is strictly convex on R * + D .

  x∈G A(x)j 0,x + y∈G B(y)j 1,y

π

  (x, y) c(x, y) = exp grad π0 (J)(x, y) = exp(A(x) + B(y)) = a(x)b(y), where a(x) := exp(A(x)) and b(y) := exp(B(y)). Theorem 4.4 gives the a W 1,+ -geodesic (f t ) between f 0 and f 1 constructed from the function m and the coupling π

Proof. Let m : E(G) → R * + be any positive function with ∇m(x) = 0 for every x / ∈ A, B, and extended to ordered families of G. We set c(x, y) := m(x,y) d(x,y)! . By Theorem 4.4, it suffices to prove the existence of a coupling π ∈ Π 1 (f 0 , f 1 ) such that π(x, y) = c(x, y)a(x)b(y)1 x≤y for a couple of positive a, b : G → R.

We will adopt the following point of view on the set Π 1 (f 0 , f 1 ):

In the space R D with the usual sclar product, we consider the particular families of vectors (j 0,x ) x∈G and (j 1,y ) y∈G defined by

If for every (x, y) ∈ D we have x 0 = x then we set j 0,x0 = 0.

In particular, we have

In other words, Π 1 (f 0 , f 1 ) is seen as the intersection of the "quadrant" R D + with an affine subspace of R D directed by the vector subspace V ⊥ , where V is the vector space generated by the families (j 0,x ) x∈G and (j 1,y ) y∈G .

Depending on the dimension of Π 1 (f 0 , f 1 ) as a subset of an affine subspace of R D , we will consider two cases:

1. The dimension of Π 1 (f 0 , f 1 ) is zero. In this case, the vector space V is R D . In particular, the vector l ∈ R D , with components l(x, y) := π(x,y) c(x,y) for every couple x ≤ y ∈ D, can be written under the form

for a unique couple of functions A, B defined on G. Considering the exponential of each side proves that π can be written under the form π(x, y) := c(x, y)a(x)b(y)1 x≤y with a(x) := exp(A(x)) and b(y) := exp(B(y)).

2. The dimension of Π 1 (f 0 , f 1 ) is positive. In this case we will use the fact that the interior Π 1 (f 0 , f 1 ) is non-empty and equal to the set of fully supported W 1 -optimal couplings:

The boundary of Π 1 (f 0 , f 1 ) is thus described by: ∂Π 1 (f 0 , f 1 ) = {π ∈ Π 1 (f 0 , f 1 ) : ∃(x, y) ∈ D, π(x, y) = 0}.

We consider the mapping J : R D + → R defined by J(π) := (x,y)∈D π(x, y) log π(x, y) c(x, y) -π(x, y),