Sergio Caracciolo

Matteo P D'achille

Vittorio Erba

Andrea Sportiello

The Dyck bound in the concave 1-dimensional random assignment model

We consider models of assignment for random N blue points and N red points on an interval of length 2N , in which the cost for connecting a blue point in x to a red point in y is the concave function |x -y| p , for 0 < p < 1. Contrarily to the convex case p > 1, where the optimal matching is trivially determined, here the optimization is non-trivial.

The purpose of this paper is to introduce a special configuration, that we call the Dyck matching, and to study its statistical properties. We compute exactly the average cost, in the asymptotic limit of large N , together with the first subleading correction. The scaling is remarkable: it is of order N for p < 1 2 , order N ln N for p = 1 2 , and N 1 2 +p for p > 1 2 , and it is universal for a wide class of models. We conjecture that the average cost of the Dyck matching has the same scaling in N as the cost of the optimal matching, and we produce numerical data in support of this conjecture. We hope to produce a proof of this claim in future work.

1 The problem

Models of Random Assignment

In this paper we study the statistical properties of the Euclidean random assignment problem, in the case in which the points are confined to a one-dimensional interval, and the cost is a concave increasing function of their distance.

The assignment problem is a combinatorial optimization problem, a special case of the matching problem when the underlying graph is bipartite. As for any combinatorial optimization problem, each realisation of the problem is described by an instance J, and the goal is to find, within some space of configurations, the particular one that minimises the given cost function. In the assignment problem, the instance J is a real-positive N × N matrix, encoding the costs of each possible pairing among N blue and N red points (J ij is the cost of pairing the i-th blue point with the j-th red point), the space of configurations is the set of permutations of N objects, π ∈ S N (describing a complete assignment of blue and red points), and the cost function is

H J (π) = N i=1 J iπ(i) .
A random assignment problem is the datum of a probability measure µ N (J) on the possible instances of the problem. The interest is in the determination of the statistical properties of this problem w.r.t. the measure under analysis, and in particular the statistical properties of the optimal configuration. The problem can be formulated as the zero-temperature limit of the statistical mechanics properties of a disordered system, where the disorder is the instance J, the dynamical variables are encoded by π, and the Hamiltonian is the cost function H J (π).

The case of random assignment problem in which the entries J ij are random i.i.d. variables, presented already in [START_REF] Orland | Mean-field theory for optimization problems[END_REF], has been solved at first, in a seminal paper by Parisi and Mézard [START_REF] Mézard | Replicas and optimization[END_REF], through the replica trick and afterwards by the Cavity Equations [START_REF] Mézard | Mean-field equations for the matching and the travelling salesman problems[END_REF] (see also [START_REF] Caracciolo | Finite size corrections in the random assignment problem[END_REF] for a recent generalization of those results also at finite system size). The Parisi-Mézard solution also leads to the striking prediction that, calling π opt (J) the optimal matching for the instance J and H opt (J) = H J (π opt (J)) its optimal cost, the average over all instances of H opt , for N large, tends to π 2 6 . This problem is simpler than a spin glass, as the determination of the optimal configuration is feasible in polynomial time (for example, through the celebrated Hungarian Algorithm [START_REF] Lovász | Matching Theory[END_REF]), however it remains non-trivial, and the thermodynamics is replica-symmetric, although the stability of the RS phase becomes marginal in the zero-temperature limit (as evinced, again, via the analysis of the cavity equations). A number of distinct other approaches to the model, and the solution of the Parisi conjecture [START_REF] Parisi | A conjecture on random bipartite matching[END_REF] for the behaviour at finite size in the case of an exponential distribution of the random costs, which is the simplest case of a more general conjecture by Coppersmith and Sorkin [START_REF] Coppersmith | Constructive bounds and exact expectations for the random assignment problem[END_REF], have appeared later on [START_REF] Aldous | The ζ(2) limit in the random assignment problem[END_REF][START_REF] Nair | Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures[END_REF][START_REF] Linusson | Completing a (k -1)-assignment[END_REF], and it is fair to say that, up to date, this model is one of the best-understood and instructive glassy system.

In analogy with the challenge of understanding spin glasses in finite dimension, there is an interest towards the study of measures µ N (J) which are induced by some random process in a d-dimensional domain. For example, the blue and red points could be drawn randomly in some compact domain Ω ⊂ R d (e.g., uniformly and independently), with the entry J ij given by some cost function c(x i , y j ) where x i and y j are the coordinates in Ω of the i-th blue point, and the j-th red point, respectively. In the simplest versions of the model, the cost will be invariant by translations and rotations, so it will just be a function of the Euclidean distance between the two points [START_REF] Mézard | The euclidean matching problem[END_REF], c(x, y) = c(|x -y|). Scaling and universality arguments suggest to consider cost functions with a power-law behaviour, that is, for some parameter p, we shall consider the cost function c(x i , y j ) = ±|x i -y j | p .

(1)

Moreover, the properties of the solution of the assignment problem depend strongly on the monotonicity and concavity of the cost function, and power-law costs span a variety of combinations of such behaviours as p varies in R (and the sign is considered). This observation suggests that models with different values of p, and different signs of the cost function, are potentially in different universality classes, so that it is desirable to perform a study of the model both at arbitrary d and at arbitrary p (and sign). For a cost function c(x, y) = s |x-y| p , with s = ±1, we say that we are in the attractive case if sp > 0 (that is, the cost increases as the distance increases), and in the repulsive case if sp < 0 (that is, the cost decreases as the distance increases). The limit p → 0 also makes sense, as the cost reads (with

s = ±1) c(x) = s|x| p = s(1+p ln |x|+O(p 2 )), but, as π opt ({J ij }) = π opt ({κJ ij +λ i +µ j }), at zero temperature this is equivalent to the cost c(x) = s ln |x| + O(p)
, where s = s for the limit p 0 and s = -s for the limit p 0. For the p > 1 attractive case (i.e. monotone increasing and convex cost function), if the subset Ω ⊂ R d is compact, it is known [START_REF] Ajtai | On optimal Matchings[END_REF] that the average total cost E N (H opt ) of the optimal assignment scales with the number of points N according to

E N (H opt )      N 1-p 2 for d = 1 N 1-p 2 (log N ) p 2 for d = 2 N 1-p d for d > 2 (2)
where a(N ) b(N ) if a(N ) b(N ) tends to a non-zero finite constant for N → ∞. In this case a relation with the classical optimal transport problem in the continuum has been exploited [START_REF] Caracciolo | Scaling hypothesis for the euclidean bipartite matching problem[END_REF], in particular for the case p = 2 where very detailed results have been obtained [START_REF] Caracciolo | Scaling hypothesis for the Euclidean bipartite matching problem. II. Correlation functions[END_REF][START_REF] Caracciolo | Quadratic stochastic euclidean bipartite matching problem[END_REF][START_REF] Ambrosio | A PDE approach to a 2-dimensional matching problem[END_REF].

If, at size N , the points are sampled uniformly in the domain Ω N := N 1 d Ω (as to keep the average density of order 1), we just have to scale the result above by the factor N p d . Recently also the case in which Ω is not compact, and the points are not sampled uniformly, has been considered [START_REF] Bobkov | One-dimensional empirical measures, order statistics, and Kantorovich transport distances[END_REF][START_REF] Caracciolo | Anomalous scaling of the optimal cost in the one-dimensional random assignment problem[END_REF][START_REF] Talagrand | Scaling and non-standard matching theorems[END_REF].

In the repulsive case p < 0 the cost function c is still convex. As far as we know, for this version of the problem only the case d = 1 has been studied in detail. In this case [START_REF] Caracciolo | On the one dimensional euclidean matching problem: exact solutions, correlation functions and universality[END_REF][START_REF] Caracciolo | Random euclidean matching problems in one dimension[END_REF]:

E N (H opt ) N . (3)
More precisely, in d = 1 corrections to the leading order in the large-N expansion were studied. Among the results, we could derive the first finite-size corrections for p < 0, and an explicit expression in N and p for p > 1 [START_REF] Caracciolo | Selberg integrals in 1d random euclidean optimization problems[END_REF]:

E N (H opt ) =        N Γ 1 + p 2 p + 1 Γ (N + 1) Γ N + 1 + p 2 Γ 1 + p 2 p + 1 N 1-p 2 for p > 1 N 1 2 p 1 + 1 3N p(p -2)(p -4) p -3 + o 1 N for p < 0 .
(4) The attractive case p < 0 has not been studied so far, but is possibly of interest. However, it is easily seen that in this case the quantity E N (H opt ) makes sense only when |p| < d, otherwise one just gets E N (H opt ) = -∞ already from the singular portion of the measure associated to the rare instances in which a red and a blue point almost coincide.

