François Baccelli

David Coupier

Viet Chi Tran

Semi-infinite paths of the 2d-Radial Spanning Tree

Keywords: stochastic geometry, random tree, semi-infinite path, asymptotic direction, competition interface AMS: 60D05

We study semi-infinite paths of the radial spanning tree (RST) of a Poisson point process in the plane. We first show that the expectation of the number of intersection points between semi-infinite paths and the sphere with radius r grows sublinearly with r. Then, we prove that in each (deterministic) direction, there exists with probability one a unique semi-infinite path, framed by an infinite number of other semi-infinite paths of close asymptotic directions. The set of (random) directions in which there are more than one semi-infinite paths is dense in [0, 2π). It corresponds to possible asymptotic directions of competition interfaces. We show that the RST can be decomposed in at most five infinite subtrees directly connected to the root. The interfaces separating these subtrees are studied and simulations are provided.

Introduction

In this paper, we are interested in semi-infinite paths of the 2d-Radial Spanning Tree (RST) introduced in [START_REF] Baccelli | The radial spanning tree of a Poisson point process[END_REF]. Let us consider a homogeneous Poisson point process (PPP) N on R 2 (endowed with its usual Euclidean norm |.|) with intensity 1. Throughout this paper, N is considered in its Palm version: it a.s. contains the origin O. The RST is a random graph T (N ) (or merely T ) defined as follows. Its vertex set is N . Its edge set E contains each pair {X, Y }, X, Y ∈ N and X = O such that

|Y | < |X| and N ∩ B(O, |X|) ∩ B(X, |X -Y |) = ∅ (1)
(where B(c, r) denotes the open ball with center c and radius r). For any X ∈ N \ {O}, there is a.s. only one Y ∈ N satisfying [START_REF] Athreya | Random directed trees and forest -drainage networks with dependence[END_REF]. Among the vertices of N ∩ B(O, |X|), this is the closest to X. This vertex is denoted by A(X) and called the ancestor of X. With an abuse of notation, for an edge e, we call ancestor of the edge the endpoint that is the ancestor of the other endpoint, which we call the descendant of the edge. The ancestor of e is the endpoint of e that is closer from O. With probability 1, the graph T admits a tree structure (there is no loop) rooted at the origin O. For convenience, we set A(O) = O.

A sequence (X n ) n≥0 of vertices of N is a semi-infinite path of the RST T if, for any n, X n is the ancestor of X n+1 . A semi-infinite path (X n ) n≥0 has asymptotic direction θ ∈ [0, 2π) if

lim n→∞ X n |X n | = e iθ 1
(by identifying R 2 with the complex plane C).

Radial random trees in the plane have been studied in many other papers, including Pimentel [START_REF] Pimentel | Multitype shape theorems for first passage percolation models[END_REF], Bonichon and Marckert [START_REF] Bonichon | Asymptotic of geometrical navigation on a random set of points of the plane[END_REF] or Norris and Turner [START_REF] Norris | Hastings-levitov aggregation in the small-particle limit[END_REF]. The main difficulty in the case of the RST, is that the local rule (1) used for selecting the ancestor implies complex dependences. The latter make it difficult to exhibit natural Markov processes and prevent a direct use of martingale convergence theorems or Lyapunov functions.

However, our study can rely on the following result of [2, Theorem 2.1] on the RST:

Theorem 1. The following properties hold almost surely: (i) Every semi-infinite path of T has an asymptotic direction;

(ii) For every θ ∈ [0, 2π), there exists at least one semi-infinite path with asymptotic direction θ;

(iii) The set of θ's in [0, 2π) such that there is more than one semi-infinite path with asymptotic direction θ is dense in [0, 2π).

This result is based on a clever method due to Howard and Newman [11, section 2.3] proving that the above properties hold for any deterministic tree that satisfies some straightness condition, which is shown to be a.s. satisfied for the RST ([2, Theorem 5.4]).

Understanding finer structural properties of radial random trees, such as the asymptotic directions of their infinite branches or the shape of the interfaces that separate subtrees, has been a recurrent question. See for instance [START_REF] Coupier | Multiple geodesics with the same direction[END_REF][START_REF] Coupier | Coexistence probability in the last passage percolation model is 6-8 log 2[END_REF][START_REF] Coupier | Stochastic domination for the last passage percolation tree[END_REF] for results on the geodesics and interfaces of the last passage percolation tree. The aim of the present paper is to investigate these questions in the RST.

Our first result concerns the number of intersection points between semi-infinite paths of the RST T and the sphere with radius r centered at the origin; its expectation tends to infinity but slower than r (Theorem 2). The proof is based on the local approximation of the RST, far enough from the origin, by the Directed Spanning Forest (DSF). See [START_REF] Baccelli | The radial spanning tree of a Poisson point process[END_REF] for details. Moreover, it has been proved recently ([7, Theorem 8]) that there is no bi-infinite path in the DSF. This allows us to conclude.

Subsequently, we focus our attention on semi-infinite paths with deterministic directions. Proposition 5 states that, for any given θ ∈ [0, 2π), there is almost surely exactly one semiinfinite path with direction θ. Let γ 0 be the one corresponding to θ = 0. Proposition 5 provides a further description of the subtree of the RST made up of γ 0 and all the branches emanating from it.

Finally, we study the subtrees of the RST rooted at the children of O. To do it, each of these subtrees is painted with a different color. This process produces the Colored RST. Each of these colored subtrees can be bounded or not. Since the origin can have at most 5 descendants with probability 1, there are at most 5 distinct unbounded subtrees rooted at O. We prove in Theorem 8 that their number may be equal to 1, 2, 3, 4 or 5 with positive probability. The border between two colored subtrees is called competition interface. Any unbounded competition interface admits an asymptotic direction (Proposition 9). This direction is random and corresponds to the one of (at least) two semi-infinite paths, as in Part (iii) of Theorem 1.

It is worth pointing out here that our proofs strongly rely on the planarity of the RST and the non-crossing property of its branches (see Lemma 14 in appendix). They cannot be carried to an arbitrary dimension.

The paper is organized as follows. In Section 2, the sublinear character of the expected number of intersection points between semi-infinite paths and the sphere with radius r is established. Section 3 contains results on semi-infinite paths with deterministic directions. The colored RST and competition intefaces are defined in Section 4. Finally, open questions and numerical studies are gathered in Section 5.

Sublinearity of the number of semi-infinite paths

Let r be a positive real number. Let us denote by χ r the number of intersection points of the sphere S(O, r) = {re iθ , θ ∈ [0, 2π)} with the semi-infinite paths of the RST. The main result of this section states that the expectation of χ r is sublinear. Theorem 2. The following limit holds:

lim r→∞ E χ r r = 0 .
The idea of the proof is as follows. For r > 0, we introduce the points A r = re i/r and B r = re -i/r of the sphere S(O, r). In the sequel, we will denote by [A r , B r ] the line segment with extremities A r and B r and by a(A r , B r ) = {re iθ , θ ∈ [-1/r, 1/r]} the arc of S(O, r) with extremities A r and B r and containing the point (r, 0). This arc is by construction of length 2. We denote by χ r the number of intersection points between semi-infinite paths of the RST and a(A r , B r ). By the rotational invariance of the PPP N , E(χ r ) = πr E( χ r ). Hence, using an additional moment condition, the proof of Theorem 2 will be shown to amount to proving that lim r→∞ P( χ r ≥ 1) = 0 .

(

) 2
To prove [START_REF] Baccelli | The radial spanning tree of a Poisson point process[END_REF], notice that far enough from the origin, the RST can be locally approximated by a directed forest named Directed Spanning Forest (DSF, see [START_REF] Baccelli | The radial spanning tree of a Poisson point process[END_REF]). The DSF T -ex with direction -e x = -(1, 0) is a graph built on the PPP N and in which each vertex X has as ancestor the closest point of N among those with strictly smaller abscissa. This construction generates a family of trees, i.e. a forest, which bears similarities with other directed forests introduced in the literature (see e.g. [START_REF] Athreya | Random directed trees and forest -drainage networks with dependence[END_REF][START_REF] Ferrari | Competition interfaces and second class particles[END_REF][START_REF] Gangopadhyay | Random oriented trees: a model of drainage networks[END_REF]).

As r tends to infinity, the neighborhood of (r, 0) in the RST increasingly looks similar to the neighborhood of O in the DSF. Hence, the probability P( χ r ≥ 1) that there exists an infinite path crossing a(A r , B r ) is close to that of having a path of the DSF crossing {0} × [-1, 1] and very long in the direction e x . Such a phenomenon is rare since the DSF is known to have a.s. only one topological end [START_REF] Coupier | The 2d-directed spanning forest is almost surely a tree[END_REF].

In order to prove Theorem 2, we will need the two following lemmas whose proofs are deferred to the end of the section. Lemma 3. For any r > 0, the number of edges of the RST that intersect an arc of S(O, r) of length 1 has finite second order moment and moreover :

lim sup r→+∞ E( χ 2 r ) < +∞ .
Lemma 4 specifies how the RST is approximated by the DSF: far from the origin (around the point (r, 0)) and locally (for the neighborhood of radius r α of (r, 0)). Notice that since the distribution of the DSF is invariant by translation along e x , T -ex ∩ B((r, 0), r α ) and T -ex ∩ B(O, r α ) have same distribution. Lemma 4. Let T and T -ex respectively denote the RST and DSF of direction -e x constructed on the same PPP N . Then, for 0 < α < 1/3:

lim r→+∞ P T ∩ B((r, 0), r α ) = T -ex ∩ B((r, 0), r α ) = 1.
(

) 3
The approximation also holds if we replace r α by a constant radius R.

Proof of Theorem 2.

Step 1: Let us prove [START_REF] Baccelli | The radial spanning tree of a Poisson point process[END_REF]. First of all, notice that all the paths which intersect the arc a(A r , B r ) necessarily intersect the segment [A r , B r ] (the converse is not necessarily true). The segment [A r , B r ] is perpendicular to the horizontal axis, and all its points have abscissa r = r cos(1/r). Its length is 2r sin(1/r) ≤ 2. Heuristically, the event { χ r ≥ 1} (consisting in the existence of at least one semi-infinite path crossing a(A r , B r )) is hence close to the existence of a path of the RST crossing the vertical segment [A r , B r ] and then surviving until a large radius. For R > 0, let us hence consider the event where there exists a path of the RST crossing { r} × [-1, 1] ⊃ [A r , B r ] before intersecting the sphere S((r, 0), R).

Our purpose is to show that the probability of this event is close to the probability that in the DSF T -ex , there exists a path intersecting {0} × [-1, 1] and then S(O, R) ∩ {x > 0}. To show that such an approximation holds, let us prove that our event is local in the sense of Lemma 4.

Let us consider a path of the RST crossing { r} × [-1, 1] and afterwards S((r, 0), R), i.e. towards descendants as is described below. From this path, we can extract a sub-path (Z 0 , . . . , Z n ) crossing only once { r} × [-1, 1] (between Z 0 and Z 1 ) and S((r, 0), R) (between Z n-1 and Z n ). See Figure 1. We show that this path is included in the ball B(( r, 0), 2R), so that the local approximation of the RST by the DSF (see Lemma 4) holds.

If Z 0 is outside the ball B((r, 0), R), then B(Z 1 , |Z 1 -Z 0 |) contains B((r, 0), R/2) for R large enough. Consequently, the set B(O, r) ∩ B((r, 0), R/2)
is empty of points of the PPP N . So, Z 0 belongs to B((r, 0), R) with high probability as r, R tend to infinity (with r tending to infinity faster than R). The same is true about the endpoint Z n and the ball B((r, 0), 2R). To sum up, given ε > 0 and r, R large enough,

P( χ r ≥ 1) ≤ P   
there exists a path of the RST crossing {r} × [-1; 1] and afterwards S((r, 0), R), whose endpoints belong to B((r, 0), 2R). and the sphere S((r, 0), R). On this picture, Z 0 and Z n belong to B(( r, 0), 2R) which occurs with high probability.

Theorem 8 of [START_REF] Coupier | The 2d-directed spanning forest is almost surely a tree[END_REF] says each path of the DSF is a.s. finite towards descendants. Then, the probability in the right-hand side of (4) tends to 0 as R tends to infinity. This means that P( χ r ≥ 1) is smaller than 3ε, i.e. (2).

Step 2: Let us prove that E(χ r ) is sublinear. As mentioned at the beginning of the section, it is sufficient to show lim r→∞ E( χ r ) = 0. Since by the Cauchy-Schwarz inequality:

E χ r ≤ E χ 2 r P( χ r ≥ 1) ,
the desired limit follows from (2) if we prove that lim sup r→+∞ E( χ 2 r ) is finite, which is the result of Lemma 3.

2

The section ends with the proofs of Lemmas 3 and 4.

Proof of Lemma 3. Let A r and B r be as in the proof of Theorem 2. Let W r be the intersection point of the two tangents to S(O, r) that pass through the points A r and B r . See the left part of Figure 2.

The number of semi-infinite paths that cross a(A r , B r ) is upper bounded by the number χr + χ r of edges of the RST which intersect [A r , W r ] ∪ [W r , B r ], where χr (resp. χ r ) denotes the number of edges crossing [A r , W r ] (resp. [W r , B r ]) and whose ancestors belong to the same half plane delimited by the line supporting [A r , W r ] (resp. [W r , B r ]) as O. Since χr and χ r are identically distributed:

E( χ 2 r ) ≤ E(( χr + χ r ) 2 ) ≤ 4E( χ2 r ), (5)
and it is sufficient to show that lim sup r→∞ E( χ2 r ) is finite. By rotational invariance, the distribution of χr is also the distribution of the number of edges with ancestors of smaller abscissa and that cross the vertical segment I r = [(r, r tan(1/r)), (r, 0)]. With an abuse of notation, we The segment [X, A(X)] crosses I r (in bold) on J(X). On this picture, X is outside I r ⊕ B(0, c).

will denote again by χr the last random variable. Notice also that the length of I r is bounded by 2 as soon as r is sufficiently large. Let c > 2 + 3 √ 2 (a technical condition needed in the sequel), and let us use ⊕ for the Minkowski addition. Then:

χr = χ≤c r + χ>c r a.s. , (6)
where χ≤c r (resp. χ>c r ) denotes the number of these edges with descendants belonging to I r ⊕ B(O, c) (resp. being at a distance at least c from I r ). χ≤c r is upper bounded by Card(N ∩ (I r ⊕ B(O, c))) and admits a moment of order 2 that is bounded independently of r. It remains to study χ>c r . Our idea is that each long edge is accompanied by a large empty space, so that it is rare that many long edges intersect I r . Let us consider an edge [A(X), X] that crosses I r at J(X) and such that the distance from X to I r is larger than c. If X = (x, y), then let us consider z(X) the point with coordinates ([x] + 1, sign(y)[|y|]), where [x] denotes the integer part of x. Among the points with integer coordinates that have an abscissa larger than x and which are closer to the abscissa axis than X, z(X) is the point that is the closest to X. See the right part of Figure 2.

By construction, |X-z(X)| ≤ √ 2. Hence B(O, |z(X)|- √ 2) ⊂ B(O, |X|)
, where the radius of the first ball is positive as soon as r ≥ √ 2. Let us consider the ball

B(z(X), |z(X)-(r, 0)|-2-2 √ 2). For our choice of c, |z(X) -(r, 0)| -2 -2 √ 2 ≥ c - √ 2 -2 -2 √ 2 ≥ 0 and the radius is positive. If U ∈ B(z(X), |z(X) -(r, 0)| -2 -2 √ 2), then |U -X| ≤ |U -z(X)| + √ 2 ≤ |z(X) -(r, 0)| -2 - √ 2 ≤ |X -J(X)| ≤ |X -A(X)|, (7)
and thus

B(z(X), |z(X) -(r, 0)| -2 -2 √ 2) ⊂ B(X, |X -A(X)|). As a consequence, if we introduce Λ(z, r) = B(O, |z|) ∩ B(z, |z -(r, 0)| -2 -2 √ 2) for z = (z x , z y ) ∈ Z 2 and r sufficiently large, we have that Card(N ∩ Λ(z(X), r)) ≤ Card(N ∩ B(O, |X|) ∩ B(X, |X -A(X)|)), the latter quantity being 0 since [A(X), X] is an edge of the RST, implying that there is no point of N in Λ(z(X), r). Thus, for r ≥ √ 2: X>c r ≤ Y r := z=(zx,zy)∈Z 2 zx≥r 1 {Λ(z,r)∩N =∅} , a.s. ( 8
)
Notice that if r and r ′ are such that z x ≥ r ′ ≥ r, then Λ(z, r) ⊂ Λ(z, r ′ ). This implies that r → Y r is almost surely a decreasing function of r. Then, if we fix r 0 ≥ √ 2, ∀r ≥ r 0 , X>c r ≤ Y r 0 . The volume of Λ(z, r 0 ) is of the order of |z| 2 and for a given integer ρ ≥ r 2 0 , the number of points z such that |z| 2 = ρ is of the order of √ ρ. Thus, for two positive constants C and C ′ :

E Y r 0 = z=(zx,zy)∈Z 2 zx≥r 0 P Λ(z, r 0 ) ∩ N = ∅ ≤ C ρ≥r 2 0 √ ρe -C ′ ρ < +∞. ( 9
)
It now remains to prove that E(Y 2 r 0 ) < +∞. For this, we compute [START_REF] Howard | Euclidean models of first-passage percolation[END_REF] for two positive constants C and C ′ . ( 9) and [START_REF] Howard | Euclidean models of first-passage percolation[END_REF] show that E(Y 2 r 0 ) < +∞ and this concludes the proof.

E Y r 0 (Y r 0 -1) = z=(zx,zy)∈Z 2 , z ′ =(z ′ x ,z ′ y )∈Z 2 zx≥r 0 , z ′ x ≥r 0 zx =z ′ x E 1 {Λ(z,r 0 )∩N =∅} 1 {Λ(z ′ ,r 0 )∩N =∅} ≤ 2 ρ≥r 2 0 z=(zx,zy)∈Z 2 , |zx| 2 =ρ z ′ =(z ′ x ,z ′ y )∈Z 2 , z ′ x ≥r 0 |z ′ |≤|z| P Λ(z, r 0 ) ∩ N = ∅ ≤ C ρ≥r 2 0 ρ 3/2 e -C ′ ρ < +∞
2

Proof of Lemma 4. We follow here the proof of Baccelli and Bordenave [2, Section 3.6], where the case of a fixed radius R is considered. Recall that T and T -ex are the RST and DSF with direction -e x , constructed on the same PPP N . We denote by A(X) and A -ex (X) the ancestors of X in T and T -ex . Let r > 0, α > 0 and β > 0.

P T ∩ B((r, 0), r α ) = T -ex ∩ B((r, 0), r α ) = P X∈N ∩B((r,0),r α ) A(X) = A -ex (X) ≤P N (B((r, 0), r α )) > r β + r β C sup X∈N ∩B((r,0),r α ) P A(X) = A -ex (X) ≤ exp -r β log r β-2α eπ + r β C r α + 1 r -r α ,
by using [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF]Lemma 11.1.1] for the first term in the r.h.s. and [2, Lemma 3.4] for the second term. The first term converges to 0 iff β > 2α and the second term converges to 0 iff α < 1 and β + α < 1. As a consequence, we see that for any α < 1/3 we can choose β > 2/3, so that both terms converges to 0 when r → +∞. 2

Semi-infinite paths in a given direction

In this section, we fix a direction θ ∈ [0, 2π) and are interested in the semi-infinite paths with asymptotic direction θ. Our first result (Section 3.1) refines Theorem 1 and states that there exists a.s. a unique semi-infinite path with direction θ. We deduce from this a precise description of the semi-infinite path with direction θ (Section 3.2).

For the proof, let us introduce further notation. We define as T X the subtree of T consisting of X = O and all its descendants, i.e. all the vertices of T that have X in their ancestry. This tree is naturally rooted at X. If T X is unbounded, then we can construct two particular semi-infinite paths that we call the right-most and left-most semi-infinite paths, γ X and γ X , of T X . The construction follows. Put X 0 = X. Let

K 0 = Card{Y ∈ N, A(Y ) = X 0 and T Y is unbounded }
be the number children of X 0 with infinite descendance. Since the number of children of a given vertex is a.s. finite (see [2, Section 3.3.2.]) and since X 0 has infinitely many descendants, K 0 ≥ 1 a.s. It is possible to rank these offspring X 1 0 , . . . , X K 0 0 by increasing order of the oriented angles A(X 0 )X 0 X k 0 for k ∈ {1, . . . , K 0 }. Define X 1 as the child of X 0 corresponding to the largest value of these angles. Iterating this construction, a semi-infinite path γ X = (X n ) n∈N rooted at X is built. In the same way, a semi-infinite path γ X rooted at X is constructed such that, among the semiinfinite paths of T X , γ X is the lowest one (in the trigonometric sense). Consequently, any given semi-infinite path in T X is trapped between γ X and γ X (in the trigonometric sense).

Uniqueness

Part (iii) of Theorem 1 ensures the existence of random directions with at least two semi-infinite paths. However, there is no more than one semi-infinite path with a deterministic direction (Proposition 5). This result completes Part (ii) of Theorem 1.