When 0 < p < 1, in the attractive case, the cost function c is instead concave. Also in this case only the case d = 1 has been considered, where it has been shown that the optimal solution is always non-crossing [START_REF] Robert | Exact solutions to the transportation problem on the line[END_REF][START_REF] Boniolo | Correlation function for the grid-poisson euclidean matching on a line and on a circle[END_REF]. A matching is non-crossing if each pair of matched points defines an interval on the line which is either nested to or disjoint from all the others. Contrary to the case p > 1, where in d = 1 the optimal matching is completely determined, and to the case p < 0, where in d = 1 it is known that the optimal matching has certain cyclic properties, the non-crossing property is not sufficient to fully characterize the optimal assignment; the regime 0 < p < 1 is thus much more challenging to study.

The relevance of non-crossing matching configurations among elementary units aligned on a line has emerged both in physics and in biology. In the latter case, this is due to the fact that they appear in the study of the secondary structure of single stranded DNA and RNA chains in solution [START_REF] Paul | RNA secondary structure: physical and computational aspects[END_REF]. These chains tend to fold in a planar configuration, in which complementary nucleotides are matched, and planar configurations are exactly described by non-crossing matchings between nucleotides. The secondary structure of a RNA strand is therefore a problem of optimal matching on the line, with the restriction on the optimal configuration to be planar [START_REF] Orland | RNA folding and large N matrix theory[END_REF][START_REF] Vernizzi | Enumeration of RNA Structures by Matrix Models[END_REF][START_REF] Nechaev | Planar diagrams from optimization for concave potentials[END_REF]. The statistical physics of the folding process is highly non-trivial and it has been investigated by many different techniques [START_REF] Bundschuh | Statistical mechanics of secondary structures formed by random RNA sequences[END_REF][START_REF] Mller | Statistical physics of RNA folding[END_REF], also in presence of disorder and in search for glassy phases [START_REF] Nechaev | Planar diagrams from optimization for concave potentials[END_REF][START_REF] Bundschuh | Statistical mechanics of secondary structures formed by random RNA sequences[END_REF][START_REF] Paul | Overlaps between RNA secondary structures[END_REF][START_REF] Pagnani | Glassy Transition in a Disordered Model for the RNA Secondary Structure[END_REF][START_REF] Marinari | Zerotemperature properties of RNA secondary structures[END_REF]. So, as a further motivation for the present work, understanding the statistical properties of the solution to random Euclidean matching problems with a concave cost function could yeld results and techniques to better understand these models of RNA secondary structure.

A summary of the scaling behaviours for the different declinations of the models is provided in the Conclusion section.

Random Assignment Problems studied in this paper

In this paragraph we describe the problem of 0 < p < 1 random assignment in detail, and fix our notations.

First, we fix Ω to be a segment (an alternate possible choice, 1-dimensional in spirit, which is not considered here but is considered, for example, in [START_REF] Caracciolo | Quadratic stochastic euclidean bipartite matching problem[END_REF][START_REF] Caracciolo | On the one dimensional euclidean matching problem: exact solutions, correlation functions and universality[END_REF][START_REF] Boniolo | Correlation function for the grid-poisson euclidean matching on a line and on a circle[END_REF], is to take Ω as a circle, or more generally, in dimension d, to take Ω as a d-dimensional torus [START_REF] Caracciolo | Scaling hypothesis for the euclidean bipartite matching problem[END_REF]).

Notice that in the literature Ω is typically taken to be deterministically the unit segment [0, 1], while in our paper we will find easier to work with a segment

x 1 y 1 x 2 x 3 y 2 • • • s 0 s 1 s 2 s 3 s 4 • • • 0 L Figure 1: Example of instance J = ( x, y) = [ s, σ]
, in the PPP model. Bottom: the configuration of points. Top: the Dyck bridge associated to σ. Here N = 8, and σ = {+, -, +, +, -, +, -, -, -, -, +, +, -, +, +, -}.

[0, L], where L may be a stochastic variable, whose distribution depends on N . We will work in the framework of constant density, that is E(L) ∼ N , so that, for comparison with the existing literature, our results should be corrected by multiplying by a factor of the order N -p . In dimension 1 there is a natural ordering of the points, so that we can encode an instance J = ( x, y) by the ordered lists x = (x 1 , x 2 , . . . , x N ), x i ≤ x i+1 , and y = (y 1 , y 2 , . . . , y N ), y i ≤ y i+1 . A useful alternate encoding of the instance is J = [ s, σ], where s = (s 0 , s 1 , . . . , s 2N ), s i ∈ R + , encodes the distances between consecutive points (and between the first/last point with the respective endpoint of the segment Ω) and the vector σ = (σ 1 , σ 2 , . . . , σ 2N ) ∈ {-1, +1} 2N , with i σ i = 0, encodes the sequence of colours of the points (see Figure 1, where the identification blue = +1 and red = -1 is adopted). In other words, the partial sums of s, i.e. (s 0 , s 0 + s 1 , s 0 + s 1 + s 2 , . . . , s 0 + • • • + s 2N -1 ), constitute the ordered list of x ∪ y, and σ describes how the elements of x and y do interlace. In this notation, the domain of the instance Ω = [0, L] is determined by L = 2N i=0 s i . Remark that the cardinality of the space of possible vectors σ is just the central binomial,

B N := 2N N . (5)
For simplicity, in this paper we consider only the non-degenerate case, in which almost surely all the s i 's are strictly positive, that is, the values in x ∪ y are all distinct.

In this paper, and more crucially in subsequent work, we shall consider two families of measures. In all these measures, we have a factorisation µ([ s, σ]) = µ 1 ( s)µ 2 (σ), and the measure on σ is just the uniform measure.

Independent spacing models (ISM). The measure µ( s) is factorised, and the s i 's are i.i.d. with some distribution f (s) with support on R + (and, for simplicity, say with all moments finite, ds s k f (s) < ∞ for all k). Without loss of generality, we will assume that the average of f (s) is 1, i.e. the average of L is 2N + 1. In particular, we will consider:

Uniform spacings (US): the s i 's are deterministic, identically equal to 1, and thus L = 2N + 1 for all instances;

Exponential spacings (ES): the s i 's are i.i.d. with an exponential distribution f (s) = g 1 (s) = exp(-s), and thus L concentrates on 2N +1, but has a variance of order N .

Exchangeable process model (EPM). This is a generalisation of the ISM above, but now the s i 's are not necessarily i.i.d., they are instead exchangeable variables, that is, for all 0 ≤ i < 2N , µ(s 0 , . . . , s i , s i+1 , . . . , s 2N ) = µ(s 0 , . . . , s i+1 , s i , . . . , s 2N ) .

In particular, within this class of models we could have that µ is supported on the hyper-tetrahedron T 2N described by s i ≥ 0, and L = i s i = 2N + 1. In this paper, we will consider:

Poisson Point Process (PPP): the s i 's are the spacings among the sorted list of 0, 2N +1, and 2N uniform random points in the interval [0, 2N + 1].

Each of these three models has its own motivations. The PPP case is, in a sense, the most natural one for what concerns applications and the comparison with the models in arbitrary dimension d. Implicitly, it is the one described in the introduction. The ES case is useful due to a strong relation with the PPP case (see Remark 1 and Lemma 4 later on in Section 2.2). In a sense, it is the "Poissonisation" of the PPP case (where in this case it is the quantity L that has been "Poissonised", that is, it is taken stochastic with its most natural underlying measure, instead of deterministic). The US case will prove out, in future work, to be the most tractable case for what concerns lower bounds to the optimal cost. As all of the measures above are factorized in σ and s, and the measure over σ is uniform, it is useful to define two shortcuts for two recurrent notions of average. Definition 1 For any quantity A(J) = A(σ, s), we denote by A the average of

A over σ A := E σ (A) = 1 B N σ A(σ, s) ; ( 7
)
This average is independent from the choice of model among the classes above. We denote by

A := E µ( s) (A) (8)
the average of A over s, with its appropriate measure dependence on the choice of model. Finally, we denote by E N (A) the result of both averages, in which we stress the dependence from the size parameter N in the measure, that is

E N (A) := E σ,µ( s) (A) = A = A . (9)
For a given instance, parametrised as J = ( x, y), or as J = [ s, σ], (and in which the cost function also has an implicit dependence from the exponent p), call π opt one optimal configuration, and H opt (J) = H J (π opt ).

In this paper, we will introduce the notion of Dyck matching π Dyck of an instance J and we will compute its average cost H Dyck := E N (H J (π Dyck )) for the measures ES and PPP (with a brief discussion on the US case).

In particular we prove the following theorem:

Theorem 1 For the three measures ES, US and PPP, let E N (H Dyck ) denote the average cost of the Dyck matchings. Then