Proposition 5. For all θ ∈ [0, 2π), there a.s. exists exactly one semi-infinite path with asymptotic direction θ in the RST.

The idea of the proof of Proposition 5 is classical: see [START_REF] Howard | Euclidean models of first-passage percolation[END_REF] for first passage percolation models defined from homogeneous PPP on R 2 and [START_REF] Ferrari | Competition interfaces and second class particles[END_REF] for a directed last passage percolation model on the lattice Z 2 . Thanks to Fubini's theorem, we get that for Lebesgue almost every θ in [0, 2π), there is at most one semi-infinite path with asymptotic direction θ with probability 1. Actually, this statement holds for all θ ∈ [0, 2π) by the isotropic character of the PPP N .

Proof. Let us denote by U (θ) the event that there exist at least two different semi-infinite paths in the RST with asymptotic direction θ. Now, assume the event U (θ) occurs and let γ 1 and γ 2 be two such semi-infinite paths. Let X be a point of the PPP N belonging to γ 1 but not to γ 2 . Thus the semi-infinite sub-path of γ 1 rooted at X belongs to T X . Then, one of the two semi-infinite paths γ X and γ X is trapped between γ 1 and γ 2 , by planarity and since paths are non-intersecting (see Lemma 14 in appendix). So, it also admits θ as asymptotic direction. Let us denote by λ the Lebesgue measure on [0, 2π). We are interested in the Lebesgue measure of the set {θ; U (θ)} of directions θ ∈ [0, 2π) where the event U (θ) is satisfied. The previous remark implies:

Eλ{θ; U (θ)} = Ω 2π 0 1 U (θ) (ω) dθ dP(ω) ≤ Ω X∈N (ω) 1 T X unbounded 2π 0 1 γ X or γ X admits θ as asymptotic direction (ω) dθ dP(ω)

8

(N is a.s. countable). For a given point X ∈ N and a given ω ∈ Ω, the indicator function 1 γ X or γ X admits θ as asymptotic direction (ω) is equal to 1 for at most two different angles in [0, 2π). Its integral is then equal to zero. Using the Fubini's theorem,

2π 0 P(U (θ)) dθ = Eλ{θ; U (θ)} = 0 .
So, the probability P(U (θ)) is zero for Lebesgue a.e. θ in [0, 2π). Actually, this is true for every θ in [0, 2π) thanks to the isotropic character of the PPP N . Combining this with Part (ii) of Theorem 1, the announced result follows. 2

Further description of the semi-infinite path with direction 0

In the rest of this section, we discuss some consequences of Proposition 5. For any given θ ∈ [0, 2π), let us denote by γ θ the semi-infinite path of the RST, started at the origin and with asymptotic direction θ. It is a.s. well defined by Proposition 5. Since the distribution of the RST is invariant by rotation, we will henceforth assume that θ = 0.

Let us recall that χ r denotes the number of intersection points of a(A r , B r ) with the semiinfinite paths of the RST and that χ r → 0 in probability, by [START_REF] Baccelli | The radial spanning tree of a Poisson point process[END_REF]. We have Corollary 6. lim sup r→∞ χ r ≥ 1 a.s. Proof. Assume that there exists with positive probability a (random) radius r 0 such that χ r = 0 whenever r > r 0 . Let us work on the set where this event is realized. In this case, no semi-infinite path crosses the abscissa axis after r 0 . Then, we can exhibit two semi-infinite paths, say γ and γ ′ , respectively below and above the horizontal axis, and satisfying the following property: there is no semi-infinite path in the RST, different from γ and γ ′ , and trapped between them (in the trigonometric sense). Parts (i) and (ii) of Theorem 1 force γ and γ ′ to have the same asymptotic direction, namely 0. Such a situation never happens by Proposition 5. In other words,

P lim sup r→∞ χ r ≥ 1 = 1 .

2

From vertices of γ 0 (different from O), some paths (finite or not) emanate, forming together an unbounded subtree of the RST T for which γ 0 can be understood as the spine. The next results describe the skeleton of this subtree. Let us denote by V + ∞ and V - ∞ the set of points X ∈ N ∩ γ 0 \ {O} from which (at least) another semi-infinite path emanates, respectively above and below γ 0 . Of course, V + ∞ and V - ∞ may have a nonempty intersection.

Corollary 7.

1. Almost surely, V + ∞ and V - ∞ are of infinite cardinality. 2. For r > 0, let us denote by D r the set of directions α ∈ [0, 2π) with a semi-infinite path starting from a point X in

V + ∞ ∪ V - ∞ with modulus |X| > r.
Then, there a.s. exist two nonincreasing sequences (α r ) r>0 and (β r ) r>0 of positive r.v.'s such that

D r = [-α r , β r ] (modulo 2π) and lim r→+∞ α r = lim r→+∞ β r = 0 . 3. Let v r ∞ be the cardinality of (V + ∞ ∪ V - ∞ ) ∩ B(O, r). Then, lim r→∞ E v r ∞ r = 0 .
The first two assertions of Corollary 7 say that an infinite number of unbounded subtrees emanate from the semi-infinite path γ 0 . Each of them covers a whole interval of asymptotic directions whose length tends to 0 as its starting point (on γ 0 ) is far from the origin. The last assertion of Corollary 7 can be understood as follows: the expected density of points of γ 0 from which emanates another semi-infinite path is zero. For this purpose, recall that the cardinality of γ 0 ∩ B(O, r) is of order r (see [2, Theorem 2.5]).

Proof. On the event {V + ∞ is finite}, let us consider the point Y of V + ∞ of highest modulus. Let Y ′′ be the child of Y belonging to γ 0 . From the definition of V + ∞ , the set of points {X ∈ N, A(X) = Y, Y ′′ Y X > 0 and T X is unbounded} is non empty. The points of this set can be ranked by increasing values of Y ′′ Y Xs. Let Y ′ be the point of this set corresponding to the smallest positive angle Y ′′ Y X. In the subtree T Y ′ , we can define the lowest semi-infinite path γ Y ′ as defined in the beginning of Section 3. Thanks to Part (i) of Theorem 1, γ Y ′ has an asymptotic direction, say θ. Moreover, using the planarity and the non-crossing property of paths together with the definition of points Y , Y ′ , all the paths between γ 0 and γ Y ′ (in the trigonometric sense) are finite. Using Part (ii) of Theorem 1, we deduce that γ Y ′ and γ 0 have the same asymptotic direction, i.e. θ = 0. Now, by Proposition 5, such a situation never occurs. So the set V + ∞ is a.s. infinite. The same goes for V - ∞ .

Let us prove the second part of Corollary 7. For any r, let us consider the point X of smallest modulus among the points of γ 0 ∩ B(O, r) c . The semi-infinite paths γ X and γ X have a.s. asymptotic directions, say respectively -α r and β r (modulo 2π) with α r ≥ 0, β r ≥ 0. Hence, (α r ) r>0 and (β r ) r>0 are by construction non-increasing sequences of positive real numbers (by Proposition 5). Let us consider D r the set of directions corresponding to semi-infinite paths starting from points in V + ∞ ∪ V - ∞ with modulus greater than r. D r contains α r and β r defined above. The bi-infinite path obtained by concatenation of γ X and γ X divides R 2 into two unbounded regions. Since the paths of the RST cannot cross, D r is included in the real interval [-α r , β r ]. This also forces any given semi-infinite path with asymptotic direction α in [-α r , β r ] to go through the vertex X. By Part (ii) of Theorem 1, D r is then an interval. It follows D r = [-α r , β r ]. Finally, let us respectively denote by ᾱ and β the limits of sequences (α r ) r>0 and (β r ) r>0 . Let β > 0. Let X 0,β be the bifurcation point of γ 0 and the semi-infinite path with asymptotic direction β (whose existence and uniqueness are given by Proposition 5). Then, β ≥ β implies that β belongs to any interval D r . In other words,

P( β ≥ β) = lim r→∞ P(|X 0,β | > r) = 0 .
As a consequence, β is a.s. equal to 0. Similarly, we can prove ᾱ = 0.

The third part of Corollary 7 follows directly from the inequality v r ∞ ≤ χ r , where χ r counts the intersection points of S(O, r) with the semi-infinite paths of the RST, and Theorem 2. 2

The Colored RST

The aim of this section is to describe the subtrees of the RST T rooted at the children of O.

In order to distinguish them, let us start with allocating a color or a label (denoted by integers i, j, k . . .) to each child X of O. Recall for this purpose there are a.s. at most 5 (see Lemma 3.2 in [START_REF] Baccelli | The radial spanning tree of a Poisson point process[END_REF]). Then, we paint all the vertices of the subtrees T X with the color of X. This process provides a coloration of points of N \ {O}. Finally, each segment [X, A(X)], for X ∈ N \ {O}, is painted with the color of X. This can be done without ambiguity thanks to the planarity and the non-crossing property of paths. See Figure 3. There are several ways to label the subtrees of T rooted at O with the colors. We use the notation i, j, etc. when the labeling is not important and can be any labeling (a possibility among others is to start from the angle 0 (abscissa axis) and label by 1 the subtree rooted at the first descendant of O that we encounter when exploring the directions in the trigonometric sense). However, to take advantage of the exchangeability of the different colored trees, one may also proceed as follows. To each of the direct descendants of O, a uniform independent r.v. is attached. We then define the tree with color 1 as the tree consisting of the offspring of the descendant with the smallest uniform r.v. This amounts to choosing one of the descendants at random for the first tree. When we proceed so, we use the notation 1, . . . i, . . . for the labels. The next step is to define the competition interfaces, i.e. the borders between the subtrees of the RST rooted at the children of the origin. To do so, let us introduce the spatially embedded version of the RST T , denoted by T, as the following subset of R 2 :

T = X∈N \{O} [X, A(X)] .
For any positive real number r, the normalized trace of T over the sphere S(O, r) is

T r = 1 r (T ∩ S(O, r)) .
An element u of T r inherits its color from the element ru ∈ T. So, for any given color i, we denote by T r (i) the points of T r with color i. By the noncrossing paths property of the RST, the points of T r are "gathered" on the unit sphere S(O, 1) according to their color. This can be formalized as follows: for any r > 0,

θ 1 , θ 2 , θ 3 , θ 4 ∈ [0, 2π) such that (θ 1 -θ 3 )(θ 2 -θ 3 ) > 0, (θ 1 -θ 4 )(θ 2 -θ 4 ) < 0, e iθ 1 ,
e iθ 2 ∈ T r (i) and e iθ 3 , e iθ 4 ∈ T r , at least one of the two points e iθ 3 and e iθ 4 is of color i. For all (θ, θ ′ ) ∈ [0, 2π) 2 , let us denote by a(θ, θ ′ ) (resp. a(θ, θ ′ )) the arc of the unit sphere from e iθ to e iθ ′ in the trigonometric sense, without (resp. with) the end points e iθ and e iθ ′ . Furthermore, let T(i) be the subset of T with color i.