E N (H Dyck )    N 0 ≤ p < 1 2 N ln N p = 1 2 N 1 2 +p 1 2 < p ≤ 1 ( 10
)
where

a(N ) b(N ) if a(N ) b(N ) tends to a finite, non-zero constant when N → ∞.
This theorem follows directly from the combination of suitable lemmas, namely Proposition 1, Proposition 2 and Corollary 1 appearing later on. In fact, our results are more precise than what is stated in the theorem above (we describe the first two orders in a series expansion for large N , including formulas for the associated multiplicative constants), details are given in the forementioned propositions.

The average cost of Dyck matchings provides an upper bound on the average cost of the optimal solution; numerical simulations for the PPP measure, described in Section 4, suggest the following conjecture, that we leave for future investigations:

Conjecture 1 For the three measures ES, US and PPP, and all 0 < p < 1, lim

N →∞ E N (H opt ) E N (H Dyck ) = k p , (11)
with 0 < k p < 1.

Basic facts

Before starting our main proof, let us introduce some more notations, and state some basic properties of the optimal solution.

Basic properties of the optimal matching

A Dyck path of semi-length N is a lattice path from (0, 0) to (2N, 0) consisting of N 'up' steps (i.e. steps of the form (1, 1)) and N 'down' steps (i.e., steps (1, -1)), which never goes below the x-axis. There are C N Dyck path of semi-length N , where

C N = 2N N - 2N N + 1 = 1 N + 1 2N N ( 12
)
are the Catalan numbers. Therefore the generating function for the Dyck paths is