Definition 1 (Competition interfaces).

Given a couple of colors (i, j) with i = j, there exists at most one couple (θ, θ ′ ) ∈ [0, 2π) 2 such that e iθ ∈ T r (i), e iθ ′ ∈ T r (j) and a(θ, θ ′ ) ∩ T r = ∅ .

When such a couple (θ, θ ′ ) exists, we denote by θ r (i, j) ∈ [0, 2π)[ the (direct) angle of the line coming from O and bisecting the arc a(θ, θ ′ ) in two equal parts. In this case, the competition interface between the sets T(i) and T(j) is defined as the curve:

ϕ(i, j) = {re iθr(i,j) ∈ C, β(i, j) < r < ∂(i, j)} ,
where β(i, j) and ∂(i, j) are respectively defined as the infimum and the supremum of the set {r > 0, θ r (i, j) exists}.

From β(i, j) to ∂(i, j), the trees T(i) and T(j) evolve in the plane side by side, separated by the competition interface ϕ(i, j). The real numbers β(i, j) and ∂(i, j) can respectively be interpreted as the birth and death times of the competition interface ϕ(i, j). When ∂(i, j) = +∞, both sets T(i) and T(j) are unbounded. When ∂(i, j) < +∞, one of the two sets T(i) and T(j) is included in the closed ball B(O, ∂(i, j)), say T(j). In this case, ∂(i, j) coincides with another death time ∂(j, k) and two situations may occur according to the color k. Either k = i which means i is the only existing color outside the ball B(O, ∂(i, j)) and there is no competition interface beyond that ball. Or k is a third color (different from i and j). Then, the competition interface ϕ(i, k) extends ϕ(i, j) and ϕ(j, k) (until its de! ath time ∂(k, j)). Its birth time satisfies:

β(i, k) = ∂(i, j) = ∂(j, k) > 0 .
Let us remark that the application r → θ r (i, j) may be discontinuous. Finally, notice that θ r (i, j) = θ r (j, i) and that one may exist and the other not. So, we distinguish the interfaces e iθ e iθ ′ θ r (i, j) ∆ Figure 4: On the unit sphere, the black squares are points of T r (i) while black circles are points of T r (j).

The arc a(θ, θ ′ ) is divided in two equal parts by the line ∆ whose angle (represented in grey) is θ r (i, j).

ϕ(i, j) and ϕ(j, i).

Our first result states there can be up to five unbounded competition interfaces with positive probability. (b). The two distributions are different since the tree associated with each child of O is not necessarily unbounded. About its second line, let us point out the cases m ∈ {4, 5} are very rare (less than 2% of the simulations) compared with the cases m ∈ {2, 3} (more than 93%). Actually, configurations corresponding to m ∈ {4, 5} are very constrained around the origin, therefore rare.

Number of Interfaces

Our proof relies on Part (i) of Theorem 1. Thinning and local modification of the PPP are other ingredients.

Proof. We consider the cases m ∈ {1, . . . , 5} separately. m = 5 Our purpose is to construct a set of configurations of N , with a positive probability, on which there are five children of the origin O giving birth to infinite subtrees. For any 1 ≤ k ≤ 5, Part (i) of Theorem 1 ensures the existence a.s. of a semi-infinite path γ k with asymptotic direction 2kπ/5. Hence, for ε > 0 and with probability 1, there exists a (random) radius r k such that γ k is included in the cone section

C 2kπ/5,ε,r k = ρe iθ ; ρ > r k and |θ -2kπ/5| < ε
for any integer 1 ≤ k ≤ 5. Without loss of generality, we can require that γ k starts from a vertex X k ∈ N whose norm satisfies r k < |X k | ≤ r k + 1 and for r k to be a positive integer. Hence, writing

A ε (r 1 , . . . , r 5 ) =     
for any 1 ≤ k ≤ 5, there exists a semi-infinite path γ k included in the cone C 2kπ/5,ε,r k and starting from a vertex

X k satisfying r k < |X k | ≤ r k + 1     
, we get that for all ε > 0, there exist some (deterministic) radii r 1 , . . . , r 5 ∈ N * such that A ε (r 1 , . . . , r 5 ) occurs with positive probability. Let R = max{r k + 1; 1 ≤ k ≤ 5} and V ε (r 1 , . . . , r 5 ) be the complementary set of the five cones in the ball B(O, R):

V ε (r 1 , . . . , r 5 ) = B(O, R) \ ∪ 5 k=1 C 2kπ/5,ε,r k ∪ {O} .
Now, we are going to change the configuration of the PPP N in V ε (r 1 , . . . , r 5 ) in such a way that the X k 's are all of different colors. Let N = N ∩ V c ε (r 1 , . . . , r 5 ) be the thinned PPP obtained by deleting all the points of N belonging to V ε (r 1 , . . . , r 5 ) (e.g. Jacod and Shiryaev [START_REF] Jacod | Limit Theorems for Stochastic Processes[END_REF], II.4.b). It is crucial to remark that deleting the points of V ε (r 1 , . . . , r 5 ) does not affect the occurrence of A ε (r 1 , . . . , r 5 ). In other words, if N satisfies the event A ε (r 1 , . . . , r 5 ), so does N ;

P N ∈ A ε (r 1 , . . . , r 5 ) ≥ P (N ∈ A ε (r 1 , . . . , r 5 )) > 0 .
Now, let us consider a PPP N on V ε (r 1 , . . . , r 5 ) with intensity 1. Let us denote by r the minimum of the r k 's. The event N ∈ B ε (r 1 , . . . , r 5 ) is defined by the three following conditions.

(♣) For any k ∈ {1, . . . , 5}, if r k > r then for all integers r ≤ n ≤ r k -1, N B(ne i2kπ/5 , ε) = 1 , else N B(re i2kπ/5 , ε) ∩ B(O, r) = 1 .
(♦) For any k ∈ {1, . . . , 5} and for all integers n such that 0 (♥) The previous points are the only ones of N .

≤ n ≤ (R -r k -1)/2ε: N B (r k + 1 + 2nε)e i(2kπ/5±2ε) , ε ∩ V ε (r 1 , . . . , r 5 ) = 1 .
It is clear that the event N ∈ B ε (r 1 , . . . , r 5 ) occurs with positive probability, for all ε > 0.

Roughly speaking, the points of N introduced in (♣) form a chain from re i2kπ/5 to (r k -1)e i2kπ/5 , for any index k such that r k > r. See Figure 5. On Figure 5, imagine that R = r 4 + 1 is much larger than r = r 5 (indeed, we have no control on the r k 's). Henceforth, the semi-infinite path γ 5 could prefer to branch on the points of N introduced in (♣) and with direction 8π/5 rather than on X 5 . To prevent this situation from occurring, we contain each path γ k in the cone C 2kπ/5,3ε,r k thanks to the points of N introduced in (♦). These points form "landing runways" for the γ k 's (they may also change slightly the γ k 's). Let us denote by A ε and B ε the events A ε (r 1 , . . . , r 5 ) and B ε (r 1 , . . . , r 5 ). Then,

{ N ∈ A ε } ∩ { N ∈ B ε } ⊂ { N + N ∈ A 3ε ∩ B ε } ,
where N + N denotes the superposition of the two processes N and N . These two processes can also be assumed independent. In this case, N + N is still a PPP on R 2 . It follows:

P(N ∈ A 3ε ∩ B ε ) = P( N + N ∈ A 3ε ∩ B ε ) ≥ P( N ∈ A ε , N ∈ B ε ) ≥ P( N ∈ A ε )P( N ∈ B ε ) > 0 .
To conclude the proof, it remains to prove that the above event implies the existence of (at least) five unbounded subtrees of T with different colors. Actually, there will be exactly five ones since the degree of O is a.s. upperbounded by 5. Let us denote by Y k the point of N belonging to the ball B(re i2kπ/5 , ε). On the event N ∈ A 3ε ∩ B ε , the point X k is a descendant of Y k for any k. Hence, the subtrees rooted at Y 1 , . . . , Y 5 are unbounded. Finally, it suffices to remark the Y k 's have O as common ancestor. Indeed, each Y k is at distance from e i2kπ/5 smaller than ε. So,

|Y k+1 -Y k | ≥ |re i2(k+1)π/5 -re i2kπ/5 | -2ε ≥ 2r sin(π/5) -2ε ≥ 1.17r -2ε ,
which is larger than the maximal distance between Y k and O, i.e. r + ε, for ε small enough (using r ∈ N * ). m ∈ {3, 4} The previous construction applied to m ∈ {3, 4} allows us to state that with positive probability, the origin O has at least m descendants from which m unbounded trees arise. Now, so as to ensure the number of unbounded subtrees of different colors is exactly m, an additional precaution must be taken. Precisely, a fourth condition is added to the event N ∈ B ε : . . Y m . The origin O cannot be the ancestor of X. This proves that O is exactly of degree m and ends the proof. This latter argument no longer works when m is equal to 1 or 2. m = 2 Following the construction for m = 5, there exists r 1 and r 2 > 0 such that there exist with positive probability two semi-infinite paths γ 1 and γ 2 included in the cones C 0,ε,r 1 and C π,ε,r 2 . The following event has a positive probability:

• For a given increasing subsequence (θ j ) j∈N of [0, π) with a sufficiently small step, and for a sufficiently small ε > 0:

N B (r 1 ∧ r 2 )(1 + cos(θ j ))e iθ j , ε = 1, N B -(r 1 ∧ r 2 )(1 + cos(θ j ))e iθ j , ε = 1,
• For all integers n and m such that 0 ≤ n ≤ (r 2r 1 )/2ε and 0 ≤ n ≤ (r 1r 2 )/2ε, if they exist:

N B (r 1 + 2nε, 0), ε = 1, N B (0, r 2 -2nε), ε = 1. • The rest of B(O, r 1 ∨ r 2 ) is empty.
The idea is that in B(O, r 1 ∧ r 2 ), the points are roughly aligned following the reunion of two cardiods {ρ(θ) = ±(1 + cos(θ)), θ ∈ [0, π)}. Notice that this curve is differentiable at O with a horizontal tangent. If r 1 < r 2 , we add points along the line segment [(r 1 , 0), (r 2 , 0)]. If the θ j 's define a sufficiently fine subdivision of [0, π), then there cannot be more than two descendants of O by construction. We conclude as in the case m = 5. We remark that the two semi-infinite paths previously built have asymptotic directions opposed to the argument of the descendant of O from which they stem. m = 1 Since the RST T is unbounded, it suffices to prove that the origin O may have only one child with positive probability.

From z 1 = e iπ/3 , we build five complex numbers z 2 , . . . , z 6 by the following induction: for k ≥ 2,

z k = |z k |e ikπ/3 whose modulus |z k | is such that |z k -z k-1 | < |z k |. This construction forces |z k | > |z k-1 |. Let ε > 0 small enough such that |z k | -ε > |z k-1 | + ε.
Hence, the six balls B(z 1 , ε), . . . , B(z 6 , ε) do not overlap. Let Ω ε be the event

∀1 ≤ k ≤ 6, N (B(z k , ε)) = 1 and N (B(O, |z 6 | + ε)) = 7
(these 7 points including the origin). For all ε > 0, P(Ω ε ) > 0. So, it remains to choose ε > 0 small enough in order to ensure that, on the event Ω ε , the origin O has only one child. Let us denote by X k the point of N ∩B(z k , ε). Since N ∩B(O, |X 1 |) is reduced to O, the ancestor of X 1 is the origin O. Thus, for 2 ≤ k ≤ 6, we can choose ε such that

|X k -X k-1 | ≤ |z k -z k-1 | + 2ε < |z k -O| -ε ≤ |X k -O| .
This condition does not prove that X k-1 is the ancestor of X k , but it is not O. Let Ω(i, j) be the event corresponding to an unbounded competition interface ϕ(i, j). It occurs with a positive probability thanks to Theorem 8. Recall that ϕ(i, j) separates the two colored subtrees T(i) and T(j) according to the trigonometric sense. The next result states that ϕ(i, j) has a.s. an asymptotic direction on the event Ω(i, j). In other words, if T(i) is unbounded then it asymptotically behaves as a cone. Proposition 9. On the event Ω(i, j), the sequence (θ r (i, j)) r>β(i,j) converges a.s. to a random angle θ(i, j) ∈ [0, 2π).

Proof. Let us consider the event Ω(i, j) satisfied. Let X(i) and X(j) be the children of the origin of color i and j. On Ω(i, j), both subtrees T X(i) and T X(j) are unbounded. Recall that γ X(i) denotes the highest (in the trigonometric sense) semi-infinite path in T X(i) (see the proof of Proposition 5). In the same way, γ X(j) is the lowest one in T X(j) . On Ω(i, j), the region delimited by γ X(i) and γ X(j) (in the trigonometric sense) only contains finite paths. It may also contain some vertices of a third color (different from i and j). Then, by Parts (i) and (ii) of Theorem 1, γ X(i) and γ X(j) have the same asymptotic direction, say θ(i, j). To conclude it suffices to remark that the competition interface ϕ(i, j) is trapped between ! γ X(i) and γ X(j) . It then admits the same direction.

2

Proposition 9 says that every competition interface that separates the colors i and j has an asymptotic direction θ(i, j). The next proposition states a result on the distribution of the asymptotic directions, which remains however partial. Recall that we use the labels 1, . . . i . . . when the subtrees rooted at O are labeled randomly. If the marginal distributions of the θ(i, i + 1)'s are easy to obtain, it is not the case for the distributions of the θ(i, i + 1)'s which necessitate the knowledge of the joint distributions of the asymptotic directions (or equivalently, the distribution of the sectors between the competition interfaces). Section 5 provides numerical simulations and conjectures.

Proposition 10. Conditionally on having m infinite trees, and when the tree with color 1 is drawn randomly, the asymptotic directions θ(i, i + 1) are uniformly distributed on [0, 2π). Moreover the distribution of θ(i, j), on Ω(i, j), admits a density with respect to the Lebesgue measure on [0, 2π).

Proof. The first part results from invariance by translation and from the characterization of the Lebesgue measure on the circle as the unique measure invariant by any rotation. The event {θ(i, j) = α} implies the existence of at least two semi-infinite paths with the deterministic direction α. This is forbidden by Proposition 5. So, θ(i, j) has no atom (when it exists). In fact, the distribution of θ(i, j) is even absolutely continuous with respect to the Lebesgue measure λ on [0, 2π). Let A be a measurable subset of [0, 2π) such that λ(A) = 0. Let us denote by M the random number of interfaces that exist. Then for i = j, since θ(i, j) corresponds to one of the θ(k, l) when we relabel the subtrees rooted at O randomly:

P {θ(i, j) ∈ A} ∩ {M ≥ 2} ∩ Ω(i, j) = 5 m=2 P {θ(i, j) ∈ A} ∩ {M = m} ∩ Ω(i, j) ≤P i =j∈{1,...,m} {θ(i, j) ∈ A} ∩ {M = m} ∩ Ω(i, j) ≤ 5 m=2 i =j∈{1,...,m} P {θ(i, j) ∈ A} ∩ {M = m} ≤ 0, since λ(A) = 0. Radon-Nikodym's theorem concludes the proof. 2
We conclude this section by a corollary that states that the asymptotic directions of competition interfaces and of semi-infinite paths are related.

Corollary 11. The asymptotic direction of the competition interface ϕ(i, j) belongs to the (random) set D of directions with at least two semi-infinite paths. This set is a.s. dense in [0, 2π) and countable.

Proof. The fact that D is dense in [0, 2π) follows from Part (iii) of Theorem 1. It is also a.s. countable. Indeed, let us consider the set Γ of couples (γ 1 , γ 2 ) of different semi-infinite paths of the RST such that the region they delimit (in the trigonometric sense) contains only finite paths. Associating to each element (γ 1 , γ 2 ) of Γ the child in γ 1 of their bifurcation point, we get an injective function from Γ to the PPP N . Consequently, Γ is a.s. countable. Moreover, Parts (i) and (ii) of Theorem 1 allow to associate to each element (γ 1 , γ 2 ) of Γ their common asymptotic direction. This provides a surjective function from Γ onto the set D. Hence D is a.s. countable. 2

Distribution of the θ(i, j)'s and conjectures

In this section, we provide some clues and conjectures that may help understanding the distribution of the vector (θ(1, 2), . . . , θ(m -1, m), θ(m, 1)) of asymptotic directions of the interfaces, given that there are m unbounded trees and assuming that the latter are labeled by following the trigonometric sense.

For this purpose, it is equivalent to study the distribution of the sectors (φ(i + 1) := θ(i + 1, i + 2)θ(i, i + 1), i ∈ {1, . . . , m}) (with the convention that θ(m, m + 1) = θ(m, 1) and θ(m + 1, m + 2) = θ(1, 2)), which characterize the asymptotic width of the unbounded trees.

Proposition 12. Conditionally on having m unbounded trees, the angles between two interfaces are identically distributed with expectation 2π/m. Notice first that this rules out the possibility that the asymptotic directions θ(i, j)'s are independent uniform r.v. on [0, 2π). Else, the distributions of the sectors would be Beta distributions B(1, m) which expectation is 2π/(m + 1). There is thus interaction between the θ(i, j)'s.

Our conjecture is as follows:

Conjecture 13. Conditionally on m ∈ {2, 3, 4, 5}, the vector (φ(1), . . . , φ(m)) has a distribution close to a symmetric Dirichlet distribution of order m on [0, 2π) with parameter α = 1, Dir(m, [0, 2π), α).

Symmetric Dirichlet distributions of order m and parameter α > 0 on [0, 2π) are probability distributions on R m with a support in Λ = {η = (η 1 , . . . , η m ) ∈ R m , m i=1 η i = 2π} and with the following density with respect to the Lebesgue measure on Λ:

f (η 1 , . . . , η m ; α) = 1 B(α) m i=1 η i 2π α-1 ,
where

B(α) = +∞ 0 t α-1 e -t dt m +∞ 0 t mα-1 e -t dt
is the Beta function. If we had a Dirichlet distribution conditionally on m, the marginal distribution of the exchangeable sectors would be a Beta distribution B(α, (m -1)α) on [0, 2π) with expectation 2π/m. This would also show that the distributions of the asymptotic directions θ(i, j)'s depend only on the number m of unbounded trees and not on the number of offspring of O, which is a local phenomenon that is forgotten at large radii.

Let us illustrate the conjecture with simulations. We compute the angle between two interfaces and calibrate Beta distributions. Whereas there are no closed form for the maximumlikelihood estimates, the following moment estimates are as follows:

α = x 2π x(2π -x) Var(x) -1 , β = 2π - x 2π x(2π -x) Var(x) -1 . ( 11
)
The different densities and the associated Beta approximations are given in Fig. 6. We discuss the case m = 2 and m = 3 for which a sufficiently large number of simulations are done to perform statistical tests. m = 2 In this case, the joint law of (θ(1, 2), θ(2, 1)) is completely described by the distribution of one of the two sectors, say φ [START_REF] Athreya | Random directed trees and forest -drainage networks with dependence[END_REF]. Conditionally on the first interface θ(1, 2), we can wonder whether the other interface is uniformly and independently distributed, i.e. whether φ( 1) is a uniform r.v. on [0, 2π]. Testing H 0 : α = β = 1 with a likelihood-ratio test provides a test statistic of 2274.93 which leads us to reject the null assumption and hence the independence between the asymptotic direction of the two interfaces. We can easily been convinced of this by looking at Fig. 6 (a). As a consequence, the asymptotic directions θ(1, 2) and θ(2, 1) are not independent. m = 3 In this case, we performed a χ 2 -test for testing the adequation of the joint distribution of the sectors to a Dirichlet distribution. Since the sum of the sectors is equal to 2π, we consider the couple (φ(1), φ( 2)). With our simulations, the χ 2 -test statistic is equal to 176.49 and the adequation with the Dirichlet distribution is rejected. However, we can see that as conjectured, the simulated sample looks like a simulated sample from a Dirichlet distribution.

A Appendix: non-crossing property for the paths of the RST Lemma 14. Any two paths γ and γ ′ of the RST (finite or not) cannot cross:

∀X ∈ γ, ∀X ′ ∈ γ ′ , (X, A(X)) ∩ (X ′ , A(X ′ )) = ∅

1 +1Figure 1 :

 11 Figure 1: Here is the sub-path Z 0 , . . . , Z n of the RST crossing the vertical segment { r} × [-1, 1] (in bold)

Figure 2 :

 2 Figure 2: On the left: The sphere S(O, r) with center O and radius r is represented in bold. The tangents (the dotted lines) to S(O, r) respectively at A r and B r , intersect the horizontal axis on W r . On the right:The segment [X, A(X)] crosses I r (in bold) on J(X). On this picture, X is outside I r ⊕ B(0, c).

Figure 3 :

 3 Figure 3: (a) Empirical distribution for the number of children of O. Over 5000 simulations, 1 (resp. 2, 3, 4 and 5) child is obtained in 114 (resp. 2232, 2449, 203, 2) cases. Simulations of m = 1, . . . , 5 subtrees of the RST rooted at the children of O are given from (b) to (f). They seem to be unbounded.

Theorem 8 .

 8 For any m ∈ {1, 2, 3, 4, 5}, there exist (exactly) m unbounded subtrees of T with different colors, with positive probability. In other words, for any m ∈ {0, 2, 3, 4, 5}, there exist (exactly) m unbounded competition interfaces, with positive probability.

Figure 5 :

 5 Figure 5: RST of the PPP N satisfying both events A ε (r 1 , . . . , r 5 ) and B ε (r 1 , . . . , r 5 ). Beware the fact that, in order not to overload the figure, the condition (♦) of B ε (r 1 , . . . , r 5 ) has not been represented. The two balls are centered at O with radii r = min k∈{1,...,5} r k and R = max k∈{1,...,5} r k + 1. The X k 's are represented by big gray squares while the other points of N by small black circles.

(

  ♠) For any k ∈ {1, . . . , m}, the argument of the point Y k of N ∩ B(re i2kπ/m , ε) belongs to (2kπ/mε, 2kπ/m). Thanks to (♠), each sector of the ball B(O, r + 1) with angle 2π/m contains (at least) one of the points Y 1 , . . . Y m . Assume N ∈ A 3ε ∩ B ε which still occurs with positive probability. By construction, the origin O has exactly m children in the ball B(O, R). Let us consider a point X ∈ N \ {O, Y 1 , . . . , Y m } such that |X| ≥ R ≥ r + 1. Then B(O, |X|) ∩ B(X, |X|) contains a sector of the ball B(O, r + 1) with angle 2π/3 and so one of the Y 1 , .

  Finally, let X be a point of the PPP N which does not belong to B(O, |z 6 | + ε). The set B(X, |X|) ∩ B(O, |X|) contains an angular sector of the ball B(O, |z 6 | + ε) with central angle 2π/3. So, it also contains one of the X k 's, preventing X from being a child of O. To sum up, X 1 is the only child of the origin O. 2

Figure 6 :

 6 Figure 6: Density estimation for the angles between two interfaces, given the number m of unbounded trees. Given m, the distribution concentrates around 2π/m (red dashed line) and has a smaller variance for greater m's. Calibration with Beta distributions have been carried (blue dotted thick line), but KS test (with test statistic D) rejects the null hypothesis of Beta distribution B( α, (m -1) β) in the three cases with p-values smaller than 2.2e -16 although the distributions look similar graphically. (a) α = β = 2.74, D = 96%; (b) α = 2.69, β = 5.38, D = 91.77%; (c) α = 2.99, β = 8.99, D = 88.79%.

(

  where (a, b) denotes the segment [a, b] in R 2 without its endpoints).Proof. Let us assume there exists a point I belonging to both (X, A(X)) and (Y, A(Y )). It is easy to check that this assumption and the construction rule of the RST force X, Y, A(X) and A(Y ) to be four different points. The same is true for their Euclidean norms with probability one. Moreover, without loss of generality, we can also assume that |Y | < |X|. Then, two cases can be distinguished.First case: If |A(X)| < |Y | then Y is closer to A(Y ) than A(X): |A(Y ) -Y | < |A(X) -Y |.In the same way, the inequality |A(Y )| < |Y | < |X| implies |A(X) -X| < |A(Y ) -X|. Now, the triangular inequality leads to a contradiction:|A(Y ) -Y | + |A(X) -X| < |A(X) -Y | + |A(Y ) -X| < |A(X) -I| + |I -Y | + |A(Y ) -I| + |I -X| < |A(Y ) -Y | + |A(X) -X| .Second case: We now assume that |Y | < |A(X)| and refer to Fig 7. The points X and A(X) do not belong to the open ball B(O, |Y |) which contains A(Y ) by definition. Hence the existence of the point I forces the segment (X, A(X)) to intersect S(O, |Y |) at two distinct points, say T 1 and T 2 , dividing the closed ball B(O, |Y |) in two non overlapping sets, say U and V . By hypothesis, each of these two sets contains (exactly) one of the two points Y and A(Y ). Since |T 1 -X| and |T 2 -X| are smaller than |X -A(X)| by construction, one of the regions U or V is included in the ball B(X, |X -A(X)|). So, one of the two points Y and A(Y ) belongs to the ball B(X, |X -A(X)|). This contradicts the fact that A(X) is the ancestor of X. 2

Figure 7 :

 7 Figure 7: The hatched area corresponds to the one of the two sets U and V which is included in the ball B(X, |X -A(X)|). Here, it contains A(Y ). Besides, let us remark the origin O cannot belong to the ball B(X, |X -A(X)|).

Table 1 :

 1 (a) Empirical distributions, obtained after N = 5000 simulations, for the number of children of O (in black plain lines) and for the number of unbounded subtrees (in red dotted lines). Percentages are given in the table

	Proportion	m Children of O	1 2.28 44.64 48.98 4.06 0.04 2 3 4 5
		Unbounded subtrees 5.28 58.68 34.64 1.38 0.02
	Number

Acknowledgments: This work has been financed by the GdR 3477 Géométrie Stochastique. The authors thank the members of the "Groupe de travail Géométrie Stochastique" of Université Lille 1 and J.-B. Gouéré for enriching discussions.


Dany Obeid
email: d.obeid@kaptalia.com

Sawsan Sadek

Gheorghe Zaharia

Ghais El Zein

Cardiopulmonary Activity Monitoring with Contactless Microwave Sensor

Keywords: microwave sensors, contactless monitoring, heart rate variability

The aim of this paper is to provide a contactless microwave sensor allowing continual remote monitoring of the heartbeat and respiratory rates. This work provides a comparative study to signal detection of heartbeat, considering different frequencies and transmission powers. In addition, a model based on cardiorespiratory measure is presented. This determines the most accurate signal processing technique for the lowest possible signal to noise ratio (SNR) values. This practical approach is a necessary step before dealing with the hardware implementation and system integration.

INTRODUCTION

The measurement of heart and breathing rates may be practiced often in emergency or clinical situations. The rates extraction of heartbeat and breathing gives information at several levels [START_REF] Lubecke | 10 GHz Doppler Radar Sensing of Respiration and Heart Movement[END_REF][START_REF] Chuang | Microprocessor-controlled automatic clutter-cancellation circuits for microwave systems to sense remotely Physiological nib-through the rubble[END_REF][START_REF] Lin | Microwave apexcardiography[END_REF]. The use of Doppler radar is an important tool for such applications. Indeed, a moving target reflects the transmitted signal with a phase shift, which depends on the position of the target [START_REF] Xiao | Frequency tuning technology for remote detection of heartbeat and respiration using lowpower bouble-sideband transmission in Ka-band[END_REF]5]. Therefore, the signal reflected from the chest of a person contains information about the movement of the chest due to heartbeat and respiration. Initially, a life sign signal can be identified. This is useful, for example, for detecting movements under rubble after an earthquake. Another important parameter is the change in heartbeat rate, namely Heart Rate Variability (HRV). HRV can predict disease states and beat-to-beat measurements can be evaluated to determine the presence of cardiac abnormalities.

This paper presents a microwave system for the detection of cardio-respiratory activities. The proposed system allows the detection of heart beat signal at a distance of 1 m, using multiple operating frequencies: 2.4, 5.8, 10, 16 and 60 GHz, and for several transmitted power between 0 and -27 dBm. Based on measurements, a model representing the cardiopulmonary activity is proposed.

The rest of this paper is organized as follows: section 2 describes the proposed system and the obtained results. Section 3 shows the detection of heart rate changes. Section 4 deals with the cardiopulmonary modeling (heart beat and breathing). Finally, a summary of the work is presented in section 5.

II. MEASUREMENTS AND OBTAINED RESULTS

The proposed system uses a vector network analyzer (VNA) and two horn antennas. The installation of this system is simple and fast as presented in Fig. 1. In order to achieve a signal frequency of 60 GHz, an upconversion and down-conversion techniques are used respectively at the transmission and reception. The 3.5 GHz signal provided by the network analyzer is converted at 60 GHz with a mixture of a local oscillator signal of 56.5 GHz.

The system operating at 60 GHz is shown in Fig. 2 [START_REF] Obeid | Multi-tunable Microwave System for Touch-less Heartbeat Detection and Heart Rate Variability Extraction[END_REF]. At a distance of 1 m from a person with a total transmitted power (including antenna gain) of -10 dBm, our system was used at different frequencies: 2.4, 5.8, 10, 16, and 60 GHz. Fig. 3 shows the phase variation of the parameter S 21 at several frequencies due to the heart beating. It can be noticed that the phase variation increases as the frequency increases. Thus, a greater sensitivity to small displacements is obtained at higher frequencies. This will reduce the effect of noise and increase the detection precision of signal peaks. In addition to the frequency parameter, the minimum transmitted power is an important parameter to be determined. Indeed, it is safer for patients and medical staff to be subject to as low emission levels as possible. For a fixed frequency (2.4 GHz), measurements were performed for different power levels: -2 dBm, -7 dBm, -12 dBm, -17 dBm, -22 dBm, and -27 dBm. Fig. 4 shows the phase variations due to heartbeats obtained for different transmission powers. One can notice that the reduction in transmit power makes the peaks of the measured signal more noisy. This makes the extraction of the heartbeat rate changes less accurate.

III. HEART RATE VARIABILITY

Extracting heartbeat rate can be determined by the application of the FFT (Fast Fourier Transform). This gives a frequency corresponding to an average heartbeat rate. However, the average frequency does not provide the temporal variation of the cardiac rhythm HRV that is a measure of changes in the duration between two successive beats (this is equivalent to the RR-interval of the ECG signal). This HRV parameter is considered as an activity monitor autonomous regulation of circulatory function. Its extraction requires a maximum detection in the time domain. A simple example of information extraction in the time domain is the calculation of standard deviation of the beat-to-beat intervals.

Fig. 5 shows the signal detected at 16 GHz with a total transmit power of -25 dBm and shows the peaks detected with the implementation of the Peak Detection Method (PDM). This technique is based on detecting the maximum value in a sliding window [START_REF] Obeid | Multi-tunable Microwave System for Touch-less Heartbeat Detection and Heart Rate Variability Extraction[END_REF].

A smoothing technique, based on a sliding averaging, is used to reduce the noise [START_REF] Obeid | Multi-tunable Microwave System for Touch-less Heartbeat Detection and Heart Rate Variability Extraction[END_REF]. During the period of 10 seconds of each experiment, the heartbeat rate is calculated for both the original signal and the smoothed signal. However, the difference between heartbeat rate extracted from the original signal and that obtained from the smoothed signal is low. The HRV is extracted both from the original signal and the smoothed signal. It can be seen from this figure that the difference between the HRV obtained from the measured signal and the HRV signal obtained after smoothing, increases with decreasing frequency. This effect is due to the amplitude of the phase variation, which is directly proportional to the transmission frequency.

Similarly, Fig. 7 (a-f) shows the HRV detected at -2 dBm, -7 dBm, -12 dBm, -17 dBm, -22 dBm and -27 dBm, for a frequency of 2.4 GHz. As the SNR increases, the transmit power increases and the signal becomes less noisy; this reduces the effect of smoothing. One can notice the difference between the HRV of the original signal (blue) and the smoothed signal (red) for several transmission powers.

IV. MEASUREMENT-BASED CARDIOPULMONARY MODELING

In order to reduce the measurement campaigns that can be cumbersome and costly, a cardio respiratory activity modeling is necessary. This helps determining the appropriate signal processing method. Triangular waves with variable frequency and amplitude are modeled to represent the cardio respiratory signal. The signal is modeled according to the following relationships:

) ( ) ( ) ( k B X k A X Y u u + = for : [X u (i) + X d (i)] ≤ X ≤ X u (k) + [X u (i) + X d (i)] i=1 k-1 ∑ i=1 k-1 ∑ and ( ) ( ) ( ) d d Y X A k X B k = +
for:

X u (k) + [X u (i) + X d (i)] ≤ X ≤ X u (k) + [X u (i) + X d (i)] i=1 k ∑ i=1 k-1 ∑
where A u and B u represent the coefficients of the rising part of the curve. A d and B d represent the coefficients of the falling portion of the curve. X u and X d represent respectively the durations of these two parts of the pulse. The sum of these two times is the duration of the pulse. In the above relationships, k is the number of pulses. Compared to the measured signal, the proposed model shows an accuracy of 100% in terms of heartbeat rate, while it shows a mean relative error of 0,12% in terms of HRV.

The heartbeat signal and the measured signal modeling are presented in Fig. 8. The separation of heartbeat and breathing signals is done using different techniques. Thus, the application of an FFT to extract the heart rate showed a mean relative error of 1% for an SNR between 0 and -20 dB, whereas with the PDM method applied after a Chebyshev filter, this error is approximately 9.1%. The application of the PDM for the extraction of heartbeat rate after wavelet filtering shows a 100% accuracy. The application of the PDM to the filtered signal with wavelet shows a measurement accuracy of heartbeat rate of 100%. On the other hand, the wavelet transform shows the possibility to extract the HRV with a mean relative error of about 4.5%. Fig. 9 shows the mean relative error to extract the HRV from the modeled signal after applying the wavelet transform to SNR values between 0 and -20 dB.

[5] Figure 9. Average relative error for the extraction of HRV after applying the wavelet transform to modeled cardio respiratory signals.

V. CONCLUSION A contactless measuring system for the cardio-pulmonary activity, using the propagation of electromagnetic waves and microwave Doppler effect, is proposed. At a distance of 1 meter, our system is tested for several different frequencies and transmitted powers, with and without breathing. The originality of the proposed system is the ability to vary the operating frequency and the transmitted power with the same hardware. This is necessary to conduct a detailed parametric study. Experiments were performed at several frequencies: 2.4, 5.8, 10, 16, and 60 GHz. For a fixed frequency of 2.4 GHz, measurements were also performed at different power levels: -2, -7, -12, -17, -22, and -27 dBm. A second part of the study deals with the modeling of cardiopulmonary signals and with the application of advanced methods for processing modeled signals. Thus, several techniques have been implemented for the separation of cardiopulmonary signals such as the use of filtering or the wavelet transform.

Figure 1 .

 1 Figure 1. Schematic of the proposed system.

Figure 2 .

 2 Figure 2. Design of the system operating at 60 GHz.

Figure 3 .

 3 Figure 3. Phase variations due to heartbeat detected at: (a) 2.4 GHz (b) 5.8 GHz, (c) 10 GHz, (d) 16 GHz, (e) 60 GHz and (f) with all frequencies.

Figure 4 .

 4 Figure 4. Phase variations due to heartbeat detected at 2.4 GHz for the different transmission powers: (a) -2 dBm, (b) -7 dBm, (c) -12 dBm, (d) -17 dBm, (e) -22 dBm and (f) -27 dBm.

Figure 5 .

 5 Figure 5. Beats of the heart detected at 16 GHz for a transmit power of -25 dBm.

Fig. 6 (

 6 Fig. 6 (a-e) shows the HRV signals detected at 2.4, 5.8, 10, 16, and 60 GHz, for a total transmit power of -10 dBm.

Figure 6 .

 6 Figure 6. Heart rate variability at: (a) 2.4 GHz; (b) 5.8 GHz; (c) 10 GHz; (d) 16 GHz and (e) 60 GHz.

Figure 7 .

 7 Figure 7. Heart rate variability for measurements performed at 2.4 GHz for the transmission powers: (a) -2 dBm, (b) -7 dBm, (c) -12 dBm, (d) -17 dBm, (e) -22 dBm and (f) -27 dBm.

Figure 8 .

 8 Figure 8. Comparison between the measured heartbeat signal at 5.8 GHz and the proposed modeled signal.

The authors acknowledge CEDRE (project reference number: 08SciF6/L4), AUF (project reference number: G3-110/1649), and "Région Bretagne" for partially funding this work.


Nagham Alhadad

Philippe Lamarre
email: philippe.lamarre@liris.cnrs.fr

Yann Busnel

Patricia Serrano-Alvarado

Marco Biazzini

Christophe Sibertin-Blanc
email: christophe.sibertin-blanc@univ-tlse1.fr

SocioPath: Bridging the Gap between Digital and Social Worlds

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Nowadays, the most widespread architectures belong to the domain of distributed systems [START_REF] Coulouris | Kindberg: Distributed Systems: Concepts and Design[END_REF]. Most of participants' activities on these systems concern their data (sharing and editing documents, publishing photos, purchasing online, etc.) [START_REF] Weaver | Social Networking[END_REF]. Using these systems implies some relationships with a lot of people. These people may be partly unknown, but one depends on them in several ways:

-Which person(s)/resource(s) a user depends on to perform an activity? -Whom can prevent a user from performing an activity? -Which persons a user is able to avoid to perform an activity? -Who is possibly able to access user's data? Some of these questions raise several issues as someone may be able to grab information about who the user is, what the user does, and so forth. That directly leads to privacy [START_REF] Westin | Privacy and Freedom[END_REF], trust [START_REF] Marti | Taxonomy of Trust: Categorizing P2P Reputation Systems[END_REF] and security issues [START_REF] Lampson | Authentication in Distributed Systems: Theory and Practice[END_REF].

The analysis of such systems is usually limited to technical aspects as latency, QoS, functional performance, failure management [START_REF] Aurrecoechea | A Survey of QoS Architectures[END_REF], etc. The aforementioned questions give some orthogonal but complementary criteria to the classical approach. Currently, people underestimate social dependences [START_REF] Emerson | Power-Dependence Relations[END_REF][START_REF] Molm | Structure, Action, and Outcomes: The Dynamics of Power in Social Exchange[END_REF][START_REF] Blau | Exchange and Power in Social Life[END_REF] generated by the systems they use and the resulting potential risks. We argue that to be able to know dependences, one should be aware of some key aspects of systems. This paper proposes the SOCIOPATH meta-model. This approach is based on notions coming from many fields, ranging from computer science to sociology. SOCIOPATH is a generic meta-model that considers two worlds: the social world and the digital world. SOCIOPATH allows us to draw a representation of a system that identifies persons, hardware, software and the ways they are related. Enriched with deduction rules, SOCIOPATH analyzes the relations in the digital world, to deduce the relations of dependences in the social world, given an activity concerning some data. As a modeling tool that bridges the gap between the digital and the social world, SOCIOPATH can be useful in the evaluation process of a system with respect to security, privacy, risk and trust requirements.

The paper is organized as follows. Section 2 introduces the SOCIOPATH meta-model and gives a simple example of its use. Section 3 defines the way to compute the user's digital and social dependences. Section 4 presents a brief overview of related works. Finally, Section 5 concludes and points out our ongoing work.

SOCIOPATH meta-model

The SOCIOPATH meta-model describes the architecture of a system in terms of the components people use to access digital resources, so that chains of dependences can be identified. It distinguishes the social world, where humans or organizations own physical resources and data, and the digital world, where instances of data are stored and processes run. Figure 1 shows the graphical representation of SOCIOPATH, which we analyze in the following sections.

The social world

The social world includes persons (users, enterprises, companies, etc.), physical resources, data and relations among them.

-Data represents an abstract notion that exists in the real life, and does not necessarily imply a physical instance (e.g., address, age, software design, etc.); -Physical Resource represents any hardware device (e.g., PC, USB device, etc.); -Person represents a generic notion that defines an Individual like Alice or a Legal Entity like Microsoft.

The digital world

The digital world has nodes that are defined as follows:

-Data Instance represents a digital representation of Data; -Artifact represents an abstract notion that describes a "running software". This can be an Application, an Operating System or a Network Service; -Digital Resource represents an Artifact or a Data Instance; -Actor represents a Person in the social world or an Artifact in the digital world.

The relations in SOCIOPATH

Several relations are drawn in SOCIOPATH. In this section, we briefly describe them.

owns: this means ownership. This relation only exists in the social world; -isConnectedTo: this means that two nodes are physically connected, through a network for instance. This symmetric relation exists only in the social world; -canOperate: this means that an artifact is able to process, communicate or interact with a target digital resource; accesses: this means that an Actor can access a Digital Resource; controls: this means that an Actor controls a Digital or a Physical Resource. There exists different kinds of control relations. A legal entity, who provides a resource, controls its functionalities. The persons who use this resource have some kind of control on it; supports: this means that the target node could never exist without the source node; represents: this is a relation between data and their instances in the digital world. Persons own some data in the social world. Data have a concrete existence in the digital world if they are represented by some Data Instance and supported by some Physical Resource. As an Actor in the digital world, a Person can access and control Data Instances representing her (and others') Data. This may be done through different resources, thus implying some dependences on other persons. Moreover, we consider that a person provides an artifact (cf. the rightmost part of Figure 2) if this person owns data represented by a data instance which supports the artifact. Applying SOCIOPATH makes possible non-trivial deductions about relations among nodes. For instance, an actor may be able to access digital resources supported by different physical resources connected to each other (e.g., a user can access processes running in different hosts).

Figure 2 shows a basic SOCIOPATH model1 of a use-case on a unique PC. In the social world, a user John owns some Data and a PC. There are also legal entities as: Microsoft, provider of Windows, Word (MSWord) and Excel (MSExcel); 3 Using SOCIOPATH to derive dependences for an activity SOCIOPATH features a set of rules we can apply to underline and discover chains of accesses and controls relations. Table 2 shows the formal definitions of some rules that we can deduce from the meta-model basic definitions. More details are given in [START_REF] Alhadad | SOCIOPATH: In Whom You Trust? Technical report[END_REF]. In this work, we want to use these relations to better understand the "social and digital dependences" among entities in the model. Thus, informally, the sets of digital dependences of a person are composed by the artifacts a user passes through to reach a particular element. The sets of social dependences are composed by the persons who control these

(A)} A A ⊂ A A A ∈ A Artifact F {F : artif act(F )} F F ⊂ F F F ∈ F Digital resource DR {DR : resource(DR)} DR DR ⊂ DR DR DR ∈ DR Physical resource PR {P R : phyresource(P R)} PR PR ⊂ PR P R P R ∈ PR Data D {D : data(D)} D D ⊂ D D D ∈ D Data instance DI {DI : dataInstance(DI)} DI DI ⊂ DI DI DI ∈ DI Operating System O {OS : operatingSystem(OS)} O O ⊂ O OS OS ∈ O Path Γ {σ : path(σ)} Υ Υ ⊂ Γ σ σ ∈ Γ Activity W - - - ω ω ∈ W Set of activity restrictions S {S = P(F N )} - - S S ∈ S

Activities and Paths

A user follows a path to perform an activity in a system. Some restrictions may be given to the ways the person might do their activity. For instance, if a person wants to read a .doc document, she must use an artifact that can "understand" this type of document, so activity is defined as follows.

Definition 1 (Activity).

We define an activity ω as a triple (P, D, S), where P is a person, D is data and S is a set of ordered multisets of F in a model, so an activity ω is an element of P × D × S. The sets in the S component of an activity are alternative sets of artifacts that are necessary for the person to perform her activity. For instance, the activity "John edits toto.doc" is defined as ω=(John,Data,{{MSWord}, {Pages}, {OOWriter}}).

We call paths the lists of actors and digital resources that describe the ways an actor may access a resource. A person may perform an activity in different ways and using different intermediate digital resources. Each possibility can be described by a path.

Definition 2 (Activity path, or ω-path).

A path σ for an activity ω = (P, D, S) ∈ P × D × S is a list of actors and digital resources such that:

-σ[1] = P ; -σ[|σ|] = D; -represents(σ[|σ| -1], σ[|σ|]); -∀i ∈ [2 : |σ| -1], artif act(σ[i]) ∧ accesses(σ[i -1], σ[i]); -∃s ∈ S, s ⊆ σ;
where σ[i], denotes the i th element of σ, and |σ| the length of σ.

Notation: Assuming that there is no ambiguity on the model under consideration, the set of ω-paths where ω= (P, D, S) is noted Υ ω and the set of all the paths in the model is noted Υ . In the first ω-path presented above, MSExcel is not mandatory to edit toto.doc. It appears in the ω-path because of the relation accesses between it and the artifact Windows. In order to exclude all the unnecessary elements from the ω-path, so we define the minimal paths as follows.

Definition 3 (Minimal path).

Let Υ ω be a set of paths for an activity ω. A path σ ∈ Υ ω is said to be minimal in Υ ω iff there exists no path σ' such that:

-σ[1] = σ [1] and ; σ[|σ|] = σ [|σ |]; -∀i ∈ [2 : |σ |], ∃j ∈ [2 : |σ|], σ [i] = σ[j].
Notation: The set of minimal paths enabling an activity ω= (P, D, S) is noted Υ ω . For sake of simplicity, we name this set the ω-minimal paths.

For instance, for the activity ω = "John edits toto.doc", the set of the ω-minimal paths are: Notation: Let say F ∈ σ iff ∃i such that σ[i] = F , and s ⊆ σ iff ∀F ∈ s, F ∈ σ.

Υ ω =    {John,

Dependence

We can now introduce the definitions of digital dependences (Definition 4 and 5) and social dependences (Definition 6 and 7). We say that a person depends on a set of artifacts for an activity ω if each element of this set belongs to one or more paths in the set of the ω-minimal paths.

Definition 4 (Person's dependence on a set of artifacts for an activity).

Let ω = (P, D, S) be an activity, F be a set of artifacts and Υ ω be the set of ω-minimal paths. P depends on F for an activity ω iff ∀F ∈ F, ∃σ ∈ Υ ω : F ∈ σ.

For instance, one of the sets on which John depends for the activity "John edits toto.doc" is {MacOS, MSWord}.

A person does not depend in the same way on all the sets of artifacts. Some sets may be avoidable i.e., the activity can be executed without them. Some sets are unavoidable i.e., the activity cannot be performed without them. To distinguish the way a person depends on artifacts, we define the degree of a person's dependence on a set of artifacts for an activity as the ratio of the ω-minimal paths that contain these artifacts.

Definition 5 (Degree of person dependence on a set of artifacts for an activity).

Let ω = (P, D, S) be an activity, F be a set of artifacts and Υ ω be the set of ω-minimal paths and | Υ ω | is the number of the minimal ω-paths. The degree of dependence of P on F, denoted d ω F , is:

d ω F = |{σ : σ ∈ Υ ω ∧ ∃F ∈ F , F ∈ σ}| | Υ ω |
For instance, the degree of dependence of John on the set {MacOS, MSWord} for the activity "John edits toto.doc" is equal to one, while the degree of dependence of John on the set {Pages, OOWriter} is equal to 2/3. From digital dependences we can deduce social dependences. A person depends on a set of persons for an activity if the persons of this set control some of the artifacts the person depends on.

Definition 6 (Person's dependence on a set of persons for an activity).

Let ω = (P, D, S) be an activity, and P be a set of persons.

P depends on P for ω iff ∧ ∃F ⊂ F : P depends on F for ω ∀F ∈ F , ∃P ∈ P : controls(P , F )

For instance, one of the sets John depends on for the activity "John edits toto.doc" is {Oracle, Apple}.

The degree of a person's dependence on a set of persons for an activity is given by the ratio of the ω-minimal paths that contain artifacts controlled by this set of persons.

Definition 7 (Degree of person's dependence on a set of persons for an activity).

Let ω = (P, D, S) be an activity, P be a set of persons and Υ ω be the ω-minimal paths. The degree of dependence of P on P, noted d ω P is:

d ω P = |{σ : σ ∈ Υ ω ∧ ∃P ∈ P, ∃F ∈ σ, controls(P , F )}| | Υ ω |
For instance, the degree of dependence of John on the set {Oracle, Apple} for the activity "John edits the toto.doc" is equal to 2/3. We recall that Oracle controls OOWriter and Apple controls MacOS.

Related work

Frameworks and tools modeling IT (Information Technology) systems are widely used in the context of Enterprise Architecture Management (EAM) [START_REF] Goethals | An Overview of Enterprise Architecture Framework Deliverables[END_REF]. EAM aims at giving a structured description of large IT systems in terms of their business, application, information and technical layers, with the additional goal of understanding how existing architectures and/or applications should be changed to improve business or strategic goals. SOCIOPATH rather focuses on dependence relationships, although converging with these frameworks in some aspects. For instance, RM-ODP (Reference Model of Open Distributed Processing) [START_REF] Farooqui | The ISO Reference Model for Open Distributed Processing: An Introduction[END_REF], is a generic set of standards and tools to create and manage aspect-oriented models of systems. RM-ODP analyzes and decomposes the systems in detail, mainly focusing on standard compliance. Aiming at different goals, SOCIOPATH gives a simpler overview of a system that is meant to inform the users about the relations that are implied by the system architecture, without exposing technical details. TOGAF (The Open Group Architecture Framework) [START_REF]TOGAF: Welcome to TOGAF -The Open Group Architectural Framework[END_REF], an approach for designing, planning, implementation, and governance of an enterprise information architecture, converges with SOCIOPATH in some of the concepts used to model the technical architecture of the enterprise. Unlike SOCIOPATH, TOGAF focuses on several aspects of the software engineering process, while describing the hardware, software and network infrastructures. None of these works considers dependence relations among users in the social world. SOCIOPATH aims at improving awareness and exposing the relations of dependence generated on the social world from the digital world. More details about the related works are available in [START_REF] Alhadad | SOCIOPATH: In Whom You Trust? Technical report[END_REF] 5 Ongoing work and Conclusion SOCIOPATH allows to deduce the degree of dependence of a person on the entities of a system architecture for an activity. With SOCIOPATH it is possible to know, for instance, who can prevent a person to perform an activity or whom a person can avoid while performing an activity.

Our ongoing work concerns several aspects. Currently SOCIOPATH does not distinguish the different kinds of access and control of an actor to a digital resource. In order to consider intentions and expectations of users regarding digital resources, SO-CIOPATH can be enriched with access and control typologies, to define different kinds of dependences. Moreover, no difference is made between what persons can do and what they are allowed to do according to the law, the moral rules etc. We aim at distinguishing between dependences related to the system's architecture, and dependences related to social commitments. Finally, the results of SOCIOPATH can be related with the notion of trust of a person toward the persons she depends on. Indeed, if a user does not trust some person, she will be concerned about architecture-induced dependences on this person, whereas if she trusts a person, she will only be concerned about commitments-related dependences.

Fig. 1 :

 1 Fig. 1: Graphical view of SOCIOPATH as a UML class diagram.

Fig. 2 :

 2 Fig. 2: Use case example: a document accessed by 2 different operating systems.

  For example, concerning the ω-paths for the activity ω = "John edits toto.doc" in Figure2, we have: {John, Windows, MSWord, Windows, MSExcel, Windows, toto.doc} {John, MacOS, OOWriter, MacOS, toto.doc} .

Table 1 :

 1 Glossary of notationsApple, provider of MacOS and Pages; and Oracle, provider of Open Office Writer (OOWriter). In the digital world, two operating systems exist on John's PC: Windows and MacOS. On Windows, two applications are available: MSWord and MSExcel. On MacOS are installed OOWriter and Pages. John's Data are represented in the digital world by the document toto.doc. We use this example to illustrate some deductions in the following. Table1summarizes the notations we use.

Table 2 :

 2 Deduced access and control relations artifacts. In the following, all those concepts are formally defined. The examples refer to Figure 2.

  Windows, MSWord, Windows, toto.doc} {John, MacOS, OOWriter, MacOS, toto.doc} {John, MacOS, Pages, MacOS, toto.doc}

	
		.
	

We consider that a model conforms to a meta-model.