C(z) := k≥0 C k z k = 1 - √ 1 -4z 2z = 2 1 + √ 1 -4z (13)
The historical name 'Dyck path' is somewhat misleading, as it leaves us with no natural name for the most obvious notion, that is, the walks of length N with steps in {(1, 1), (1, -1)}. With analogy with the theory of Brownian motion (which relates to lattice walks via the Donsker's theorem) [START_REF] Pitman | A guide to Brownian motion and related stochastic processes[END_REF], we will define four types of paths, namely walks, meanders, bridges and excursions, according to the following table:

y(2N ) = 0 y(x) ≥ 0 ∀x walk no no meander
no yes bridge yes no excursion yes yes (of course, by 'no' we mean 'not necessarily'). Thus, in fact, the 'paths' are the most constrained family of walks, that is the excursions.

In general a Dyck path (i.e., a Dyck excursion) can touch the x-axis several times. We shall call an irreducible Dyck excursion a Dyck path which touches the x-axis only at the two endpoints. It is trivially seen that the generating function for the irreducible Dyck excursions is simply z C(z). As we said above a Dyck bridge is a walk made with the same kind of steps of Dyck paths, but without the restriction of remaining in the upper half-plane, and which returns to the x-axis. The generating function for the Dyck bridges is

B(z) := 1 1 -2z C(z) = 1 √ 1 -4z = k≥0 B k z k (14)
with B k the central binomials ( 5), and k is the semi-length of the bridge (just like excursions, all Dyck bridges must have even length). The factor 2 in the functional form of B(z) in terms of C(z) enters because a bridge is a concatenation of irreducible excursions, each of which can be in the upper-or the lower-half-plane. Now, it is clear that each configuration σ corresponds uniquely to a Dyck bridge of semi-length N , with σ i = +1 or -1 if the i-th step of the walk is an up or down step, respectively.

In a Dyck walk we shall call (k blue (i), h blue (i)) the two coordinates of the mid-point of the i-th ascending step of the walk (minus ( 12 , 1 2 ), in order to have integer coordinates and enlighten the notation), and call (k red (i), h red (i)) the coordinates of the mid-point of the i-th descending step (again, minus ( 12 , 1 2 )). For e = (i, j) an edge of a matching π, call e = k blue (i)-k red (j) the horizontal distance on the walk, and |e| = |x i -y j | the Euclidean distance on the domain segment.

For a given Dyck bridge σ, we say that π ∈ S N is non-crossing if, for every pair of distinct edges e 1 = (i 1 , j 1 ) and e 2 = (i 2 , j 2 ) in π, we do not have the pattern k blue (i 1 ) < k blue (i 2 ) < k red (j 1 ) < k red (j 2 ), or the analogous patterns with k blue (i 1 ) ↔ k red (j 1 ), or k blue (i 2 ) ↔ k red (j 2 ), or (•) 1 ↔ (•) 2 . The name comes from the fact that, if we represent a matching π as a diagram consisting of the domain segment [0, L], and the set of N semicircles above this segment connecting the x i 's to the y π(i) 's (as in the bottom part of Figure 2), then these semicircles do not intersect if and only if π is non-crossing. Note that, although these semicircles are drawn on the full [ s, σ] instance, the notion of π being non-crossing only uses the vector σ.

For a given Dyck bridge σ, we say that π ∈ S N is sliced if, for every edge e = (i, j) ∈ π, we have h blue (i) = h red (j).

Two easy lemmas have a crucial role in our analysis.

Lemma 1 All the optimal matchings are non-crossing.

Proof. The proof is by absurd. Suppose that π is a crossing optimal matching. If we have a pattern as k blue (i 1 ) < k red (j 2 ) < k red (j 1 ) < k blue (i 2 ), then the matching π with edges e 1 = (i 1 , j 2 ) and e 2 = (i 2 , j 1 ) has

H J (π ) < H J (π), because |e 1 | < |e 1 | and |e 2 | < |e 2 |.
If we have a pattern as k blue (i 1 ) < k blue (i 2 ) < k red (j 1 ) < k red (j 2 ), then again the matching π with edges e 1 = (i 1 , j 2 ) and e 2 = (i 2 , j 1 ) has H J (π ) < H J (π), although this holds for a more subtle reason.

Calling a = x 2 -x 1 , b = y 1 -x 2 and c = y 2 -y 1 , we have |e 1 | = a + b, |e 2 | = b + c, |e 1 | = a + b + c and |e 2 | = b.
It is the case that, for a, b, c > 0 and 0 < p < 1,

(a + b) p + (b + c) p > (a + b + c) p + b p . ( 15
)
A proof of this inequality goes as follows. Call

F (a, b, c) = (a + b) p + (b + c) p - (a + b + c) p -b p .
We have F (a, b, 0) = 0, and

1 p ∂ ∂c F (a, b, c) = 1 (b + c) 1-p - 1 (a + b + c) 1-p > 0 . ( 16
)
All the other possible crossing patterns are in the first or the second of the forms discussed above, up to trivial symmetries.

Non-crossing properties for assignment and optimal transport problems with concave cost functions were studied in the continuum case in [START_REF] Robert | Exact solutions to the transportation problem on the line[END_REF] and in the discrete one in [START_REF] Boniolo | Correlation function for the grid-poisson euclidean matching on a line and on a circle[END_REF].

Lemma 2 All the optimal matchings are sliced.

Proof. The proof is by absurd. Suppose that π is a non-sliced optimal matching. If we have (i, j) ∈ π with h blue (i) = h red (j), say h blue (i) -h red (j) = δh = 0, we have that the point x i is matched to y j , and that, between x i and y j , there are n blue and n red blue and red points, respectively, with n blue -n red = -δh = 0. So there must be at least |δh| points inside the interval (x i , y j ) which are matched to points outside this interval, and thus, together with (i, j), constitute pairs of crossing edges. So, by Lemma 1, π cannot be optimal. The slicing of optimal assignments was studied in [START_REF] Delon | Local Matching Indicators for Transport Problems with Concave Costs[END_REF].

Reducing the PPP model to the ES model

Theorem 1 (and, hopefully, Conjecture 1), in principle, shall be proven for three different models, Uniform Spacings (US), Exponential Spacings (ES) and the Poisson Point Process (PPP). However, as we anticipated, the PPP case is a minor variant of ES. In this section we give a precise account of this fact. The starting point is a relation between the two measures:

Remark 1 We can sample a pair [ s , σ] with the measure µ ES N by sampling a pair [ s, σ] with the measure µ PPP N , a value L ∈ R + with the measure g 2N +1 (L) = L 2N
(2N )! exp(-L) dL, and then defining

s i = s i L 2N +1 .
Indeed, the measure on s in the PPP can be seen as the measure over independent exponential variables conditioned to the value of the sum; thus, the procedure leads at sight to a measure over s which is unbiased within vectors s with the same value of L = i s i . Then, from the independence of the spacings in the ES model we easily conclude that the distribution of L must be exactly g More precisely, for k an integer, define the Gamma measure

g k (x) := x k-1 Γ(k) e -x = g * k 1 (x) . (17)
We use the same notation for its analytic continuation to k real positive. We introduce (the analytic continuation of) the rising factorial (following the notation due to D. Knuth [START_REF] Graham | Concrete mathematics[END_REF]):

n p := Γ(n + p) Γ(n) = dx g n (x)x p . ( 18
)
This choice of notation is motivated by the fact that n 1 = n 1 = n, and that, for

n p 2 , n p = n p (1 + O(p 2 /n))
. More precisely we have:

Lemma 3 For 0 ≤ p ≤ 1 and n > 1 (n + p -1) p ≤ n p ≤ n p . ( 19
)
Proof. It is well known that the Gamma function is logarithmically convex [START_REF] Artin | The Gamma Function[END_REF].

In particular, for any 0

≤ p ≤ 1, ln Γ(n + p) ≤ (1 -p) ln Γ(n) + p ln Γ(n + 1) = ln Γ(n) + p ln n , (20)
that is

n p = exp(ln Γ(n + p) -ln Γ(n)) ≤ exp(p ln n) = n p . (21)
Analogously, we have ln Γ(n) ≤ (1-p) ln Γ(n+p)+p ln Γ(n+p-1) = ln Γ(n+p)-p ln(n+p-1) , [START_REF] Caracciolo | Selberg integrals in 1d random euclidean optimization problems[END_REF] that is

n p = exp(ln Γ(n + p) -ln Γ(n)) ≥ exp(p ln(n + p -1)) = (n + p -1) p . ( 23
)
Summing up, Remark 1 and Lemma 3 allow to prove that Lemma 4 The following inequalities hold:

2N 2N + 1 p(1-p) E(H ES opt ) ≤ E(H PPP opt ) ≤ E(H ES opt ) . ( 24
)
Also the corresponding inequalities with H opt replaced by H Dyck do hold, as well as for any other quantity H(π * (J)), whenever π * is some matching determined by the instance, and invariant under scaling of the instance, that is

π * [ s, σ] = π * [λ s, σ].
Proof. For compactness of notation, we do the proof only for the H opt case, but the generalisation is straightforward. Of course,

H [λ s,σ] (π) = λ p H [ s,σ] (π)
for all instances [ s, σ], all configurations π, and all scaling factors λ > 0 (so

as π * [ s, σ] = π * [λ s, σ], it follows that H [λ s,σ] (π * [λ s, σ]) = λ p H [ s,σ] (π * [ s, σ])).
In particular, H opt ([λ s, σ]) = λ p H opt ([ s, σ]). In light of Remark 1, we can describe the average over µ ES [ s, σ] in terms of an average over µ PPP [ s, σ], and over g 2N +1 (L). More precisely

E(H ES opt ) = dµ ES [ s , σ] H opt ([ s , σ]) = dµ PPP [ s, σ] dL g 2N +1 (L) L 2N + 1 p H opt ([ s, σ]) = E(H PPP opt ) dL g 2N +1 (L) L 2N + 1 p = E(H PPP opt ) (2N + 1) p (2N + 1) p . ( 25
)
The upper bound follows directly from Lemma 3. The lower bound follows as:

(2N + 1) p (2N + 1) p ≥ 1 - 1 -p 2N + 1 p ≥ 1 - 1 2N + 1 p(1-p) (26)
where first one uses Lemma 3, then the inequality (1 -q ) p ≥ (1 -) pq (valid for , p, q ∈ [0, 1]), with = 1 2N +1 and q = 1 -p. In light of this lemma, it is sufficient to consider Theorem 1 (and Conjecture 1) only for the US and ES models.

The precise statement of our conclusions is the following:

Corollary 1

E P P P N (H Dyck ) = E ES N (H Dyck ) 1 + O N -1 . ( 27
)
The relevance of this statement lies in the fact that, in the forthcoming equation (28), we provide an expansion for E ES N (H Dyck ) in which corrections of relative order 1/N appear as the third term in the expansion (and we provide explicit results only for the first two terms). As a result, the very same conclusions that we have for the ES model do apply verbatim to the PPP model.

The Dyck matching

For every instance [ s, σ], there is a special matching, that we call π Dyck , which is sliced and non-crossing for σ. This is the matching obtained by the canonical pairing of up-and down-steps within every excursion of the Dyck bridge (see Figure 2). In analogy with our notation H opt (J) = H J (π opt ), let us introduce the shortcut H Dyck (J) = H J (π Dyck ).

Remark 2

The Dyck matching π Dyck is determined by the order of the colours of the points, σ. In particular it does not depend on the actual spacings between them, s, and it does not depend on the cost exponent p.

Remark 2 is a crucial fact that makes possible the evaluation of the statistical properties of π Dyck , with a moderate effort. In particular, it will lead to the main result of this paper: Proposition 1 For all independent spacing models

E N (H Dyck ) ∼        Ap 2 N + 2 p Γ(p-1 2 ) 4Γ(p+1) N 1 2 +p + O(1) p < 1 2 1 √ 2π N log N + A * 2 + A * N + O(log N ) p = 1 2 . 2 p Γ(p-1 2 ) 4Γ(p+1) N 1 2 +p + Ap 2 N + O(N -1 2 +p ) p > 1 2 ( 28
)
where A p and A * are model-dependent quantities, which are not larger than

A max p := 2 p+1 (1 -2p)Γ (1 -p) , A max * = 2 π (log 2 + γ E ) . (29)
and

A * = γ E + 2 log 2 -2 √ 2π . ( 30
)
In particular, for the ES model

A ES p = Γ 1 2 -p Γ (p + 1) 2 p-1 √ π Γ (2 -p) A ES * = 2 π (5 log 2 + γ E -4) . (31)
The remaining of this section is devoted to the proof of this proposition. First, we factorize the average over the instance J = [ s, σ] in two independent averages, the average over σ and the one over s (see Definition 1):

E N (H Dyck ) = E N i=1 J i,π Dyck (i) = N i=1 J i,π Dyck (i) = B -1 N σ N i=1 |k blue (i) -k red (π σ Dyck (i))| p , (32)
where in the last line we emphasize that π Dyck depends only on σ, as stated in Remark 2, and we adopted again the shortcut B N = 2N N for the total number of configurations σ.

Due to the fact that the spacings s i are independent, the quantity appearing above, |k blue (i) -k red (π σ Dyck (i))| p , only depends on the length e = 2k + 1 of the corresponding link e = (i, π Dyck (i)), via the formula

S (p) k := |k blue (i) -k red (π σ Dyck (i))| p = 2k j=0 s j p , (33)
where the s j 's are i.i.d. variables sampled with the distribution f (s) (that is, in the ES model, i.i.d. exponential random variables).

Then, as a general paradigm for observables of the form e∈π F (|e|) , we rewrite the sum over all possible σ and over all links e of a given matching π = π Dyck (σ) as a sum over the forementioned parameter k, with a suitable combinatorial factor v N,k :

e∈π F (|e|) = B -1 N N -1 k=0 v N,k F 2k j=0 s j (34) v N,k = σ e∈π Dyck (σ) δ e ,2k+1 . (35)
(Note that k v N,k = N B N = 2 2N -1 N
). In particular, in our case,

E N (H Dyck ) = B -1 N N -1 k=0 v N,k S (p) k . (36)
So we face two separate problems: (1) determining the combinatorial coefficients v N,k , which are 'universal' (i.e., the same for all independent-spacing models, for all cost exponents p and for all observables F as above); (2) determining the quantities S (p) k , that is, the average over the Euclidean length |e| of the link (which depends from the function f (s) that defines the independent-spacing model, and from the exponent p).

For what concerns S = Γ(2k + 1 + p)/Γ(2k + 1). More generally, for any model with independent spacings we would have that S (p) k = dx x p f * 2k+1 (x) that is, the sum of 2k + 1 i.i.d. random variables is distributed as the (2k + 1)-fold convolution of the single-variable probability distribution. For the ES case this is exactly the Gamma distribution g 2k+1 (s). Up to this point, we could have also evaluated the analogous quantity for the PPP model, although with a bigger effort (but, from Section 2.2, we know that this is not necessary).

For what concerns v N,k , in Appendix A we prove that

v N,k = C k 4 N -k-1 + N -k 2 B N -k =: C k V N -k-1 . (37)
In particular, the simple expression for V N -k-1 gives in a straightforward way

V (z) := ∞ j=0 V j z j = (1 -4z) -1 + (1 -4z) -3 2 . ( 38
)
We pause to study the distribution of the lengths e of links in π Dyck , that is, the normalised distribution (in k), with parameter N , given by the expression v N,k /(N B N ). It is known that planar secondary structures have a universal behaviour for the tail of such a distribution, with exponent -3 2 . Indeed, by performing a large N expansion at fixed k, and then studying the large k behaviour, one has

v N,k N B N = C k N B N 4 N -k-1 + N -k 2 B N -k N →∞ ≈ 2 C k 4 -k k→∞ ≈ 2 π k -3 2 , (39)
reproducing the known behaviour. Equation [START_REF] Graham | Concrete mathematics[END_REF], with the help of ( 37) and [START_REF] Flajolet | Analytic combinatorics[END_REF], can be used to relate the generating functions

E(z; p) := ∞ N =0 B N E N (H Dyck ) z N (40) S(z; p) := ∞ k=0 C k S (p) k z k . (41)
Lemma 5

E(z; p) = z V (z) S(z; p) (42)
Proof.

E(z; p) := ∞ N =0 B N E N (H Dyck )z N = ∞ N =0 N -1 k=0 C k V N -k-1 S (p) k z N = ∞ k=0 C k S (p) k z k ∞ N =k+1 V N -k-1 z N -k = z V (z) S(z; p) (43)
The behaviour at large k of S (p) k is determined by the theory of large deviations. Said heuristically, the sum of the 2k + 1 i.i.d. variables s i concentrates on 2k + 1, with tails which are sufficiently tamed that the average of x p is equal to (2k + 1)

p (1 + O(k -1 )). That is, S (p) k ∼ (2k + 1) p ∼ 2 p k p ,

and we have

C k S (p) k ∼ 2 p √ π 4 k k p-3 2 . ( 44
)
We recall a fundamental fact in the theory of generating functions: the singularities of a generating function determine the asymptotic behaviour of its coefficients. In particular, the modulus of the dominant singularity (that nearest to the origin) determines the exponential behaviour, and the nature of the singularity determines the subexponential behaviour (see [START_REF] Flajolet | Analytic combinatorics[END_REF] for a comprehensive treatment of singularity analysis, and Appendix B for a summary of results). This tells us that we just need an expression for E(z; p) around its dominant singularity to extract asymptotic information on the total cost, i.e. we just need to evaluate S(z; p) locally around the dominant singularity of E(z; p). First of all, one needs to locate the dominant singularity of S(z; p) and compare it with the z = 1 4 singularity of V (z). From Equation 44, we find an exponential behaviour ∼ 4 n of the coefficient of S(z; p), trivially due to the entropy of Dyck walks of length 2n, thus, the singularity must be in z = 1 4 . Notice that this agrees with the dominant singularity of V (z) (which also is, essentially, a generating function of Dyck walks up to algebraic corrections), so that both generating functions will combine to give the final average-cost asymptotics.

At the dominant singularity, the power-law behaviour of the coefficients is given by a generating function of the kind

S(z; p) = A p + B p (1 -4z) gp + o((1 -4z) gp ) , (45)
where A p encodes the regular terms at the singularity, and o((1-4z) gp ) accounts for all other singular terms leading to non trivial subleading corrections (among them one finds power, logarithms. . . in the variable 1 -4z).

In fact, in such a simple situation as in our case, we expect a more precise behaviour, S(z; p)

= A p (1 + O(1 -4z)) + B p (1 -4z) gp (1 + O(1 -4z))
, where we have two series of corrections, in integer powers, associated to the regular and singular parts of the expansion around the singularity (up to the special treatment of the degenerate case g p ∈ Z).

Notice that B p and g p can be found by computing the asymptotic behaviour of the coefficients of Equation 45

S (p) k ∼ B p Γ (-g p ) 4 k k -gp-1 = 2 p √ π 4 k k p-3 2 , ( 46
)
giving, by comparison with Equation 44,

g p = 1 2 -p B p = 2 p Γ p -1 2 √ π . ( 47
)
Nothing can be said on the coefficient A p without performing the exact resummation of the generating function at the singularity (possibly, after having subtracted a suitable diverging part). This analysis results in an asymptotic expression for E(z; p):

E(z; p) ∼ 1 4 A p (1 -4z) -3 2 + 2 p Γ p -1 2 √ π (1 -4z) -(1+p) (48)
for p = 1 2 , and

E z; p = 1 2 = 1 4 (1 -4z) -3 2 A 1 2 + + 1 2 π + 2 π log 1 1 -4z + o( ) = 1 4 (1 -4z) -3 2 A * + 2 π log 1 1 -4z (49) for p = 1
2 , where = p -1 2 . The hypothesis of S(z; p) being non-singular in p implies that A p must cancel the 1 singularity, leaving a regular part

A * = lim →0 A 1 2 + + 1 2 π . ( 50
)
This set of results has remarkable consequences, as it unveils a certain universality feature for E(z; p). In fact, for all models in our large classes, the nature of the dominant singularity of E(z; p) is the same, giving a universal asymptotic scaling in N for the average cost of Dyck matchings. Moreover, in the p ≥ 1 2 regime, also the coefficient of the dominant singularity is universal.

We can now expand the generating function using standard techniques (Appendix B, [START_REF] Flajolet | Analytic combinatorics[END_REF]) and the fact that

B N ∼ 4 N √ π N , obtaining E N ∼      Ap 2 N + o(N ) p < 1 2 1 √ 2π N log N + o(N log N ) p = 1 2 . 2 p Γ(p-1 2 ) 4Γ(p+1) N 1 2 +p + o(N 1 2 +p ) p > 1 2 (51)
and in fact, more precisely,

E N ∼        Ap 2 N + 2 p Γ(p-1 2 ) 4Γ(p+1) N 1 2 +p + O(1) p < 1 2 1 √ 2π N log N + A * 2 + A * N + O(log N ) p = 1 2 . 2 p Γ(p-1 2 ) 4Γ(p+1) N 1 2 +p + Ap 2 N + O(N -1 2 +p ) p > 1 2 (52)
where the terms of the expansion are just the same for the p < 1 2 and p > 1 2 cases, but have been arranged differently, in the order of dominant behaviour. The quantity A * has been defined in (50), for the behaviour of S(z; 1 2 ), while the quantity

A * = γ E + 2 log 2 -2 √ 2π ( 53
)
is a further (universal) correction coming from taking into account how S(z; 1 2 ) enters in E(z; 1 2 ), via V (z) (and γ E is the Euler-Mascheroni constant). The formulas above gives the precise asymptotics, up to relative corrections of the order N -1 . As a corollary, we have this very same behaviour in the PPP model, as, from Lemma 4 and Corollary 1, we know that also the relative corrections between ES and PPP models are of the order N -1 .

For higher-order corrections, one would need to take into account more subleading terms in Equation 45.

For the ES case the resummation of E(z; p) can be performed analytically by writing the Catalan number in terms of Gamma functions, namely

C k = 4 k Γ k + 1 2 √ π Γ(k + 2) . ( 54
)
giving

S(z; p) = Γ (p + 1) F p+1 2 , p+2 2
2 4z ( 55
)
where F is the 2 F 1 hypergeometric function (a reminder is in Appendix B, equation ( 86)). This allows for an explicit computation of the two non-universal quantities in our expansion:

A ES p = Γ 1 2 -p Γ (p + 1) 2 p-1 √ π Γ (2 -p) A ES * = 2 π (5 log 2 + γ E -4) . ( 56
)
note how the A * and A * terms involve combinations of quantities of the same algebraic nature. See Appendix B for the details of the derivation. Similar but more complex resummations seem possible in the independent spacing case, when the function f (x) is a Gamma distribution, f (x) = ag a (ax) for a ∈ N/2, and S(z; p) is obtained in terms of generalised hypergeometric functions k+1 F k . However no exact resummation seems possible for the US case (which would require a limit a → ∞ in this procedure). Nonetheless, we are able to provide bounds on A US p . Proposition 2

Γ 1 2 -p Γ (p + 1) 2 p-1 √ π Γ (2 -p) = A ES p ≤ A US p ≤ A US,upper p := 2 p+1 (1 -2p)Γ (1 -p) . (57)
Note that, due to the fact Γ(

1 2 -p)Γ(1 -p) = √ π 2 2p Γ(1 -2p
), the bounds above can be rewritten as

1 p (2 -2p) p 2 p+1 (1 -2p)Γ (1 -p) ≤ A US p ≤ 2 p+1 (1 -2p)Γ (1 -p) . (58)
Proof. We use Lemma 3 and the increasing monotony of x p to write

(2k + 1) p ≤ (2k + 1) p ≤ 2 p (k + 3 2 -p) p ≤ 2 p (k + 2 -p) p (59)
so that we can bound A U S p from below by A ES p , and from above by the regular part of the expansion around z =1 4 of the generating function

2 p k≥0 C k (k + 2 -p) p z k . (60)
This can be easily resummed to a hypergeometric function

2 p Γ (2 -p) F 1 2 , 1 2 -p 4z (61)
whose regular part is (see Appendix B)

A US,upper p = 2 p+1 (1 -2p)Γ (1 -p) . ( 62
)
The ratio between the upper and lower bound, in the range p ∈ [0, 1 2 ] (where the corresponding term in the expansion is leading), is rather near to 1: it reaches 1 at the endpoints of the interval, and has a unique maximum, at the value p solving 2ψ(2-2p) = ψ(2-p)+ψ(1+p), or, by using a duplication formula for the digamma function, solving ψ(p + 1) -ψ(p + 1 2 ) = ln 4 -π tan(πp). Numerically, the maximum is around p = 0.2626 . . ., and is valued 1.1445 . . . The analogous treatment in the degenerate case p → 1 2 gives bounds also on

A US * 2 π (log 2 + γ E + 4 (log 2 -1)) ≤ A US * ≤ 2 π (log 2 + γ E ) . (63)
The fact that A US p ≥ A ES p , that we used above, is not isolated, but is instead the consequence of the fact that the US distribution f U S (x) = δ(x -1) and the ES distribution

f ES (x) = e -x Θ(x) are 'ordered', f U S (x)
f ES (x), w.r.t. the notion of transportation order introduced in Appendix C. More generally, as implied by Lemmas 6 and 7 in the appendix, if for two probability distributions f 1 (x) f 2 (x) we have determined A f1 p ≤ A ub p and A f2 p ≥ A lb p (and the analogous statement for A * ), then, for every distribution f 1 (x) f (x) f 2 (x) we have that A lb p ≤ A f p ≤ A ub p (and the analogous statement for A * ), with no need of calculations (notice the inversion of upper and lower bounds due to the concavity of our cost function). This is due to the fact that, for all k, the integral dx

x p f * k (x) is bounded as dx x p f * k 2 (x) ≤ dx x p f * k (x) ≤ dx x p f * k 1 (x) (64)
(first, by Lemma 6, f * k

1 f * k f * k 2 ,
then by Lemma 7 and the fact that x p is concave, we obtain the inequalities above).

In particular, the US distribution is the bottom element of the transportationorder semilattice, thus the upper bound in equation ( 57) is universal for all independent-spacing models.

Numerical results and the average cost of the optimal matching

Our main results concern the leading behaviour of the average cost of the Dyck matching, which, of course, provides an upper bound to the average cost of the optimal matching. The explicit investigation of small-size instances suggests that the optimal matching is often quite similar to the Dyck matching, in the sense that the symmetric difference between π opt and π Dyck typically consists of 'few' cycles, which are 'compact', in some sense. Thus, a natural question arises: could it be that the large-N average properties of optimal matchings and Dyck matchings the same? If not, in which respect do they differ? In order to try to answer this question, we have performed numerical simulations by generating random instances with measure µ P P P N , and we have computed the average cost associated to the optimal and to the Dyck matching.

Figure 3 gives a comparison between the two average costs by plotting their ratio as a function of N for various values of p. The corresponding fits seem to exclude the possibility that the limit for large N of the ratio of average costs go to zero algebraically in N (and also makes it reasonable that there are no logarithmic factors, although this is less evident), that is, these data suggest the content of Conjecture 1. In order to further test this hypothesis, we fitted the optimal average cost to the same scaling behaviour found for the Dyck matching average cost, i.e.

a p N + b p N 1 2 +p p = 1 2 c N log N + d p = 1 2 (65)
fixing the scaling exponents and aiming to compute the scaling coefficients. Notice that the term a p N is leading for 0 < p < 1 2 , while b p N 1 2 +p is leading for 1 2 < p < 1. Figure 4 summarizes the fitted parameters.

For the Dyck matching, the fitted parameter for the leading scaling coefficient agrees perfectly with the computed coefficient, as expected. The coefficient of the subleading term seems to agree with the computed coefficient in a less precise way, probably due to stronger higher-order corrections. For the optimal matching, the fitted coefficients behave qualitatively as the coefficients that we have computed for the Dyck case, but the agreement is visibly not quantitative. The fit seems to confirm the hypothesis that the two average costs have the same scaling exponents with different coefficients.

To completely confirm such hypothesis, we suggest that lower bounds for the cost could be computed. We expect such lower bounds to share the same scaling as that found in this paper, but with different constants. We leave such matter open for future work.

Conclusion

In this paper we have addressed the random Euclidean assignment problem in dimension 1, for points chosen in an interval, with a cost function which is an increasing and concave power law, that is c(|x|) = |x| p for 0 < p < 1. We introduced a new special matching configuration associated to an instance of the problem, that we called the Dyck matching, as it is produced from the Dyck bridge that describes the interlacing of red and blue points on the domain.

As this is a deterministic configuration, described directly in terms of the instance, instead of involving a complex optimisation this configuration is much more tractable than the optimal matching. On top of this fact, we can exploit a large number of nice facts, from combinatorial enumeration, which provides us also with several results which are exact at finite size, this being, to some extent, surprising. In particular, we computed the average cost of Dyck matchings under a particular choice of probability measure (the one in which the spacings among consecutive points are i.i.d. exponential variables). Finally, we performed numerical simulations that suggest that the average cost of Dyck matchings has the same scaling behaviour of the average cost of optimal matchings. We leave this claim as a conjecture. A promising way to prove this conjecture seems to be that of providing a lower bound on the average cost of optimal matchings with the same scaling as our upper bound, by producing "sufficiently many" or "sufficiently large" sets of edge-lengths which must be taken by the optimal solution. If we assume our conjecture, this result allows to fill in a missing portion in the phase diagram of the model, for what concerns the scaling of the average optimal cost as a function of p (see Figure 5). These new facts highlight a much richer structure that what could have been predicted in light of the previous results alone, with the concatenation of four distinct regions, and a special point with logarithmic corrections.

The case of uniformly spaced points needs further analysis in the region p < 1/2. One can define an interpolating family of independent spacing models, which encompasses both the ES and US cases, by taking as function f (s) the Gamma distribution αg α (αs), for α > 0. For example, when α is an integer, each s i is distributed as a sum of α i.i.d. exponential random variables, each with mean α -1 . The ES case is, of course, α = 1, while, due to the central limit theorem, the US model is the limit as α tends to infinity. This generalised model appears to be treatable with the same technique that we employed for the pure ES case whenever α is a half-integer: the generating function of the average cost can be computed exactly in this case, and involves more and more complicated hypergeometric functions as α grows (namely, if α = k/2, we have a k F k-1 hypergeometric function). Performing singularity analysis over such functions is a challenging task, which builds on classical results on generalised hypergeometric functions (due to Nørlund and Bühring), that we leave for future work.

On a parallel but distinct research direction, Dyck matchings may provide a fruitful framework to study other interesting features of the assignment problem, such as the ground-state degeneracy at p = 1 or the properties of the cycle decomposition of optimal matchings, w.r.t. the natural ordering along the domain segment. p Scaling(p)

0 1 2 -1 1 1 2 1 2 N N 1-p √ N log N √ N N 1-p 2 Figure 5
: Scaling exponent of the average optimal cost as a function of p, in the case of cost function c(|x|) = +|x| p (that is, attractive case for p > 0 and repulsive case for p < 0). In our conjectured result. In black, results from [START_REF] Caracciolo | Selberg integrals in 1d random euclidean optimization problems[END_REF]. Notice that we rescaled our result by a factor (2N + 1) -p , i.e. we plotted the result for Ω = [0, 1].

A The coefficients v N,k

The goal of this section is to compute the coefficients v N,k , crucially used in the calculation of the average cost of the Dyck matching, starting with equation [START_REF] Graham | Concrete mathematics[END_REF]. These coefficients count, among the N edges of all the possible 2N N Dyck matchings on 2N points, the number of edges e of length e = 2k + 1. That is, v N,k (N -1)! 2 2(2N -1)! is the probability that, taking a random Dyck matching π Dyck uniformly, and an edge e ∈ π Dyck uniformly, we have e = 2k + 1.

Dyck matchings correspond to Dyck 'bridges', w.r.t. the notation introduced in Section 2.1. We proceed with the calculation by first computing the analogous quantity on a restricted ensemble, associated to Dyck 'excursions' (that is, the ordinary Dyck paths), which are Dyck bridges satisfying the extra condition j i=1 σ i ≥ 0 for all 1 ≤ j ≤ 2N . In the whole class of Dyck paths of length 2N there are

r N,k := N -k + 1 2 C k C N -k = 1 2 C k B N -k (66)
edges of length e = 2k + 1 (http://oeis.org/A141811), with 0 ≤ k ≤ n -1. These numbers obey the recursion relation, which determines them univocally (together with the initial conditions)

r N,k = C k C N -k-1 + N -1 m=0 [r m,k C N -m-1 + r N -m-1,k C m ] . (67)
The recursion can be understood in terms of a first-return decomposition. If we decompose the path into its first return, i.e. the portion between its left endpoint and its first zero (say at position 2m + 2, 0 < m < n -1), and into its tail, i.e. the remaining portion of the path on the right, then:

• the first term counts all the paths in which the link between the first step and the first zero is of the required length. The multiplicity of paths in which this situation arise is given by all the possible paths composing the first excursion times all the possible paths composing the tail;

• the sum counts, for all the possible positions of the first zero, the possible links of the required length hidden in the first excursion or in the tail of the path. To count links of the required length hidden in the first excursion, one can use r m,l itself, times all the possible tails C n-m-1 . The tail case is symmetric.

It is easy to prove by induction that

r N,k = C k R N -k-1 (68)
and the recursion reduces to

R s = C s + 2 s-1 m=1 C s-m R m-1 . (69)
By introducing the generating function

R(z) := n≥0 R n z n (70)
we get the equation

R(z) = C(z) + 2 z C(z) R(z) (71)
and therefore

R(z) = C(z) 1 -2 z C(z) = C(z)B(z) = 1 2 z 1 √ 1 -4 z -1 = - 1 2 z + 1 2 z + n≥0 B n+1 2 z n = n≥0 B n+1 2 z n (72) indeed n k=1 C k B n-k = B n+1 2 . ( 73
) It follows that R N -k-1 = B N -k 2 (74)
as announced.

The preliminary computation of the r N,k coefficients suggests to use the same technique for the v N,k , and provides an ingredient to write a recursion for

B Singularity analysis

Singularity analysis is a technique that allows to extract information on the coefficients of a generating function f (z) when an explicit series expansion around z = 0 is not available. Roughly speaking, two main principles hold (see e.g. [38, pg. 227]):

1. the moduli of the singularities of f dictate the asymptotic exponential growth of its coefficients

. If z = a is a singularity of f (z) = n≥0 f n z n , then f n ∼ |a| -n ;
2. the nature of the singularities of f dictate the asymptotic sub-exponential growth of its coefficients, i.e. they determine the (typically polynomial or logarithmic) function θ(n) such that f n ∼ |a| -n θ(n).

We will specialise this analysis to the case of a single singularity, along the real positive axis, which is pertinent to series with positive coefficients, and no oscillatory behaviour. Generalizations of these principles (and of the related theorem below) for the case of multiple singularities at the same radius hold as well, but in our case are not relevant and will not be discussed.

The main result that we are going to need is a theorem (see [START_REF] Flajolet | Analytic combinatorics[END_REF]thm. VI.4]) that states that if f (z) is a "well-behaved" complex function analytic in 0, with a singularity at z

= ζ + i0 such that f (z) = σ(z/ζ) + o(τ (z/ζ)) (82)
for some functions σ = n≥0 σ n z n and τ = n≥0 τ n z n in the span of the reference set

S = (1 -z) α 1 z log 1 1 -z β α, β ∈ C , ( 83
) then f n = ζ -n σ n + o(ζ -n τ n ) . (84)
Here "well behaved" means that there exists an indented disk of radius bigger than ζ, with the indentation that specifically excludes z = ζ + i0, where f (z) can be analytically continued. This means that the theorem is applicable to functions with very general singularities (isolated poles, branch cuts, . . . ), and in particular to hypergeometric functions. The reference set S is composed of functions whose expansion can be computed exactly thanks to generalizations of the binomial theorem. These functions are ubiquitous in series expansions around poles of complex functions, so that the theorem is extremely versatile.

In our specific case of the ES model, the generating function to study is of the form where γ is the Euler-Mascheroni constant and ψ 0 is the digamma function. The limit is to be performed with care: each term must be written as a function of = p -1 2 and expanded in powers series. The expansion of the hypergeometric functions must be performed using their definition. When everything is expanded, o( ) are discarded taking the limit → 0, and the leading terms in the (1 -4z) are found by taking n = 0 in the sum of the hypergeometric function definition.

C Transportation order

Let us introduce a notion of ordering among distributions with the same average, which is a version analogue (but slightly different) from the several ones already existing in literature (such as second-order stochastic dominance, or variability order, or convex order, see e.g. [START_REF] Colonius | Mathematical Models of Perception and Cognition Volume I: A Festschrift for[END_REF]). We shall call our order the transportation order.

If f (x) and g(x) are probability distributions on R with the same average, we say that f g if there exists a non-negative function h(x, y) such that, for all x, dy h(x, y) = 1 dy y h(x, y) = x (92) and g(y) = dx h(x, y)f (x) .

We call h the transportation map of the pair (f, g).

We have two crucial facts:

Lemma 6 Convolution preserves transportation order, that is, if f 1 g 1 and f 2 g 2 , then f 1 * f 2 g 1 * g 2 .

Proof. Let us call h 1 and h 2 the associated transportation maps. We have

(f 1 * f 2 )(x) = dx f 1 (x )f 2 (x -x )
= dx dy dy h 1 (x , y )h 2 (x -x , y -y )f 1 (x )f 2 (x -x ) (94) and (g 1 * g 2 )(y) = dy g 1 (y )g 2 (y -y ) = dx dy dx h 1 (x , y )h 2 (x -x , y -y )f 1 (x )f 2 (x -x ) .

(95) This shows that the function

h(x, y) =    (h 1 f 1 ) * (h 2 f 2 ) (x, y) (f 1 * f 2 )(x) (f 1 * f 2 )(x) > 0 0 (f 1 * f 2 )(x) = 0 (96)
(where convolution of (hf ) is both over x and y) is a candidate transportation map for the pair (f 1 * f 2 , g 1 * g 2 ), and is at sight a non-negative function. We shall only verify that the conditions (92) are satisfied. We have dy h(x, y) = 1 (f 1 * f 2 )(x) dx dy dy h 1 (x , y )h 2 (x -x , y -y

)f 1 (x )f 2 (x -x ) = 1 (f 1 * f 2 )(x)
dx dy 1 h 1 (x , y 1 ) dy 2 h 2 (x -x , y 2 ) The average of convex/concave observables is monotone w.r.t. transportation order, that is, if f g and A(x) is convex, then dx A(x)f (x) ≤ dx A(x)g(x), and if A(x) is concave then the opposite inequality holds.

× f 1 (x )f 2 (x -x ) = 1 (f 1 * f 2 )(x) dx f 1 (x )f 2 (x -x ) = 1 (
Proof. Let us call h the transportation maps. We have Φ(x) := dx A(x)g(x) -dx A(x)f (x) = dy (A(y) -A(x))h(x, y)f (x) (99) If A(x) is convex, then for all x there exists m(x) such that A(y) ≥ A(x) + m(x)(y -x), thus Φ(x) ≥ dy m(x)(y -x)h(x, y)f (x) (100)

As dy (y -x)h(x, y) = 0 for all x, and f (x) is non-negative, we get Φ(x) ≥ 0, as was to be proven. For the concave case, of course it suffices to consider the convex function -A(x).

Figure 2 :

 2 Figure 2: The Dyck matching π Dyck associated to the Dyck bridge σ in the example of Figure 1.

k

  , this can be computed exactly both in the US and ES cases: in the US case S (p) k = (2k + 1) p , as in fact |e| = 2k + 1 = e deterministically, while in the ES case S (p) k

9 Figure 3 :Figure 4 :

 934 Figure3: Ratio of the average cost of optimal matchings over that of Dyck matchings as a function of N . The number of simulated instances at each value of (p, n) is 10000, whenever n ≤ 4000, and 5000, whenever n = 5000 or 6000.

F 2 ∈ [-1 2 , 1 2 ] 1 -

 221 z) ∈ span S is singular at z = 1, and F = 2 F 1 is the (2study the hypergeometric function around z = 1, a celebrated 'inversion formula' due to Gauss is available)Γ(c -a -b) Γ(c -a)Γ(c -b) F a, b a + b + 1 -c 1 -z + Γ(c)Γ(a + b -c) Γ(a)Γ(b) (1 -z) c-a-b F c -a, c -b c + 1 -a -b 1 -z(89)This formula restates the seeked expansion around z = 0 in terms of an expansion near the singularity at z = 1. As the hypergeometric function is analytic in z = 0, the singular behaviour at z = 1 of the right-hand side combination is described by the power-law prefactors in the inversion formula.In our specific case, a = p+1 2 , b = p+2 2 and c = 2 with p ∈ [0, 1], giving c -a -b = 1-2p . Thus, the leading terms of the expansion of f (z) are:f (z) = s(4z) Γ(c)Γ(c -a -b) Γ(c -a)Γ(c -b) + Γ(c)Γ(a + b -c) Γ(a)Γ(b) (1 -4z) c-a-b + Θ((1 -4z), (1 -4z) c-a-b+1 ) . (90)The above expression is valid only for p = 1 2 . A limit procedure combines the diverging Γ's and the (1 -4z) term to give f (z) = s(4z) 4z) ln(1 -4z)) . (91)

2 )

 2 97)anddy (y -x)h(x, y) = 1 (f 1 * f 2 )(x)dx dy dy× ((y -y ) -(x -x ) + y -x )h 1 (x , y )h 2 (x -x , y -y )f 1 (x )f 2 (x -x ) = 1 (f 1 * f 2 )(x) dx f 1 (x )f 2 (x -x ) × dy 1 (y 1 -x )h 1 (x , y 1 ) dy 2 h 2 (x -x , y 2 ) + dy 1 h 1 (x , y 1 ) dy 2 (y 2 -(x -x ))h 2 (x -x , y

(1-p)(1-2p) -

the v N,k :

we get

We introduce now the generating function

to get the relation

which is our seeked result. We can finally check that the recursion above is indeed satisfied, as


Impact of machine stiffness and heat treatments on crack propagation instabilities in an

-

  Broken coarse Mg 2 Si in dimples -Nucleation controlled by coarse precipitates (Mg 2 Si & IMF) No difference in zone with and without pop-in stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy No preferential localization of coarse particles: mainly transgranular fracture Intergranular fracture around the small grains stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy Ductile failure, very rough crack surface Heterogeneous presence of large clusters of porosity at the crack tip Design of an assembly allowing to decrease the stiffness 𝑲 𝒕 Use of belleville washers, to increase the compliance in compression stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy 'Load' approach Instability criterion ? 𝑡 = 𝑢 𝑚 + 𝑢 𝑠 = 𝑢 𝑚 + 𝑢 𝑠 𝑒 + ≤ -𝐾 𝑡 (𝑁, 𝑢 𝑠 𝑝 ) instability 16 th European Mechanics of Materials Conference | March 26-28, 2018 | 18 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy 𝑡 𝑁, 𝑢 𝑠 𝑝 ≤ 0 ? Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy Excellent agreement between the predictions of the criterion and the tests General small-scale yielding case Reasoning developed by Paris et al., 1979 Machine stiffness Good agreement between the predictions of the criterion and the tests Experimental pop-ins seem to stop too late : some dynamic effects are not considered 𝑇 𝑚𝑎𝑡 = 𝑑𝐽 𝑚𝑎𝑡 𝑑𝑎 ≤ 𝑇 𝑎𝑝𝑝 (𝑃, 𝑎) Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy Conclusions : • Pop-ins studied are purely mechanical crack growth instabilities • Result from the interaction of the material behavior (favored by a decrease of tearing modulus) and imposed loading (favored by a high compliance of the total system) (𝑃, 𝑎) = 𝑔(𝑃, 𝑎) 𝑎 𝑒𝑓𝑓 = 𝑎 + 𝑟 𝑦 𝑇 𝑚𝑎𝑡 = 𝑑𝐽 𝑚𝑎𝑡 𝑑𝑎 ≤ 𝑇 𝑎𝑝𝑝 (𝑃, 𝑎 𝑒𝑓𝑓 ) = 𝑔(𝑃, 𝑎 𝑒𝑓𝑓 1 -𝐸 𝛾𝜋𝜎 𝑦 2 𝑔(𝑃, 𝑎 𝑒𝑓𝑓 ) Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy Aluminium 6061-T6 Age-hardened alloy → 4 aging times (175 °C) to obtain 4 metallurgical states: stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy • Pilotage en longueur d'arc : méthode incrémentale de Riks • Principe : ajouter aux équations d'équilibre une équation imposant la longueur du vecteur incrémental dans le plan charge/déplacement -> le chargement appliqué devient une variable additionnelle du problème • Rajout d'un ressort à raideur variable dans la simu 2D : Mechanics of Materials Conference | March 26-28, 2018 | 42 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy • Méthode : -Extraction de la contrainte principal 𝜎 𝐼 -𝑓 𝑛 = 𝐴(𝜎 𝐼 ) 𝑝 -𝐴(𝜎 𝐼 ) = 𝐴 𝑛0 + 𝜎 𝐼 𝜎 𝑀 • Paramètres d'optimisation : -q 1 (Tvergaard). Potentiel plastique : -𝐴 𝑛0 -𝜎 𝑀 -fact (facteur géométrique permettant de dilater le maillage fin) 16 th European Mechanics of Materials Conference | March 26-28, 2018 | 43 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy • Zebulon • Eléments quadrangles (8 noeuds) linéaires à intégration sélective • Comparaison 2D déf planes -3D validée • Différents traitements thermiques : -Loi élastoplastiques (Voce) différentes -Lois d'endommagement (Gurson et nucléation par les contraintes) identiques 2D • Après optimisation des paramètres :

th European Mechanics of Materials Conference | March 26-28, 2018 | 10

th European Mechanics of Materials Conference | March 26-28, 2018 | 12

th European Mechanics of Materials Conference | March 26-28, 2018 | 13

th European Mechanics of Materials Conference | March 26-28, 2018 | 14

th European Mechanics of Materials Conference | March 26-28, 2018 | 15

th European Mechanics of Materials Conference | March 26-28, 2018 | 16 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

th European Mechanics of Materials Conference | March 26-28, 2018 |

th European Mechanics of Materials Conference | March 26-28, 2018 | 19

th European Mechanics of Materials Conference | March 26-28, 2018 | 20 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

th European Mechanics of Materials Conference | March 26-28, 2018 | 23 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

th European Mechanics of Materials Conference | March 26-28, 2018 | 35 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

th European Mechanics of Materials Conference | March 26-28, 2018 | 38 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

th European Mechanics of Materials Conference | March 26-28, 2018 | 40 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

th European Mechanics of Materials Conference | March 26-28, 2018 | 41

th European Mechanics of Materials Conference | March 26-28, 2018 | 44 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

No PLC effect (contrary to the literature)


P Castany

Elaboration of oxide dispersion strengthened Fe-14Cr

steel by selective laser melting a new route for new applications

  Direction de l'Energie Nucléaire Direction aux Activités Nucléaires de Saclay Département des Matériaux pour le Nucléaire Service 2018 MRS Spring Meeting -April 2 -6, 2018 -Phoenix, Arizona Elaboration of oxide dispersion strengthened Fe-14Cr steel by selective laser melting : a new route for new applications Mill steel powder with oxides powder Aim : Insertion of Y, Ti and O atoms in solution solid Non-spherical powder Oxide Dispersion Strengthened (ODS) stainless steels are being considered as materials for fast breeder reactor, an application that requires a low swelling rate and high creep strength in the temperature range of 400 -800°C. Conventional processing techniques, which involve melting such as foundry, tend to be avoided to produce ODS alloys since oxide particles can slag off into the molten pool which is detrimental for alloys creep strength. That is why ODS materials are usually produced by powder metallurgical process : Consolidation of the powder by hot extrusion or hot Isostatic Pressing Limitation in final shape of materials • Homogenous distribution of precipitates • Precipitates rich in Y, Ti and O • Mean diameter of precipitates : 30 nm Influence of process parameters on grain's size Power Grain's size Speed Grain's size HD Grain's size d 50 powder Density Microstructure Influence of powder size on density • ODS stainless steel can successfully be produced by SLM process • Innovative microstructure is obtained thanks to a good control of the process parameters • A good creep resistance is expected thanks to micrometric grains and homogenous distribution Consolidation of the powder by selective laser melting Overcome design limitations Consolidation of the powder Main objective : generate fine dispersion of precipitates inside the material to increase creep resistance • Columnar grains along the building direction (BD) • Microstructure very different than microstructure coming from conventional route IPF map of as-extruded ODS steel A. García-Junceda et al., 2012 SEM images of cross-sections of SLM builds viewed in two different orientations Influence of process parameters on texturation • Strong fiber texture along building direction {100} Influence of process parameters on density To obtain a dense ODS steel : • Power > 175 W • HD ~ track's width • Speed < 200 mm/s Pierre-françois Giroux 1 , Fernando Lomello 2 , Hicham Maskrot 2 , Philippe Castany 3 1 DEN-Service de Recherches Métallurgiques Appliquées, CEA, Université Paris-Saclay, F91191 Gif-sur-Yvette, France 2 DEN-Service d'Etude Analytiques et de Réactivité des Surfaces, CEA, Université Paris-Saclay, F91191 Gif-sur-Yvette, France 3 ISCR/CM -Institut des Sciences Chimiques de Rennes, INSA, F35708 Rennes Perspectives • Study the influence of process parameters on precipitation • Perform mechanical test : tensile tests, Charpy impact tests and creep tests • Study the influence of process parameters on mechanical properties