Xuan Hoang

Mickaël Montassier

Alexandre Pinlou

Petru Valicov

Hoang La

Mickael Montassier

r-hued (r + 1)-coloring of planar graphs with girth at least 8 for r ≥ 9

Keywords: planar graphs, 2-distance coloring, r-hued coloring, dynamic coloring, discharging method

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A k-coloring of the vertices of a graph G = (V, E) is a map φ : V → {1, 2, . . . , k}. A k-coloring φ is a proper coloring, if and only if, for all edge xy ∈ E, φ(x) = φ(y). In other words, no two adjacent vertices have the same color. The chromatic number of G, denoted χ(G), is the smallest integer k so that G has a proper k-coloring. A generalization of k-coloring is k-list-coloring. A graph G is L-list colorable if for a given list assignment L = {L(v) : v ∈ V (G)} there is a proper coloring φ of G such that for all v ∈ V (G), φ(v) ∈ L(v). If G is L-list colorable for every list assignment L with |L(v)| ≥ k for all v ∈ V (G), then G is said to be k-choosable or k-list-colorable. The list chromatic number of a graph G, is the smallest integer k such that G is k-choosable. List coloring can be very different from usual coloring as there exist graphs with a small chromatic number and an arbitrarily large list chromatic number.

In 1969, Kramer and Kramer introduced the notion of 2-distance coloring [START_REF] Kramer | Ein Färbungsproblem der Knotenpunkte eines Graphen bezüglich der Distanz p[END_REF][START_REF] Kramer | Un problème de coloration des sommets d'un graphe[END_REF]. This notion generalizes the "proper" constraint (that does not allow two adjacent vertices to have the same color) in the following way: a 2-distance k-coloring is such that no pair of vertices at distance at most 2 have the same color (similarly to proper k-list-coloring, one can also define 2-distance k-list-coloring). The 2-distance chromatic number of G, denoted χ 2 (G), is the smallest integer k so that G has a 2-distance k-coloring. An example of 2-distance colorings is given in Figure 1.

For all v ∈ V , we denote d G (v) the degree of v in G and by ∆(G) = max v∈V d G (v) the maximum degree of a graph G. For brevity, when it is clear from the context, we will use ∆ (resp. d(v)) instead of ∆(G) (resp. d G (v)). One can observe that, for any graph G, ∆ + 1 ≤ χ 2 (G) ≤ ∆ 2 + 1. The lower bound is trivial since, in a 2-distance coloring, every neighbor of a vertex v with degree ∆, and v itself must have a different color. As for the upper bound, a greedy algorithm shows that χ 2 (G) ≤ ∆ 2 + 1. Moreover, this bound is tight for some graphs, for example, Moore graphs of (ii) A non-optimal 2-distance 7-coloring. type (∆, 2), which are graphs where all vertices have degree ∆, are at distance at most two from each other, and the total number of vertices is ∆ 2 + 1. See Figure 2.

A graph is planar if one can draw its vertices with points on the plane, and edges with curves intersecting only at its endpoints. When G is a planar graph, Wegner conjectured in 1977 that χ 2 (G) becomes linear in ∆(G): Conjecture 1 (Wegner [38]). Let G be a planar graph with maximum degree ∆. Then,

χ 2 (G) ≤        7, if ∆ ≤ 3, ∆ + 5, if 4 ≤ ∆ ≤ 7, 3∆ 2 + 1, if ∆ ≥ 8.
The upper bound for the case where ∆ ≥ 8 is tight (see Figure 3(i)). Recently, the case ∆ ≤ 3 was proved by Thomassen [START_REF] Thomassen | The square of a planar cubic graph is 7-colorable[END_REF], and by Hartke et al. [START_REF] Hartke | The chromatic number of the square of subcubic planar graphs[END_REF] independently. For ∆ ≥ 8, Havet et al. [START_REF] Havet | List colouring squares of planar graphs[END_REF] proved that the bound is 3 2 ∆(1 + o(1)), where o( 1) is as ∆ → ∞ (this bound holds for 2-distance list-colorings). Conjecture 1 holds for K 4 -minor free graphs [START_REF] Lih | Coloring the square of a K 4 -minor free graph[END_REF].

For large ∆ (≥ 8), the coefficient before ∆ becomes 1 when the graph becomes "sparser". Here, a "sparse" graph means that it has a "low" number of edges. One way to measure the sparsity of a graph is through its maximum average degree. The average degree ad of a graph G = (V, E) is defined by ad(G) = 2|E|

|V | . The maximum average degree mad(G) is the maximum, over all subgraphs H of G, of ad(H). Another way to measure the sparsity is through the girth, i.e. the length of a shortest cycle. We denote by g(G) the girth of G. Intuitively, the higher the girth of a graph is, the sparser it gets. These two measures can actually be linked directly in the case of planar graphs. Proposition 2 (Folklore). For every planar graph G, (mad

(G) -2)(g(G) -2) < 4.
As a consequence, any theorem with an upper bound on mad(G) can be translated to a theorem with a lower bound on g(G) under the condition that G is planar.

In the case of sparse planar graphs, extensive researches have been done and many results have taken the following form: every planar graph G of girth g ≥ g 0 and ∆(G) ≥ ∆ 0 satisfies χ 2 (G) ≤ ∆ + c(g 0 , ∆ 0 ), where c(g 0 , ∆ 0 ) is a constant depending only on g 0 and ∆ 0 . Table 1 shows all known such results on the 2-distance chromatic number of planar graphs with fixed girth, up to our own knowledge. For example, the result from line "7" and column "∆ + 1" from Table 1 reads as follows : "every planar graph G of girth at least 7 and of ∆ at least 16 satisfies χ 2 (G) ≤ ∆ + 1". The crossed out cases in the first column correspond to the fact that, for g 0 ≤ 6, there are planar graphs G with χ 2 (G) = ∆ + 2 for arbitrarily large ∆ [START_REF] Borodin | Sufficient conditions for the 2-distance (∆ + 1)-colorability of plane graphs[END_REF][START_REF] Dvořák | Coloring squares of planar graphs with girth six[END_REF]. The lack of results for g ≥ 4 is due to the fact that the graph in Figure 3(ii) has girth 4, and χ 2 = 3∆ 2 -1 for all ∆. Finally, many of these results are corollaries of theorems on 2-distance list-colorings or 2-distance colorings of graphs with bounded maximum average degree.

The "2-distance" condition in 2-distance colorings requires that vertices at distance at most two have different colors. In other words, all neighbors of the same vertex must have different colors. This condition was generalized recently and the notion of r-hued coloring was introduced [33]. Let r, k ≥ 1 be two integers. An r-hued k-coloring of the vertices of G is a proper k-coloring of the vertices, such that all vertices are r-hued. A vertex is r-hued if the number of colors in its neighborhood N G (v) = {x|xv ∈ E} is at least min{d G (v), r}. The r-hued chromatic number of G, denoted χ r (G), is the smallest integer k so that G has an r-hued k-coloring.

It is indeed a generalization of 2-distance colorings which corresponds to the case r ≥ ∆, as all vertices in the same neighborhood will have different colors. More generally, its link to proper coloring and 2-distance coloring resides in the following equation:

χ(G) = χ 1 (G) ≤ χ 2 (G) ≤ • • • ≤ χ ∆ (G) = χ ∆+1 (G) = • • • = χ 2 (G) (1)
Examples of r-hued colorings are given in Figure 4. Similar to the 2-distance chromatic number, the r-hued chromatic number is linear in r when it comes to planar graphs. In 2014, Song et al. proposed a generalization of Conjecture 1: Conjecture 3 (Song et al. [START_REF] Song | On r-hued coloring of K 4 -minor free graphs[END_REF]). Let G be a planar graph. Then,

χ r (G) ≤      r + 3, if 1 ≤ r ≤ 2, r + 5, if 3 ≤ r ≤ 7, 3r 2 + 1, if r ≥ 8.
One can note that the case r = 1 corresponds to the Four Color Theorem [START_REF] Appel | Every planar map is four colorable. part I. discharging[END_REF][START_REF] Appel | Every planar map is four colorable. part II. reducibility[END_REF] ; additionally, by taking r = ∆(G), Conjecture 3 implies Conjecture 1 except for the case r = 3. Moreover, the only extremal known examples reaching the upper bounds of Conjecture 3 are the same as for Conjecture 1 (see Figure 3(i)).

The case of r = 2 has been proven by Chen et al. in [START_REF] Chen | On dynamic coloring for planar graphs of higher genus[END_REF]. Song and Lai [START_REF] Song | Upper bound of r-hued colorings of planar graphs[END_REF] proved that, if r ≥ 8, then every planar graph verifies χ r (G) ≤ 2r + 16. Similar to 2-distance coloring, the coefficient before r in this upper bound becomes 1 for graphs with a higher girth. Table 2 shows all known results of the following form: let r and r 0 be integers such that r ≥ r 0 , every planar graph G of girth g(G) ≥ g 0 satisfies χ r (G) ≤ r + c(g 0 , r 0 ), where c(g 0 , r 0 ) is a constant depending only on g 0 and r 0 .

g 0 χ r (G) r + 1 r + 2 r + 3 r + 4 r + 5 r + 6 r + 7 . . . r + 10 3 r = 2 [25] 6 r = 2 [14] r = 2 [27] 7 r = 3 [32] 4 5 r ≥ 15 [11] 8 all r [11] 6 r ≥ 3 [30] 7 r = 2 [27] 7 r = 3 [26] 7 8 r ≥ 66 [36] 9 r ≥ 9 10 9 r ≥ 8 [12] 7 r = 3 [26] 7 10 r ≥ 6 [12] 7 11 12 r ≥ 5 [12] 7 13 14 r = 3 [15]
Table 2: The latest results with a coefficient 1 before r in the upper bound of χ r .

The result from the "9" line and "r + 1" column reads "for r ≥ 8, every planar graph G of girth at least 9 satisfies χ r (G) ≤ r + 1". Since an r-hued coloring is a 2-distance coloring when r ≥ ∆, some results for 2-distance colorings come from r-hued colorings. Similarly to 2-distance colorings, many of these results also come from r-hued list-colorings, or r-hued colorings of graphs with a bounded maximum average degree.

We are interested in the case χ r (G) = r + 1 (as r + 1 is a trivial lower bound for χ r (G) as soon as the graph contains a vertex of degree at least r). In particular, we were looking for the smallest integer r such that a planar graph of girth at least 8 can be r-hued colored with r + 1 colors, with the aim to find a sufficiently good lower bound to obtain a new result on 2-distance coloring which is a long-standing active research area. Song et al. [START_REF] Song | List r-hued chromatic number of graphs with bounded maximum average degrees[END_REF] showed that every graph G with mad(G) < 14 5 and r ≥ f ( ) satisfies χ r (G) ≤ r + 1 for 0 < ≤ 1 20 and f ( ) = 16 5 + 2. Therefore, as a corollary, one can derive that, if G is a planar graph with girth at least 8 and r ≥ 66, then χ r (G) ≤ r + 1. While restricting the study on planar graphs we improve this corollary in Theorem 4.

Our main result is the following:

Theorem 4. If G is a planar graph with g(G) ≥ 8, then χ r (G) ≤ r + 1 for r ≥ 9.
Hence for r = ∆, we get the following corollary:

Corollary 5. If G is a planar graph with g(G) ≥ 8 and ∆(G) ≥ 9, then χ 2 (G) = ∆(G) + 1.
Corollary 5 is an improvement of the best known 2-distance coloring result for planar graphs of girth at least 8 with ∆ + 1 colors (see Table 1). Results for this class of graphs were first proved by Borodin et al. in [START_REF] Borodin | List 2-distance (∆ + 1)-coloring of planar graphs with given girth[END_REF] who showed that these graphs can be list 2-distance colored with ∆ + 1 colors for ∆ ≥ 15. Later, the lower bound on ∆ was improved to ∆ ≥ 10 by Ivanova in [START_REF] Ivanova | List 2-distance (∆+1)-coloring of planar graphs with girth at least 7[END_REF]. We generalized these results to r-hued coloring. By dropping the choosability restriction and by exploiting heavily the planarity of the input graph, we are able to improve the lower bound on the maximum degree to ∆ ≥ 9 for every planar graph of girth at least 8.

Notations and drawing conventions.. In the following, we will only consider planar graphs. Each considered planar graph will be embedded into the plane. We will denote F (G) the set of faces of a plane graph G. We denote

d G (f ) the size of face f ∈ F (G). For v ∈ V (G), the 2-distance neighborhood of v, denoted N * G (v)
, is the set of 2-distance neighbors of v, which are vertices at distance at most two from v, not including v. We also denote

d * G (v) = |N * G (v)|.
From now on, we will omit the subscript G when there is no ambiguity. Some more notations:

• A d-vertex (d + -vertex, d --vertex) is a vertex of degree d (at least d, at most d). A (d ↔ e)-
vertex is a vertex with degree between d and e included.

• A d-face (d + -face, d --face) is a face of size d (at least d, at most d).

• A k-path (k + -path, k --path) is a path of length k + 1 (at least k + 1, at most k + 1) where the k internal vertices are 2-vertices.

• A (k 1 , k 2 , . . . , k d )-vertex is a d-vertex incident to d different paths, where the i th path is a k i -path for all 1 ≤ i ≤ d.
As a drawing convention for the rest of the figures, black vertices will have a fixed degree, which is represented, and white vertices may have a higher degree than what is drawn.

Proof of Theorem 4

Let us now consider the proof of our main result, namely, if G is a planar graph with g(G) ≥ 8, then χ r (G) ≤ r + 1 for r ≥ 9.

Let G be a counterexample to Theorem 4 with the fewest number of edges. The purpose of the proof is to prove that G cannot exist. In the following we will study the structural properties of G (Section 2.1). We will then apply a discharging procedure (Section 2.2). For a plane graph

G = (V, E, F ), Euler's formula |V | -|E| + |F | = 2 can be rewritten as v∈V (G) (3d G (v) -8) + f ∈F (G) (d G (f ) -8) = -16. (2)
We assign to each vertex v the charge µ(v) = 3d(v)-8 and to each face

f the charge µ(f ) = d(f )-8.
To prove the non-existence of G, we will redistribute the charges preserving their sum and obtaining a non-negative total charge, which will contradict Equation (2).

Structural properties of G

Without loss of generality, we can assume that G is connected. Moreover G has no vertex of degree 1. Otherwise, we can simply remove the unique edge incident to such vertex v and color the resulting graph with an r-hued coloring φ, which is possible due to the minimality of |E(G)|.

Then, we add the edge back and check the degree of v's unique neighbor x in G. If d(x) ≤ r, we can choose a color for v different from x's and all of its neighbors' to maintain the r-hued property of the coloring. If d(x) > r, then x is already r-hued, so it suffices to choose a color for v different from φ(x).

Lemma 6. Let w be a vertex of G that is adjacent to

k vertices u i (k ≤ d(w)), each satisfying d * (u i ) ≤ r + i -1 for 1 ≤ i ≤ k. Then we have d * (w) ≥ r + k + 1.
Proof. Suppose by contradiction that w is adjacent to 5. We remove the edges wu i for 1 ≤ i ≤ k. By minimality of G, let φ H be a r-hued coloring of H = (V, E \ {wu 1 , . . . , wu k }).

u i with d * G (u i ) ≤ r + i -1 for 1 ≤ i ≤ k, but d * G (w) ≤ r + k. See Figure
We uncolor the vertex w and the vertices u i for 1 ≤ i ≤ k. We extend then φ to G as follows :

1. We define φ G (v) = φ H (v) for all v ∈ V \ {w, u 1 , . . . , u k }. w ≥ i d G (u i ) -k + 1 u 1 ≥ d G (w) + 1 u 2 u k ≤ r + k -k i=1 d G (u i ) ≤ r -d G (w)
. . . 2. We define φ G (w) to be a color different from all of those of the vertices of

F w = k i=1 N G (u i ) \ {w} N * H (w)
. Since G has girth at least 8, we have

|F w | = k i=1 (d G (u i ) -1) + d * H (w) = k i=1 (d G (u i ) -1) + d * G (w) -k i=1 d G (u i ) = d * G (w) -k.
By hypothesis, we have d * G (w) ≤ r + k and thus |F w | ≤ r. Thus, we have r + 1 colors and at most r are forbidden, so it remains at least one color for w.

3. We then define φ G (u k ) to be a color different from those that appear on

F u k = N * H (u k ) ∪ N H (w) ∪ {w}. Since d * G (u i ) ≤ r + i -1, we have d * H (u i ) ≤ r + i -1 -d G (w). Therefore, we have |F u k | = d * H (u k ) + d H (w) + 1 ≤ (r + k -1 -d G (w)) + d H (w) + 1 = (r + k -1 -d G (w)) + (d G (w) -k) + 1 = r.
So it remains at least one color for u k .

4. One by one (from k -1 to 1), we define φ G (u i ) to be a color different from those that appear on

F u i = N * H (u i ) ∪ N H (w) ∪ {w, u i+1 , u i+2 , . . . , u k }.
Using similar argument as the previous subcase, |F u i | ≤ r and thus it remains at least one color for each u i .

Observe that we 2-distance colored the vertices w, u 1 , . . . , u k . Hence the obtained coloring φ G is r-hued. Lemma 7. Graph G has no 4 + -paths.

Proof. Suppose G contains a 4-path stuvwx (see Figure 6). Then d * (u) = d * (v) = 4 < r which contradicts Lemma 6.

x s w v u t Proof. Consider a 2-path uxyw (see Figure 8). Suppose by contradiction that d(w) = r and d(u) / ∈ {r -1, r}.

If d(u) ≤ r -2, then d * (x) = d(u) + 2 ≤ r. So, by Lemma 6, d * (y) = d(w) + 2 ≥ r + 2 meaning that d(w) > r.
By minimality of G, we color G -{x, y}. Observe that w is already r-hued. We 2-distance color x (u and y become r-hued), and we color y with a color different from that of u, x, and w (x becomes r-hued).

If d(u) ≥ r + 1, then we color G -{x, y}. Observe that u is r-hued. Either d(w) ≥ r + 1 (in that case w is already r-hued) and we color y with a color different from that of w and u, or d(w) ≤ r -1 and we 2-distance color y. Finally we color x with a color different from the colors of u, y, and w. w u y x Proof. Suppose that G contains a cycle consisting of k 3-paths (see Figure 9). We remove all vertices v 4i+1 , v 4i+2 , v 4i+3 for 0 ≤ i ≤ k -1. Consider a coloring of the resulting graph. We color v 1 , v 3 , v 5 , . . . , v 4k-1 . This is possible since each of them has at least two choices of color (as Lemma 8) and by 2-choosability of even cycles. This procedure ensures that every vertex with even index is r-hued. Finally, it is easy to color greedily v 2 , v 6 , . . . , v 4k-2 since they each have at most four forbidden colors (ensuring that every vertex with odd index is r-hued).

d(v 0 ) = d(v 4 ) = • • • = d(v 4(k-1) ) = r due to
v 4 v 0 v 3 2 v 2 r -3 v 1 2 2 v 4j v 4(j+1) v 4k-1 2 Figure 9: A cycle consisting of consecutive 3-paths. Lemma 11. Let v be a vertex such that 3 ≤ d(v) ≤ r+1 2 . Then v cannot be a (2, 1 + , 1 + , . . . , 1 + )- vertex. Proof. Suppose that G contains a vertex v with 3 ≤ d(v) ≤ r+1 2 that is a (2, 1 + , 1 + , . . . , 1 + )- vertex.
Let w be a neighbor of v that belongs to a 2-path. See Figure 10. We have

d * (w) = d(v)+2 and d * (v) = 2d(v). Moreover, as d(v) ≤ r+1 2 , it follows that d * (w) ≤ r since r > 3. Thus, d * (v) ≥ r + 2 by Lemma 6. Since d(v) is an integer and 2d(v) ≥ r + 2, d(v) ≥ r+2 2 which contradicts d(v) ≤ r+1 2 .
v w Proof. Recall that the endvertex of a 3-path always have degree r by Lemma 8. Also, at least one endvertex of a 2-path has degree r unless they both have degree r -1 by Lemma 9. Thus, x, y, and v always have degree r in what follows (r ≥ 9). By minimality of G, let φ be an r-hued

coloring of G = G-{a, b, c, u, v, w, a , b , c , v }. Observe first that, since d * (b) < r + 1, d * (v) < r + 1, d * (b ) < r + 1, vertices b, v, b

Discharging rules

In this section, we define the discharging procedure that contradicts the structural properties of G (see Lemmas 6 to 13) showing that G does not exist.

Definition 14 (Small, medium, and large 2-vertex). A 2-vertex v is said to be

• large if it is adjacent to two 3 + -vertices,
• medium if it is adjacent to exactly one 2-vertex,

• small if it is adjacent to two 2-vertices.

Definition 15 (Bridge vertex).

A large 2-vertex is called a bridge if it has a 3-neighbor and a 8 + -neighbor.

Definition 16 (Sponsor). Consider the set of 3-paths in G. By Lemma 8, the endvertices of every 3-paths are r-vertices and by Lemma 10, the graph induced by the edges of all the 3-paths of G is a forest F. For each tree of F, we choose an arbitrary root. Each small 2-vertex v is assigned a unique sponsor which is the r-vertex corresponding to the grandson of v. See Figure 13. Definition 17 (Special and non-special vertices). A (3 ↔ 5)-vertex is said to be special if it has at least two r-neighbors and non-special otherwise.

root sponsor

We first assign to each vertex v the charge µ(v) = 3d(v) -8 and to each face f the charge µ(f ) = d(f ) -8. By Equation (2), the total sum of the charges is negative. We then apply the following discharging rules (R1 to R9):

Vertices to vertices: R0 (see Figure 14): (i) Every 3 + -vertex gives 1 to its large 2-neighbors, and 2 to its medium 2-neighbors.

(ii) Every sponsor gives 1 to its small 2-neighbors. R9 (see Figure 19): Each 8 + -face f incident to a path v 1 v 2 . . . v 7 as described in R5 gives 1 to v 4 . (viii) u is a (1, 1, 0)-vertex, or a (1, 0, 0)-vertex.

Verifying that charges on vertices and faces are non-negative

Let µ * be the assigned charges after the discharging procedure. In what follows, we prove that: ∀x ∈ V (G) ∪ F (G), µ * (x) ≥ 0.

Faces

Let f be a face of G. Recall that µ(f ) = d(f ) -8. We consider two cases according to the length of f :

Case 1: d(f ) ≥ 9.
Note that f may give 1 2 (resp. 1 2 , 1) by R7 (resp. R8, R9). By R9 (resp. R8, R7), face f may give 1 (resp. 1 2 , 1 2 ) at most d(f ) 6 (resp. d(f ) 4 , d(f ) 8 ) times. Observe that in Figures 19 to 21 except the r-vertices (u , w , x 1 , x 5 , v 1 , v 7 ), all other vertices are pairwise distinct. Therefore, assuming that R9 (resp. R8, R7) is applied i (resp. j, k) times, we must have d(f ) ≥ 6i + 4j + 8k.

Observe that: µ * (f ) ≥ d(f )-8-i-j 2 -k 2 ≥ 6i+4j+8k-8-i-j 2 -k 2 ≥ 5i+ 7 2 j+ 15 2 k-8 ≥ 0 when i ≥ 2 or k ≥ 2 or j ≥ 3 or (j ≥ 1 and i = 1) or (j ≥ 1 and k = 1) or (i = 1 and k = 1). Now observe that for the remaining cases:

µ * (f ) ≥ d(f ) -8 -i -j 2 -k 2 ≥

Figure 1 :

 1 Figure 1: A graph G with χ 2 (G) = 6 and χ(G) = 3.

  The Moore graph of type (3,2): the Petersen graph. (iii) The Moore graph of type (7,2): the Hoffman-Singleton graph.

Figure 2 :

 2 Figure 2: Examples of Moore graphs for which χ 2 = ∆ 2 + 1.

Figure

  Figure 3: Graphs with χ 2 ≈ 3 2 ∆

5 (Figure 4 :

 54 Figure 4: A graph G with ∆ = 5.

Figure 5 :

 5 Figure 5: The configuration of Lemma 6.

Figure 6 :Lemma 8 .Figure 7 :Lemma 9 .

 6879 Figure 6: A 4-path.

Figure 8 :

 8 Figure 8: A 2-path.

Figure 10 : 2 . 12 . 4 Figure 11 :

 10212411 Figure 10: A (2, 1 + , . . . , 1 + )-vertex v with 3 ≤ d(v) ≤ r+1 2 .

( a )

 a Consider the configuration depicted on Figure 11(i) where d(w) ≤ r -2. By minimality of G, let φ be an r-hued coloring of G = G -{a, b, u, v}. Let us start coloring a and u. Both vertices have r -2 + 1 = r -1 restrictions coming from x. Additionally, a (resp. u) has one restriction from c (resp. w). As φ(c) = φ(w) (since d(y) = r), one can color a and u with two distinct colors. Finally, b and v can always be 2-distance colored since b only has four restrictions on its number of colors, and v always has at least one choice of color as d(w) ≤ r -2. The obtained coloring is r-hued. That contradiction completes the proof. (b) Consider the configuration depicted on Figure 11(ii).

( c )Lemma 13 .Figure 12 :

 c1312 Figure 12: A (2, 1, 0)-vertex having a 7-neighbor.

Figure 13 :

 13 Figure 13: The sponsor assignment in a tree consisting of 3-paths.

Figure 14 :

 14 Figure 14: R0.

Figure 15 :

 15 Figure 15: R1.

Figure 16 :. 8 + 5 2Figure 17 1 Figure 18 1 Figure 19 :

 168517118119 Figure 16: R2.

Figure 20

 20 Figure 20: R7.

Figure 21

 21 Figure 21: R8.

Figure 22 :

 22 Figure 22: R6.

Table 1 :

 1 The latest results with a coefficient 1 before ∆ in the upper bound of χ 2 .

	3: Graphs with χ 2 ≈ 3 2 ∆
	3

  can be 2-distance colored at the end. Vertices a, u, a have the same r -2 restrictions coming from x ; they must be colored with the last three available colors, say α 1 , α 2 , α 3 . Similarly c and w (resp. c and v ) have the same r -1 restrictions coming from y (resp. v ) ; they must be colored with the last two available colors, say β 1 and β 2 (resp. γ 1 and γ 2 ). Now, if β 1 does not occur in {α 1 , α 2 , α 3 }, then one can sequentially color c with β 1 , then w, v , u, c , a , and a. So by symmetry, we have {β 1 , β 2 } ⊂ {α 1 , α 2 , α 3 } and {γ 1 , γ 2 } ⊂ {α 1 , α 2 , α 3 }. If follows that {β 1 , β 2 } and {γ 1 , γ 2 } have at least one common element, say β 1 = γ 1 . Hence we color the vertices as follows : c with β 1 , w with β 2 , v with γ 1 = β 1 , c with γ 2 (which may be equal to β 2 ), a with β 1 , a with β 2 , and u with the color of {α 1 , α 2 , α 3 \ {β 1 β 2 }. That leads to an r-hued coloring of G, a contradiction.

For G connected and different from C 5 .

Corollaries of results on r-hued list-colorings of graphs with a bounded maximum average degree.

Corollaries of results on r-hued list-colorings of planar graphs.

Corollaries of results on r-hued coloring of graphs with a bounded maximum average degree.

This is our result (see Theorem 4).

(iii) Every 8 + -vertex gives 1 to its adjacent bridges. R1 (see Figure 15): (i) Every 8 + -vertex gives 2 to its 3-neighbors.

(ii) Every (5 ↔ 7)-vertex v gives 1 to its 3-neighbors.

(iii) Every bridge gives 1 to its 3-neighbor. R2 (see Figure 16):

(i) Every 8 + -vertex gives 2 to its 4-neighbors.

(ii) Every (6 ↔ 7)-vertex gives 1 to its 4-neighbors. R3 (see Figure 17): Every 8 + -vertex gives 2 to its 5-neighbors. R4 (see Figure 18): Every special vertex gives 1 to its r-neighbors.

Vertices to faces: R5 (see Figure 19): Each 8-face

, receives charge 1 2 from v 1 and v 7 . R6 (see Figure 22): Let f = xabcywvu be an 8-face where xabcy is a 3-path.

(i) If xuvw is a 2-path with d(w) ≥ r -1, then y gives 1 2 to f . (ii) If xuv is a 1-path with d(v) ≥ 4, then x gives 1 2 to f . (iii) If xuv is a 1-path with d(v) = 3 and d(w) ≤ 5, then v gives 1 2 to f . (iv) If xuv is a 1-path with d(v) = 3 and d(w) ≥ 6, y gives 1 2 to f . (v) If d(u) ≥ 6 and d(w) ≥ 3, then x gives 1 2 to f . (vi) If 4 ≤ d(u) ≤ 5 and d(w) ≥ 3, then u gives 1 2 to f . (vii) If d(u) = 3 and d(v) ≥ 3, then u gives 1 2 to f . (viii) If u is a (1, 1, 0)-vertex, or a (1, 0, 0)-vertex, with d(v) = 2, and d(w) ≥ 3, then u gives 1 2 to f . Faces to faces: R7 (see Figure 20): Let f = xabcywvu be an 8-face where xabcy is a 3-path, and u and w are (2, 1, 0)-vertices (with the 1-path in common). Let u , u , and u (resp. w , w , and w ) be, respectively, the 1-distance, 2-distance and 3-distance neighbor of u (resp. w) along its incident 2-path. We also suppose that u = w . Let f be the 9 + -face incident to u u u uvww w w . Face f gives 1 2 to f . Faces to vertices: R8 (see Figure 21): Each face f gives 1 2 to each of its incident small 2-vertices 11 .

11 f gives 1 2 twice to a small 2-vertex if that vertex is only incident to f .

Suppose f is not incident to a 3-path. It follows that f is involved only in R5 and R9. Observe that if R9 applies, then R5 applies. In all cases, we have either µ

Suppose that f is incident to a 3-path. By Lemma 10, f has only one such path on its boundaries. Face f gives once 1 2 by R8 (and R9 cannot be applied). We show now that f receives 1 2 by R6 or R7. Let f = xabcywvu where xabcy is a 3-path. • If f is also incident to a 2-path of the form xuvw, then f gets 1 2 by R6(i) (see Figure 22(i)). Note that the case where d(w) ≤ r-2 does not occur by Lemma 12(i).

• If f is incident to a 1-path of the form xuv, then f gets 1 2 by R6(ii), (iii), or (iv) (see Figure 22(ii), (iii), (iv))).

• If f is incident to a 1-path of the form uvw and d(u) > 3, then f gets 1 2 from R6(v) or (vi) (see Figure 22(v), (vi)). If d(u) = 3, then u is either a (1, 1, 0)-vertex, or a (1, 0, 0)-vertex, or a (2, 1, 0)-vertex. By symmetry, the same reasoning holds for w. If one of them is a (1, 1, 0)-vertex, or a (1, 0, 0)-vertex, then f gets 1 2 by R6(viii) (see Figure 22(viii)). If both of them are (2, 1, 0)-vertices, then we are in Configuration R7 (see Figure 20) with u = w by Lemma 12(iii). In that case, f also receives 1 2 . So, we have in all cases:

• In the remaining case, f receives 1 2 by R6(v), (vi) or (vii) (see Figure 22(v), (vi), (vii)).

Vertices

Observation 18. Consider a special (3 ↔ 5)-vertex u adjacent to an r-vertex v. It follows that R4 applies, so u gives 1 to v. In return, if d(u) = 3 (resp. d(u) = 4, d(u) = 5), then v gives 2 to u by R1(i) (resp. R2(i), R3). Additionally, u may give 1 2 (at most twice) along uv to incident faces by R6(vi), (vii) or (viii) (see Figure 23). To sum up, when R4 applies, u does not lose charge along uv, as in the worst case 2 -1 -2 • 1 2 = 0. Moreover, when R6 does not apply, u gains 2 -1 = 1. Case 1:

and v gives at most 2 to each adjacent vertex by R0(i), R1(i), R2(i), R3 or a combination of R0(i) and (iii) (in the case of a bridge). Hence,

Suppose now that d(v) = r. Additionally, v also gives charges to faces by R5 and R6 and to sponsored small 2-vertices by R0(ii). Using the same idea as before, we show that v gives at most 2 along each incident edge.

When R5 is applied to v, w.l.o.g. v 1 = v in Figure 19, one sends 1 2 to f via the edge v 1 v 8 . The edge v 1 v 8 belongs to two faces, hence v 1 v 8 may be involved twice by R5. If v 8 has degree at least 6, no additional charge transits via v 1 v 8 . If v 8 is a (3 ↔ 5)-vertex, then v 1 gives 2 to v 8 by R1(i), R2(i), and R3, but it receives 1 by R4 since v 8 would be special as v 1 , v 7 are r-vertices. If v 8 has degree 2, then only 1 may transit by R0(i). In all cases, at most 2 transits from v 1 along v 1 v 8 .

Consider now that R6 is applied to v. As previously, we show that the charge 1 2 is given to f via a particular edge on which at most 2 transits. Rule R6 is applied to v in the cases R6(i), R6(ii), R6(iv), and R6(v). Observe that no charge is given to 6 + -vertices. Hence charge 1 2 transits (at most twice) along edge yw in R6(i) and R6(iv), along edge xu in R6(v). In case R6(ii), charge 1 2 transits (at most twice) along edge xu and x = v gives 1 to u by R0(i). Again at most 2 transits along each incident edge.

Finally, vertex v can sponsor at most one small 2-vertex by the definition of the sponsor relation and R0(ii). It follows that:

Observe that v may send 1 by R1(ii), R2(ii), and R0(i) in the case of the 1-path, and may send 2 by R0(i) in the case of the 2-path. As µ(v) = 13, µ * (v) ≥ 0 except in the case where v is incident to seven 2-paths, but in that case d * (v) = 14, contradicting Lemma 6 (that implies d * (v) ≥ 17).

Case 3: d(v) = 6. Vertex v may give 1 (resp. 2, 1, 1) by R0(i) in the case of the 1-path (resp. R0(i) in the case of the 2-path, R1(ii), R2(ii)). As µ(v) = 10, µ * (v) ≥ 0 except in the case where v gives 2 to each of five of its neighbors and gives at least 1 to its last neighbor, but in that case d * (v) ≤ 14, contradicting Lemma 6 (that implies d * (v) ≥ 15). ) by R0(i) in the case of the 1-path (resp. R0(i) in the case of the 2-path, R1(ii), R4 when it is a special vertex, and R6(vi)) and may receive 2 (resp. 1) by R3(i) (resp. R9). Recall µ(v) = 7.

Suppose that R6(vi) is applied to v (v plays the role of u in Figure 22(vi)). Let us use the notations of Figure 22(vi). Hence u gives 1 2 to f (let say via the edge ux). It may give 1 to x by R4 (if u is special), and receives 2 from x by R3. Moreover R6(vi) may be applied to the two faces incident to ux. When we sum the charges transiting along ux, u may give at most 2 • 1 2 -2 + 1 = 0. Hence in the following we consider that, if R6(vi) is applied to u, no charge is transferred along ux.

By Lemma 11, v is not a (2, 1 + , 1 + , 1 + , 1 + )-vertex. Hence v is incident to at most four 2paths. If v is incident to four 2-paths, then v receives 1 from three incident faces by R9 and may give at most 2, 2, 2, 2, 1 along incident edges ; so µ * (v) ≥ 7 + 3 -4 • 2 -1 = 1. If v is incident to exactly three 2-paths, then v receives at least 1 by R9 and may give at most 2, 2, 2, 1, 1 along incident edges ; so µ * (v)

Vertex v may give 1 (resp. 2, 1, 1 2 ) by R0(i) in the case of the 1-path (resp. R0(i) in the case of the 2-path, R4, R6(vi)) and may receive 2 (resp. 1, 1) by R2(i) (resp. R2(ii), R9). Recall µ(v) = 4. Similar to 5-vertices, if R6(vi) is applied to v, then no charge is transferred along the edge linking v and the r-vertex. By Lemma 11, v is not a (2, 1 + , 1 + , 1 + )-vertex. Hence, v is incident to at most three 2-paths.

If v is incident to three 2-paths, then v is not special, v receives 1 from two incident faces by R9 and gives 2, 2, 2, 0 along incident edges ; so µ

Suppose now that v is incident to two 2-paths. If v is not incident to a 1-path, then we are done as µ * (v) = 4 -2 • 2 = 0 whether v is special or not due to Observation 18. So consider that v is incident to exactly one 1-path by Lemma 11 and so is not special. The 3 + -neighbor of v has degree at least 6 (otherwise it contradicts Lemma 6, d * (v) ≤ 11 while we must have d * (v) ≥ 12), then it gives at least 1 to v by R2 and so µ

Finally assume that v is incident to at most one 2-path. If v gives at most one along each incident edge, then we are done (as µ * (v) ≥ 4 -4 • 1 ≥ 0). So assume that v gives 2 to one of its neighbors. In that case, it means that R0(i) applied and v is thus incident to exactly one 2-path. Since v is not a (2, 1 + , 1 + , 1 + )-vertex, it may be incident to at most two 1-paths. If v is incident to a 2-path and two other 1-paths, then v is not special. Hence we have

Vertex v may give 1 (resp. 2, 1 2 , 1) by R0(i) in the case of the 1-path (resp. R0(i) in the case of the 2-path, R6, R4) and may receive 2 (resp. 1, 1, 1) by R1(i) (resp. R1(ii), R1(iii), R9). Recall µ(v) = 1. By Lemma 11, v is not a (2, 1 + , 1 + )-vertex. Let us examine all possible configurations for v.

-Suppose that v is a (2, 2, 0)-vertex. Let v 1 , v 2 , and u be the two 2-neighbors and 3 +neighbor of v respectively. Since v is not special, R4 does not apply. Vertex v does not fall into any configuration of R6, so R6 does not apply. Vertex v gives 2 to each of its 2-neighbors by R0(i). By Lemma 9, the other endvertices of the two 2-paths are r-vertices; so v falls into the configuration in R9 and receives 1 from an incident face. Moreover,

By R1(i), v receives 2 from u. In total, we have

-Suppose that v is a (2, 1, 0)-vertex. Let v 1 , v 2 , and u be the two 2-neighbors (where v 1 belongs to the 2-path and v 2 belongs to the 1-path) and 3 + -neighbor of v respectively. As previously, v is not special. Vertex v 1 has d * (v 1 ) = 5 ≤ r. By Lemma 6, d * (v) ≥ 11, and d * (v) = d(u) + 4, so d(u) ≥ 7. It follows that R6 does not apply (in particular R6(iii)).

If d(u) ≥ 8, then v receives 2 from u by R1(i). Hence, by R0(i) and R1(i), we have:

If d(u) = 7, then v receives 1 from u by R1(ii). Moreover, the neighbor of v 2 (different from v) has degree at least 8 by Lemma 13. Hence v receives 1 from v 2 by R1(iii). It follows that:

-Suppose that v is a (2, 0, 0)-vertex. Let x 1 , x 2 be the 0-path neighbors of v and v 1 be the 2-path neighbor of v.

Suppose first that v is not concerned by R6(vii) (i.e. v only gives charge to vertices).

Vertex

Note that, if v is non-special, then R4 does not apply and v receives at least 1 from x 1 by R1(i) or R1(ii); if v is special, then d(x 1 ) = d(x 2 ) = r, v gives 1 to x 1 and x 2 by R4 and receives 2 from x 1 and x 2 by R1(i). In both case, we can consider that v receives at least 1 from

Suppose now that R6(vii) is applied to v. Observe that R6(vii) is applied once. If v is non-special, then v receives 2 from its r-neighbor by R1(i); if it is special, by the same arguments as in the previous paragraph, we can consider that v receives 1 from both x 1 and x 2 (by R1(i) and R4). So

-Suppose that v is a (1, 1, 1)-vertex. Note that only R0(i), R1(iii), and R6(iii) may concern v. Vertex v gives 1 to each 2-neighbor by R0(i) and 1 2 to at most one incident face by R6(iii) and Lemma 12(ii). Let vxw be a 1-path incident to v. We have d * (v) = 6 ≤ r. It follows that d * (x) ≥ 11 by Lemma 6 and as d * (x) = d(w) + 3, we have d(w) ≥ 8, meaning that R1(iii) applies. Thus,

-Suppose that v is a (1, 1, 0)-vertex. Let vv 1 w 1 and vv 2 w 2 be the two 1-paths incident to v and let u be the 3 + -neighbor of v. Note that v is not special, and it may be concerned by R0(i), R1, R6(iii), and R6(viii).

Suppose first that v is not concerned by R6 (i.e. v only gives charge to vertices). By R0(i), v gives 1 to each of its 2-neighbors.

If d(u) ≥ 5, then we have by R1(i) and R1(ii):

Suppose that R6(iii) or R6(viii) is applied to v.

Assume we are in configuration R6(viii). Vertex v gives 1 to each of its 2-neighbors and 1 2 to at most three incident faces (by a combination of R6(iii) and R6(viii)), and receives 2 from u by R1(i). If it gives charge to three faces, then w 1 and w 2 are also endvertices of a 3-path, meaning that they are of degree r ≥ 8. By R1(iii), v receives 1 from each bridge v 1 and v 2 . Thus,

Now, if v only gives charge to at most two faces, then we have:

Assume we are in configuration R6(iii) (only, otherwise we are in the previous case). Let us reuse the notation of Figure 22. Observe that either w has degree 2 and u and w are two bridges (since x and y are r-vertices), or w is a (3 ↔ 5)-vertex and the endvertices of the 1-paths incident to v (different from v) are 8 + -vertices by Lemma 6 implying that the 2-neighbors of v are bridges. Hence if R6(iii) is applied at most twice, we have by R0(i) and R1(iii):

Now, if R6(iii) is applied three times, then we obtain the configuration depicted by Figure 11(iv) which is forbidden by Lemma 12.

-Suppose that v is a (1, 0, 0)-vertex. Let u, v 1 , and v 2 be its 2-neighbor and the two 3 +neighbors of v, respectively. First note that each time R4 applies, by Observation 18, in the worst case, the total number of charges transferred via vv 1 and vv 2 is 0. So, µ * (v) ≥ 1 -1 = 0 Suppose now that R6(iii), (vii) or (viii) is applied to v (which is not special).

If R6(vii) or R6(viii) is applied to v, then (at least) one of the 3 + -neighbors of v is an r-vertex. So v gains 2 by R1(i). It follows that

Suppose now only R6(iii) is applied to v. Observe that R6(iii) may be applied at most twice. Vertex v receives 1 from the bridge by R1(iii). Hence,

-Suppose that v is a (0, 0, 0)-vertex. If R4 is applied (i.e. v is special), then v does not need any charge by Observation 18. Suppose that v is not special. Vertex v may give charge to faces only by R6(vii) and in that case it receives 2 from its r-neighbor by R1(i). It follows that:

Case 7: d(v) = 2.

We have µ(v) = -2. Vertex v receives 2 by R0(i) unless v is a small 2-vertex. When v is small, it receives 1 from its sponsor by R0(ii) and twice 1 2 from incident faces by R8. Now if v is a bridge, then it also gives 1 to a 3-vertex by R1(iii), but it also receives 1 from R0(iii). In all cases, µ * (v) = 0.

To sum up, we have proven that we started out with a negative total number of charge, and after the discharging procedure that preserves this sum, we end up with a non-negative one, a contradiction. That completes the proof of Theorem 4.


Thai Ha-Huy
email: thai.hahuy@univ-evry.fr

Nhat-Thien Tran

A simple characterization for sustained growth *

Keywords: Sustained growth, non-convex dynamic programming, super-modularity JEL classication: C61, O40, O41

This article considers an inter-temporal optimisation problem in a general form and gives conditions ensuring the convergence to innity of the economy. These conditions can be easily veried and applied for a large class of problems in the literature. Some applications for dierent economies are given as illustrative examples.

Introduction

Initiated by Bellman [START_REF] Bellman | Dynamic Programming[END_REF], the dynamic programming literature has rapidly become a workhorse of economic dynamic analysis. The traditional approach, culminating in Stokey and Lucas (with Prescott) in [START_REF] Stokey | Recursive methods in economic dynamics[END_REF], gives a good explanation for and prediction of many economic phenomena. The theory of dynamic programming described in Stokey and Lucas (with Prescott) [START_REF] Stokey | Recursive methods in economic dynamics[END_REF] is based on a relatively strong structure of convexity. One of its implications is that in general, the economy converges to a steady state independently of the initial state.

Many studies have shown congurations where this strong convex structure is not satised. Clark [START_REF] Clark | Economically Optimal Policies for the Utilization of Biologically Renewable Resources[END_REF], Majumdar and Mitra [START_REF] Majumdar | Dynamic optimisation in non-convex models with irreversible investment: monotonicity and turnpike result[END_REF], Majumdar and Nermuth [START_REF] Majumdar | Dynamic optimisation with a Non-Convex Technology: The Case of a Linear Objective Function[END_REF], and Skiba [START_REF] Skiba | Optimal growth with a convex-concave production function[END_REF] consider economies where production functions exhibit an early phase of increasing returns, usually known as convex-concave functions. Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregated model with a non-concave production function[END_REF] extend their works to a general non-concave production function.

These works prove the existence of a critical level of capital stock, usually named the "Dechert-Nishimura-Skiba" point 1 . Beginning with a level capital stock under the Dechert-Nishimura-Skiba point, the economy shrinks and collapses to zero, otherwise it increases to a steady state 2 .

Kamihigashi and Roy [START_REF] Kamihigashi | Dynamic optimisation with a nonsmooth, nonconvex technology: the case of a linear objective function[END_REF] extend the analysis to a larger class of production function, by assuming only the upper-semi continuity. They characterise the critical point below which the economy collapses in the long run and above which survival (bounded away from zero) is possible.

Another line of the literature studies conditions allowing the convergence to innity of the economy. Jones and Manuelli [START_REF] Jones | A convex model of equilibrium growth: theory and policy implications[END_REF], [START_REF] Jones | The source of growth[END_REF] work with concave production function which keeps suciently high productivity even with a large accumulation of capital. Under this condition, the economy always converges to innity. Kamihigashi and Roy [START_REF] Kamihigashi | A nonsmooth, nonconvex model of optimal growth[END_REF] relax not only the concavity but also the continuity of production, and prove that under the condition that the productivity is suciently high for a large accumulation of capital stock, if the initial state of the economy is higher than a critical level, it will increase to innity 3 . Majumdar and Nermuth [START_REF] Majumdar | Dynamic optimisation in non-convex models with irreversible investment: monotonicity and turnpike result[END_REF], Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregated model with a non-concave production function[END_REF], Mitra and Ray [START_REF] Mitra | Dynamic optimisation on a non-convex feasible set: some general results for non-smooth technologies[END_REF], and Kamihigashi and Roy [START_REF] Kamihigashi | A nonsmooth, nonconvex model of optimal growth[END_REF] use the notion of net gain function, representing the discounted net returns on investment. They prove that the economy always evolves to increase the value of net gain function. It is interesting and surprising to see how the use of this notion provides such rich results, and it gives us deep insights in economic dynamics.

Roy [START_REF] Roy | On sustained economic growth with wealth eects[END_REF] studies an economy with wealth eects, where the utility depends not only on the consumption but also on the capital level. He proves that the if the sum of the marginal rate of substitution between capital-consumption and the productivity overcomes the discount rate, beginning with a suciently high level of capital accumulation, the economy does not stop accumulating and, hence, converges to innity.

In this article, we consider the same question about conditions ensuring sustained growth, in the generalised case, i.e. where the dynamics of the economy can be characterised as a solution of

max ∞ s=0 δ s V (x s , x s+1 ) ,
where δ ∈ (0, 1) is the discount factor and V denotes the payos function.

Under mild conditions, the following condition is sucient for characterising sustained growth:

V 2 (x, x) + δV 1 (x, x) > 0, (1.1)
for every x large enough 4 .

The intuition for (1.1) is that, if choosing between saving and remaining in status quo, the saving choice always prevails, then sustained growth is possible.

The results in this article allow us to gather a large class of cases studied in the literature under the same viewpoint. It can also be applied to situations where Kamihigashi and Roy's [START_REF] Kamihigashi | A nonsmooth, nonconvex model of optimal growth[END_REF] techniques for one-sector economy can not be used, for example, two-sector economies, the economy with wealth eects presented by Roy [START_REF] Roy | On sustained economic growth with wealth eects[END_REF] and the capitalism spirit of Kamihigashi [START_REF] Kamihigashi | The spirit of capitalism, stock market bubbles and output uctuations[END_REF], or an economy with accumulation of human capital, presented in this article.

The article is organised as follows. Section 2 presents the fundamentals of the model. Under the tail-insensitivity condition, an optimal solution exists and, under the super-modularity condition, its monotonicity is ensured. Section 3 studies the conditions ensuring sustained growth, with the main one being (1.1). Section 4 concludes. Examples and proofs are given in the Appendix.

2 Fundamentals

The model

Time is discrete: s = 0, 1, 2, . . . . The discount factor is 0 < δ < 1. The technology of this economy is characterised by a correspondence Γ : R + → R + . For x 0 ≥ 0, denote by Π(x 0 ) the set of feasible paths {x s } ∞ s=0 satisfying x s+1 ∈ Γ(x s ) for all s ≥ 0.

Given capital stocks at some consecutive dates x s and x s+1 , the corresponding payo utility level at date s is V (x s , x s+1 ), where V is a real function whose domain of denition is the graph of Γ: the set (x, y), such that y ∈ Γ(x).

For a given x 0 ≥ 0, the economy solves the following inter-temporal optimisation

problem max ∞ t=0 δ s V (x s , x s+1 ) , s.c x s+1 ∈ Γ(x s ), ∀ s ≥ 0.
Denote by v the value function of this problem:

v(x 0 ) = sup Π(x 0 ) ∞ s=0 δ s V (x s , x s+1 ) .
2.2 Existence of solution and the Bell-man functional equation Assumption A1 establishes standard conditions ensuring the existence of a solution for the maximisation problem. For the detailed comments about these conditions, curious readers can refer to Le Van and Morhaim [18].

Assumption A1.

i) The correspondence Γ is non-empty, convex, compact valued, ascending 5 and upper semi-continuous.

ii) The function V is continuous on Graph(Γ) and dierentiable on its interior, strictly increasing with respect to the rst argument and strictly decreasing with respect to the second one.

iii) Non-triviality: for every x 0 > 0, there exists

{x s } ∞ s=0 ∈ Π(x 0 ) such that ∞ s=0 δ s V (x s , x s+1 ) > -∞.
iv) Tail-insensitivity: Fixed x 0 > 0, for every > 0, there exists T 0 , a neighbourhood V of x 0 , such that for every

x 0 ∈ V, any {x s } ∞ s=0 ∈ Π(x 0 ), any T ≥ T 0 : ∞ s=T δ s V (x s , x s+1 ) < .
The conditions (i), (ii) and (iii) are usual in the literature, characterising the main properties of the technology, the trade-o between consume today and invest tomorrow, and ensuring that the problem is not trivial.

The most important condition is the tail-insensitivity one. This condition not only states that the value function should be nite, but also allows the satisfaction of upper semi-continuity, which is important for the existence of a solution.

Under A1, the value function is strictly increasing and upper-semi continuous. This continuity ensures the existence of a solution for the optimisation problem.

For the details about the proof of Proposiiont 2.1, curious readers are referred to Stokey and Lucas (with Prescott) [START_REF] Stokey | Recursive methods in economic dynamics[END_REF], chapter 4. Proposition 2.1. Assume A1. Then:

i) The value function v is strictly increasing and upper-semi continuous.

ii) A solution exists.

iii) The value function satises the Bellman equation:

v(x 0 ) = max x 1 ∈Γ(x 0 ) V (x 0 , x 1 ) + δv(x 1 ) . iv) A sequence {x s } ∞ s=0 is a optimal if and only if for all s ≥ 0, v(x s ) = V (x s , x s+1 ) + δv(x s+1 ).
From now on, for x 0 ≥ 0, we denote by φ the optimal policy correspondence:

φ(x 0 ) = argmax x 1 ∈Γ(x 0 )
V (x 0 , x 1 ) + δv(x 1 ) .

Proposition 2.1 has a consequence that φ(x 0 ) is a non-empty, compact valued correspondence 6 .

Super-modularity and monotonicity

In this section, we will study the monotonicity of optimal path and optimal policy correspondence. It is intuitive to assume super-modularity, a property stating the complementarity of capital accumulations.

Assumption A2. The payo function V is strictly super modular. 7 Under the super-modularity property, the optimal policy correspondence is "increasing", as stated in Proposition 2.1. This is an important result helping the understanding of optimal paths' behaviour. The super-modularity implies that every optimal path is strictly monotonic. The result and proof of Lemma 2.1 are similar to the one-sector conguration studied in Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregated model with a non-concave production function[END_REF], and Amir [START_REF] Amir | Sensitivity analysis of multisector optimal of economic dynamics[END_REF].

Lemma 2.1. Assume A1 and A2. Then i) For every x 0 < x 0 , and

x 1 ∈ φ(x 0 ), x 1 ∈ φ(x 0 ), we have x 1 < x 1 .
ii) Every optimal path is either strictly monotonic or constant.

A direct consequence of Lemma 2.1 is that every optimal path converges either to some real value, or to innity. Moreover, Lemma 2.1 allows us to characterise a general feature of optimal paths, stated in Proposition 2.2. If, for some initial state x 0 , the optimal path converges to innity, then the same property is also satised for every greater initial level of capital stock, thanks to the monotonicity of optimal policy correspondence. If such an initial state x 0 does not exist, every optimal path is bounded from above.

Proposition 2.2. Assume A1 and A2. Then only one of the following holds:

i) There exists x ≥ 0, such that for every x 0 ≥ x, every optimal path beginning from x 0 is strictly increasing and converges to innity.

ii) for every x 0 ≥ 0, every optimal path beginning from x 0 is bounded from above. 7 The (strict) super-modularity is dened as: for every (x, x ) and (y, y ) that belong to Graph(Γ), V (x, y)

+ V (x , y )(>) ≥ V (x , y) + V (x, y ) is veried whenever (x , y )(>) ≥ (x, y).
When V is twice dierentiable, (strict) super modularity sums up to positive cross derivatives: V 12 (x, y)(>) ≥ 0 for every x, y. See Amir [START_REF] Amir | Sensitivity analysis of multisector optimal of economic dynamics[END_REF]. [START_REF] Amir | Sensitivity analysis of multisector optimal of economic dynamics[END_REF] The sustained growth condition Under Assumption A1, a solution exists. Under Assumption A2, optimal paths are monotonic. Hence, each optimal path converges either to a steady state, or to innity. If, for some x 0 , there is an optimal path beginning from x 0 that converges to innity, then this property is veried for every optimal path beginning from

x 0 > x 0 .
In this section, we discuss the condition ensuring the possibility of sustained growth, i.e., the convergence to innity of the economy. To x ideas and to simplify the exposition, we also assume that the payo function V is bounded from below. The case where V is unbounded from below will be discussed in Section 3.3.

The condition

The main idea runs as follows: staying in the status quo is better than diminishing the capital accumulation and remaining unchanging after that. Under this situation, the economic agents prefer to save and the capital increases.

Definition 3.1. The state x > 0 satises condition C if x ∈ int (Γ(x)) and V 2 (x, x) + δV 1 (x, x) > 0. (3.1)
The signicance of condition C is intuitive: for every capital accumulation level

x, between the choice of staying in status quo and saving a little, the economy prefers the latter.

Proposition 3.1 states our rst main result. The idea runs as follows 8 . Assume that condition C is satised for every x > 0. Suppose there is a strictly decreasing optimal path from some x 0 > 0. For every T ,

v(x 0 ) ≥ ∞ s=0 δ s V (x 0 , x 0 ) = V (x 0 , x 0 ) 1 -δ > V (x 0 , x 1 ) + δV (x 1 , x 1 ) 1 -δ > V (x 0 , x 1 ) + δV (x 1 , x 2 ) + δ 2 V (x 2 , x 2 ) 1 -δ • • • > T s=0 δ s V (x s , x s+1 ) + δ T +1 V (x T +1 , x T +1 ) 1 -δ .
Let T converges to innity. As V is bounded from below, the right-hand-side of the inequality converges to v(x 0 ), which leads us to a contradiction.

The Sustained growth

In this subsection, we prove that if the condition C is satised for every x > 0, then the sustained growth is ensured.

Proposition 3.1. Assume A1 and A2. Assume that every x > 0 satises condition C.

Then every optimal path beginning from x 0 > 0 is strictly increasing and converges to innity.

In opposition to the condition for sustained growth, we can also characterise the one under which the economy is always bounded.

Proposition 3.2. Assume A1 and A2. Suppose that there exists some x such that for every x > x, either x ≤ min Γ(x), or x ∈ int(Γ(x)) and

V 2 (x, x) + δV 1 (x, x) < 0.
Then for every x 0 , every optimal path beginning from x 0 is bounded.

No unbounded payoff function

By the importance of logarithmic function, in many studies, the payo function

V is assumed to be unbounded from below. Moreover, it is possible that, for example in economies with a convex-concave production function, the condition C is satised only for a suciently large level of capital accumulation. This section provides a partial response to these concerns. First, we relax the condition that

V is bounded from below.
Under a suitable conditions, without the boundeness hypothesis of payo function, the condition C ensures sustained growth. Condition (3.2) states that although the payo function is unbounded from below, the speed of convergence to minus innity when x converges to zero is not too fast 9 . Under this condition, extinction does not occur along optimal paths. Proposition 3.3. Assume A1 and A2.

i) Suppose that for every x that is suciently small, the condition C is satised. Moreover,

lim x→0 V (x, 0) -V (x, x) = 0. (3.2)
Then every optimal path beginning from x 0 > 0 is bounded away from zero.

ii) Assume further that for every x > 0, the condition C is satised. Then every optimal path beginning from x 0 > 0 is strictly increasing and converges to innity.

Part (ii) in Proposition 3.3 is a direct consequence of (i). As optimal paths are bounded away from zero, they can not be decreasing. Hence, under condition C, every optimal path converges to innity.

Corollary 3.1. Assume A1 and A2. Suppose that for every x > 0, the function V (x, •) is concave in respect to the second argument. Moreover,

lim x→0 xV 2 (x, x) = 0. (3.3)
Then every optimal path beginning from x 0 > 0 is bounded away from zero. In the economic literature, it is possible that for some small value of capital stock, the condition C is not satised. Proposition 3.4 establishes conditions ensuring sustained growth for cases where the economy begins with a suciently large level of capital.

Proposition 3.4. Assume A1 and A2. Suppose that for every x suciently large, the condition C is satised. Moreover, there exists x > 0 such that ∞ x V 2 (y, y) + δV 1 (y, y) dy = ∞.

Then there exists x such that every optimal path beginning from x 0 > x is strictly increasing and converges to innity.

Corollary 3.2 follows from Proposition 3.4.

Corollary 3.2. Assume A1, A2. Suppose that,

lim x→∞ V (x, x) = ∞.
Suppose that for some > 0, the following inequality is satised for every x that is suciently large:

-V 2 (x, x) δV 1 (x, x) ≤ 1 -.
Then there exists x such that every optimal path beginning from x 0 > x is strictly increasing and converges to innity.

Conclusions

This article establishes conditions ensuring sustained growth. The threshold beyond which the economy converges to innity is characterised. The conditions, in our subjective opinion, are simple and easy to verify. Conditions under which extinction does not occur along optimal paths are precise. We can apply them in a large class of inter-temporal optimisation problems.

The strict super-modularity in condition A2 is not only for technical convenience.

If the utility function satises only the super-modularity (but not strict), the optimal paths exhibit complicated behaviours. For example, in Kamihigashi and Roy [START_REF] Kamihigashi | Dynamic optimisation with a nonsmooth, nonconvex technology: the case of a linear objective function[END_REF], the instantaneous utility function is linear, and the optimal path reaches one steady state in a nite time and can jump between dierent steady states afterwards 10 . A careful consideration for this case is interesting, but that must be the subject of another work.

Appendix

Applications

In this section, we discuss some applications. For the details of the models, see Kahimigashi and Roy [START_REF] Kamihigashi | A nonsmooth, nonconvex model of optimal growth[END_REF], Roy [START_REF] Roy | On sustained economic growth with wealth eects[END_REF], Dana and Le Van [9] and Crettez et al [START_REF] Crettez | Optimal growth with investment enhancing labour[END_REF].

The detailed proofs can be found in the online version of this article [START_REF] Ha-Huy | A simple characterization for sustained growth[END_REF].

One sector economy

For the details, see Kahimigashi and Roy [START_REF] Kamihigashi | A nonsmooth, nonconvex model of optimal growth[END_REF]. The payo function is dened as 10 The monotonicity is not veried.

V (x, y) = u f (x) -y .
We have

V 2 (x, x) + δV 1 (x, x) = -u (f (x) -x) + δu (f (x) -x) f (x) = u (f (x) -x) (δf (x) -1) .
The condition C is equivalent to f (x) > 1 δ . This is the same condition in Kamihigashi and Roy [START_REF] Kamihigashi | A nonsmooth, nonconvex model of optimal growth[END_REF].

Proposition 5.1. Assume that i) lim inf x→∞ f (x) > 1 δ .
ii) The utility function is unbounded from above.

Then there exists x ≥ 0, such that for every x 0 ≥ x, every optimal path beginning from x 0 is strictly increasing and converges to innity.

Proposition 5.1 is a direct consequence of Proposition 3.4. It adds a complementary feature to the result of Kamihigashi and Roy [START_REF] Kamihigashi | A nonsmooth, nonconvex model of optimal growth[END_REF], which requires that lim c→∞ u (c)c < ∞ and hence rules out the constant elasticity and constant elasticity of marginal utility functions.

A two-sector economy

Consider the two-sectors economy in Dana and Le Van 11 [9]. One sector produces consumption good, characterised by function f , and the other one produces capital good, characterised by function g. Both functions are concave.

Dene ζ(x) = g -1 (x), the inverse function of g. This function is convex. The payo function is:

V (x, y) = u f x -ζ(y) .
The condition C is equivalent to ζ (x) < δ. Proposition 5.2 is a consequence of Proposition 3.4.

11 Chapter 4, page 92.

Proposition 5.2. Assume that δ(1 + λ) > 1. Then, for every x > 0, ζ (x) < δ and the optimal path beginning from x is strictly increasing, converges to innity.

The economy with wealth effects

Consider the model of economic growth with wealth eects, presented in Kamihigashi [START_REF] Kamihigashi | The spirit of capitalism, stock market bubbles and output uctuations[END_REF] and Roy [START_REF] Roy | On sustained economic growth with wealth eects[END_REF]. In this set up, the utility function depends on consumption level and capital stock level.

The indirect function is V (x, y) = u (f (x) -y, x). This function is concave. The Euler condition is equivalent to

f (x) + u x (f (x) -x, x) u c (f (x) -x, x) > 1 δ .
This is the same condition as in Roy [START_REF] Roy | On sustained economic growth with wealth eects[END_REF]. By Roy [START_REF] Roy | On sustained economic growth with wealth eects[END_REF], for x that is suciently large, the optimal policy function h satises h(x) ≥ x. We weaken the condition U1 of Roy by the following one: either u cx (c, x) ≥ 0 for every (c, x), or u cx (c, x) ≤ 0 for every (c, x). By Proposition 3.1, we obtain the same result in Roy [START_REF] Roy | On sustained economic growth with wealth eects[END_REF].

Proposition 5.3. Denote by x * the biggest steady state (if steady state does not exist, let x * = 0). Assume also that for some x > x * we have

f (x) + u x (f (x) -x, x) u c (f (x) -x, x) > 1 δ .
Then every optimal path beginning from x 0 > x * is strictly increasing and converges to innity.

Optimal growth with investment enhancing labour

We consider the optimisation problem presented by Crettez et al [START_REF] Crettez | Optimal growth with investment enhancing labour[END_REF], considering an economy with investment enhancing labour. The labour force is divided in one part to the production sector, and in other part to enhancing labour, for example the labour allocated to the nancial sector.

The payo function is dened as

V (x, y) = max u (F (x, y)) ,
where

F (x, y) = max 0≤z≤1 f (x, 1 -z) - y φ(z)
.

The condition C is equivalent to

φ (z(x, x)) f 1 (x, 1 -z(x, x) > 1 δ .
Proposition 5.4 is a consequence of Propositions 3.1 and 3.4.

Proposition 5.4. Assume that u is unbounded from above and

lim inf x→∞ - 1 φ z(x, x) + δf 1 (x, 1 -z(x, x) > 0.
Then for a large enough x, every optimal path beginning from x is strictly increasing and converges to innity.

Although the productivity is low, sustained growth may occur if the nancial sector is suciently ecient.

Optimal growth with human capital

In this section, we consider a economy where investing in human capital may yield a sustainable economic growth, presented in Tran [START_REF] Tran | An essay on human capital accumulation and economic growth[END_REF]. There is no physical capital.

The economic agent divides the production in consumption and investment in human capital, and solves the inter-temporal maximization:

max ∞ t=0 δ t u(c t ) , s.c c t + s t+1 ≤ f (h t ), h t+1 h t = ϕ(s t+1 ).
The quantities c t , s t are respectively the consumption and the saving at period t and h t is the human capital at the same period. The function ϕ represents the technology of human capital formation. It is supposed to be continuous and strictly increasing.

Let ψ(s) = ϕ -1 (s). It is the inverse function of φ. The payo function is dened as

V (x, y) = u f (x) -ψ y x .
The condition C is equivalent to

u (f (x) -ψ(1)) δf (x) -(1 -δ) ψ (1) x > 0. Proposition 5.5. i) Suppose that f (x) > 1-δ δ ψ (1)
x , for every x > 0. For every initial level of human capital, the economy converges to innity.

ii) Suppose that the utility function u is unbounded from above. Assume that

lim inf x→∞ f (x) > 0.
Then, there exists h ≥ 0 such that for all h 0 > h, every optimal path beginning from h 0 is strictly increasing and converges to innity. This proof is in line with Dechert and Nishimura [START_REF] Dechert | A complete characterization of optimal growth paths in an aggregated model with a non-concave production function[END_REF].

Suppose that there exists x 0 < x 0 , x 1 ∈ φ(x 0 ), x 1 ∈ φ(x 1 ) and x 1 ≥ x 1 . Hence x 1 ∈ Γ(x 0 ) and in the same denition as Amir [START_REF] Amir | Sensitivity analysis of multisector optimal of economic dynamics[END_REF]: (x 0 , x 1 ) = (x 0 , x 1 ) ∨ (x 0 , x 1 ), (x 0 , x 1 ) = (x 0 , x 1 ) ∧ (x 0 , x 1 ).

We have V (x 0 , x 1 ) + δv(x 1 ) ≥ V (x 0 , x 1 ) + δv(x 1 ), V (x 0 , x 1 ) + δv(x 1 ) ≥ V (x 0 , x 1 ) + δv(x 1 ).

Combining these two equations we obtain V (x 0 , x 1 ) + V (x 0 , x 1 ) ≥ V (x 0 , x 1 ) + V (x 0 , x 1 ), which is contradictory to the super-modularity assumption A2.

The monotonicity of optimal paths is a direct consequence of the monotonicity of the optimal policy correspondence.

Proof of Proposition 2.2

Assume that for some x, there exists an optimal path {x s } ∞ s=0 beginning from x that converges to innity. Then by induction, using Lemma 2.1, for all x 0 > x, every optimal path {x s } ∞ s=0 beginning from x 0 satises x s > x s for every s ≥ 0. Hence, the sequence {x s } ∞ s=0 is strictly increasing and lim s→∞ x s = ∞.

As the constant sequence (x 0 , x 0 , . . . ) belongs to Π(x 0 ), we have:

v(x 0 ) ≥ V (x 0 , x 0 ) 1 -δ > V (x 0 , x 1 ) + δ 1 -δ V (x 1 , x 1 ) > V (x 0 , x 1 ) + δV (x 1 , x 2 ) + δ 2 1 -δ V (x 2 , x 2 ) • • • > T s=0 δ s V (x s , x s+1 ) + δ T +1 1 -δ V (x T +1 , x T +1 ).
Letting T converge to innity, the right-hand-side of the inequality converges to v(x 0 ): a contradiction.

Therefore the sequence {x s } ∞ s=0 is either strictly increasing or constant. Suppose that this sequence does not converge to innity, then lim s→∞ x s = x. By the upper semi-continuity of the value function v, we have x ∈ φ(x): the limit value x is a steady state. By the Euler equation, we have V 2 (x, x) + δV 1 (x, x) = 0, a contradiction. The proof is completed. Fix a suciently large x 0 . Suppose that there is an strictly increasing optimal path beginning from x 0 . As, for a suciently large x, we have V 2 (x, x) + δV 1 (x, x) < 0, the function h(y) = V (x, y) + δV (y,y) 1-δ is decreasing in [x, ∞). Using the same argument in the proof of Proposition 3.1, we obtain:

v(x 0 ) ≥ V (x 0 , x 0 ) 1 -δ > T s=0 δ s V (x s , x s+1 ) + δ T +1 V (x T +1 , x T +1 ) 1 -δ ,
which converges to v(x 0 ) when T converges to innity: a contradiction. (i) Fix x 0 > 0 and an optimal path {x s } ∞ s=0 beginning from x 0 . Assume that this path converges to zero. This implies that for all 0 < x < x 0 , every optimal path beginning from x is strictly decreasing and converges to zero.

First, we prove the following claim: under (3.2),

lim x→∞ v(x) - V (x, x) 1 -δ = 0.
Indeed, x any > 0. By (3.2), for a suciently small x, we have

V (x, 0) < V (x, x) + (1 -δ) .
Consider an optimal path {x s } ∞ s=0 beginning from x. We have

v(x) = ∞ s=0 δ s V (x s , x s+1 ) ≤ ∞ s=0 δ s V (x, 0) < V (x, x) 1 -δ + .
As is chosen arbitrarily, the claim is proven.

We prove the second claim: for every 0 < x < x 0 , the following inequality is satised:

v(x 0 ) -v(x) < x x V 1 (y, y)dy. Consider T such that x T > x ≥ x T +1 . For 0 ≤ s ≤ T -1 we have v(x s ) -v(x s+1 ) = V (x s , x s+1 ) + δv(x s+1 ) -v(x s+1 ) ≤ V (x s , x s+1 ) + δv(x s+1 ) -V (x s+1 , x s+1 ) -δv(x s+1 ) = V (x s , x s+1 ) -V (x s+1 , x s+1 ) = xs x s+1 V 1 (y, x s+1 )dy ≤ xs x s+1 V 1 (y, y)dy.
The last inequality comes from the super-modularity: since V satises the increas-

ing dierences property, V 1 (y, y) ≥ V 1 (y, x s+1 ) for y ≥ x s+1 .
For s = T , observe that by the ascending property and the continuity of Γ,

x T +1 ∈ Γ(x). We then have

v(x T ) -v(x) ≤ V (x T , x T +1 ) + δv(x T +1 ) -V (x, x T +1 ) -δv(x T +1 ) = V (x T , x T +1 ) -V (x, x T +1 ) = x T x V 1 (y, x T +1 )dy ≤ x T x V 1 (y, y)dy. This implies v(x 0 ) -v(x) = T -1 s=0 (v(x s ) -v(x s+1 )) + (v(x T ) -v(x)) ≤ T -1 s=0 xs x s+1 V 1 (y, y)dy + x T x V 1 (y, y)dy = x 0 x V 1 (y, y)dy.
The second claim is proven. Now, we chose a suciently small x such that

v(x) - V (x, x) 1 -δ < 1 1 -δ x 0
x V 2 (y, y) + δV 1 (y, y) dy. Let = v(x) -V (x,x) 1-δ .

We have

V (x 0 , x 0 ) -V (x, x) ≤ (1 -δ)v(x 0 ) -(1 -δ)v(x) + (1 -δ) ≤ (1 -δ) v(x 0 ) -v(x) + (1 -δ)
≤ (1 -δ)

x 0

x V 1 (y, y)dy + (1 -δ) .

This implies

x 0

x (V 1 (y, y) + V 2 (y, y)) dy ≤ (1 -δ)

x 0 x V 1 (y, y)dy + (1 -δ) ,
which is equivalent to (ii) Fix any x 0 > 0. Suppose that there exists an optimal path {x s } ∞ s=0 beginning from x 0 that is decreasing or constant. In the former case, by part (i), this path is bounded away from zero. Using the same arguments in the proof of Proposition 3.1, we have lim T →∞ δ T V (x T , x T ) = 0, which implies V (x 0 , x 0 ) > (1 -δ)v(x 0 ): a contradiction. In the later case, since x 0 ∈ int(Γ(x 0 )), the Euler equation give V 2 (x 0 , x 0 ) + δV 1 (x 0 , x 0 ) = 0: a contradiction. Consider some x 0 > x and an optimal path {x s } ∞ s=0 beginning from it. If there exists T such that x T ≥ x > x T +1 , using the same arguments as in the proof of Proposition 3.3, we obtain (1 -δ) Hence, the path {x s } ∞ s=0 is bounded from below by x. Using the same arguments as in the proof of Proposition 3.1, the sequence {x s } ∞ s=0 must be strictly increasing and converges to innity. Obviously, the condition in the statement implies that V 2 (x, x) + δV 1 (x, x) > 0 for x > x * . As V 2 (y, y) ≤ 0 for all y and V (x, x) -V (x * , x * ) = The condition in the statement also implies that for x > x * , V 2 (x, x) + δV 1 (x, x) ≥ V 1 (x, x).

Corollary 3 .

 3 1 follows from the result that under the concavity hypothesis, (3.3) implies (3.2).

5. 2

 2 Proofs 5.2.1 Proof of Lemma 2.1

5. 2 . 4

 24 Proof of Proposition 3.2

5. 2 . 5

 25 Proof of Proposition 3.3

(V 2

 2 (y, y) + δV 1 (y, y)) dy ≤ (1 -δ) , a contradiction. The sequence {x s } ∞ s=0 is bounded away from zero.

5. 2 . 6

 26 Proof of Corollary 3.1By the concavity of V (x, •) with respect to the second argument, we haveV (x, 0) -V (x, x) ≤ -xV 2 (x, x).Then (3.3) implies (3.2).

5. 2 . 7

 27 Proof ofProposition 3.4 Fix any x > 0 such that everyx 0 > x satises condition C. Fix x > x such that v(x) -V (x, x) 1 -δ < x xV 2 (y, y) + δV 1 (y, y) dy.

V 2

 2 (y, y) + δV 1 (y, y) ≤ (1 -δ)v(x) -V (x, x), a contradiction.

5. 2 . 8

 28 Proof of Corollary 3.2

V 1

 1 (y, y) + V 2 (y, y) dy, we have∞ x * V 1 (y, y)dy = ∞.

  (y, y) + δV 1 (y, y)) dy ≥ ∞ x * V 1 (y, y)dy = ∞.The proof is completed by applying Proposition 3.4.

For a more detail survey, see Akao et al[START_REF] Akao | Monotonicity and continuity of the critical capital stock in the DechertNishimura model[END_REF].

For an analysis in continuous time, see Akao et al[START_REF] Akao | Critical capital stock in a continuous-time growth model with convex-concave production function[END_REF].

In order to cover the case where the production function is not continuous, their condition is stated on the properties of upper and under derivatives of this function.

The notations V 1 (x, y) and V 2 (x, y) denote respectively the partial derivatives corresponding to the rst and the second arguments.

For x ≤ x , y ∈ Γ(x), y ∈ Γ(x ), we have min{y, y } ∈ Γ(x) and max{y, y } ∈ Γ(x ).

As in Dechert and Nishimura[START_REF] Dechert | A complete characterization of optimal growth paths in an aggregated model with a non-concave production function[END_REF], under super-modularity condition, for x 1 ∈ φ(x 0 ), the set φ(x 1 ) is single-valued. Moreover, the value function v is dierentiable at x 1 . This implies that almost everywhere, the correspondence φ is single-valued and the value function is dierentiable. A generalisation of this result for congurations with uncertainty is given in Nishimura et al[START_REF] Nishimura | Stochastic optimal growth with nonconvexities[END_REF].

The idea is inspired by similar consideration in Cao and Werming[START_REF] Cao | Saving and dissaving with hyperbolic discounting[END_REF].

For example, in the one sector economy in Kamihigashi and Roy[START_REF] Kamihigashi | A nonsmooth, nonconvex model of optimal growth[END_REF], (3.2) is satised for logarithmic utility function and a production function satisfying Inada condition at zero.

The authors give many thanks to Ken-Ichi Akao and Carmen Camacho for their helpful comments. They also acknowledge the LABEX MME-DII (ANR-

Consider x 0 > 0 and an optimal path {x s } ∞ s=0 beginning from x 0 . By Proposition 2.1, the sequence {x s } ∞ s=0 is strictly increasing, decreasing or constant. Suppose that this sequence is strictly decreasing: x s > x s+1 for all t ≥ 0.

First, we prove that for all s ≥ 0,

Indeed, for x s+1 < y < x s , consider the function:

Since x s ∈ int(Γ(x s )), by the continuity and the compact-valued properties of the correspondence Γ, x s ∈ int(Γ(x s+1 )). The function h is well dened and dierentiable.

We have,

Hence, h(x s ) > h(x s+1 ), which implies V (x s , x s ) 1 -δ > V (x s , x s+1 ) + δV (x s+1 , x s+1 ) 1 -δ .


André Grimaldi
email: andre.grimaldi@aphp.fr

Patient expert ou patient ressource ? Expert patient or resource patient?

Keywords:

Le rôle du patient expert varie en fonction de ses missions. Il peut aider les patients, n'acceptant pas leur maladie et rencontrant des difficultés à suivre le traitement. Il leur permet de s'identifier à lui, à la condition d'avoir connu des difficultés similaires et d'avoir réussi à les surmonter. Dans une démarche d'empathie réciproque, il peut jouer le rôle de tuteur de résilience bénévole. Intégré à l'équipe de soins, il doit bénéficier d'une supervision. Il en va différemment des autres activités d'un patient expert au sein d'une association ou pour l'enseignement, ou encore pour la représentation des usagers au sein des diverses instances du système de santé.

3

Le qualificatif de « patient expert » s'est imposé dans le sillage de « l'expert profane », expression d'un double mouvement général de nos sociétés : démocratisation du pouvoir et du savoir d'un côté, relativisme scientifique et critique des experts, de l'autre [START_REF] Grimaldi | Les différents habits de l'« expert profane[END_REF]. Mais, en transformant le mot en slogan ou en « élément de langage », on s'éloigne de la réalité, de sa diversité et de sa complexité. Il convient d'abord de se demander : à qui s'adresse le qualificatif d'expert ? Aux autres patients novices ou non experts ? Sûrement pas, cela relèverait d'une certaine arrogance élitiste. Le qualificatif s'adresse à l'évidence aux autorités de santé, et plus encore aux professionnels de santé. Aux premiers, il signifie : « nous sommes concernés par vos décisions sur la santé et le système de santé. Nous voulons être consultés : rien pour nous, sans nous ! ». Aux seconds, il dit : « vous êtres des experts de la maladie, nous sommes des experts du vécu avec la maladie ». Je dois reconnaître que cette affirmation nous a pris à contre-pied. En effet, l'éthique « minimale » de tout soignant suivant des patients atteints de maladies chroniques, est que le patient n'est pas un « porteur de la maladie », mais une personne ayant une maladie. Il n'est jamais réductible à sa maladie. Or, voilà des patients qui font de leur maladie leur identité, au point d'y consacrer parfois l'essentiel de leur emploi du temps : réunions multiples, articles, conférences, formation, enseignement, recherche, militantisme associatif…

Le vécu commence avec l'annonce du diagnostic

Il s'agit en effet d'une double annonce, biomédicale et psychosociale. L'annonce d'un dysfonctionnement qu'il va falloir suppléer de façon durable par un traitement, se double de l'annonce d'une triple rupture dans la vie du patient : (1) « Ce ne sera jamais plus comme avant ». Le malade devra donc faire le deuil de l'insouciance de sa bonne santé d'avant.

(2) « Désormais vous serez différent des autres ». Le patient devra incorporer la maladie à son identité : le voilà différent aux regards des autres, et pourtant toujours le même à ses yeux.

(3) « Il va vous falloir adopter de nouveaux comportements ». Cette injonction sollicite la capacité d'adaptation du patient et met à l'épreuve son auto-observance dans la durée. Cette triple rupture, temporelle, relationnelle, et comportementale, est à l'origine d'un traumatisme psychique d'intensité variable selon la pathologie et selon les patients. Le traumatisme dépend en effet des symptômes de la maladie, douloureux ou non, des handicaps, visibles ou non, des traitements plus ou moins complexes, plus ou moins bien tolérés, plus ou moins efficaces, et finalement du pronostic. Il dépend aussi et surtout du patient : son style d'attachement dans l'enfance sécure ou insécure, jouant un rôle important dans sa confiance en soi et dans les autres, son âge, son style de personnalité optimiste ou pessimiste, angoissé ou « zen », son entourage plus ou moins aidant, sa culture, ses représentations, et surtout son rapport au temps. Que veut dire la prévention pour un adolescent pour qui dix ans est une éternité, pour un précaire qui ne sait pas où il dormira ce soir, pour un épicurien qui jouit de l'instant, pour un « ça passe ou ça casse » pour qui la vie ne vaut d'être vécue que si on peut la perdre, pour un « addict » tyrannisé par le manque… Le vécu du traumatisme psychique dépend aussi des expériences de vie antérieures, un deuil non fait rendant tout nouveau deuil particulièrement difficile.

4

son histoire de vie : retour vers la médecine narrative de la personne [START_REF] Goupy | La médecine narrative : une révolution pédagogique ?[END_REF]. À l'opposé, le mouvement post-moderne en quête de résultats comportementaux rapides grâce à des procédures standardisées et à la recherche d'efficience, souhaite se débarrasser du travail de deuil. Après avoir proposé un « deuil express », on en vient à vouloir supprimer le deuil : « souvent, le soignant miséricordieux dit « avoir une maladie chronique, c'est faire le deuil d'un état de bonne santé »… Pas facile de faire un deuil en si peu de temps. Est-ce bien nécessaire ?... Faire le deuil augmente les craintes à l'égard de la maladie… Faire son deuil de la santé devient contreproductif… » [START_REF] Giordan | Bien vivre avec sa maladie[END_REF]. Mais supprimer le mot suffit-il à faire disparaître la chose ? Comment faire ? Suffit-il de développer le présentisme grâce à la méditation en pleine conscience et aux massages ayruvédiques ? Faut-il devenir adepte du carpe diem, en vivant chaque jour comme si c'était le dernier ? Pas vraiment facile quand, en même temps, on vous enjoint de préserver votre « capital santé », et surtout assez contradictoire avec l'objectif à long terme de prévention des complications.

La grande loi du vivant : l'homéostasie

Nous connaissons bien, depuis Claude Bernard, la loi de l'homéostasie biologique et ses boucles de régulation visant à maintenir la stabilité du milieu intérieur entre des bornes servant à définir la normalité. La rupture de cette homéostasie peut déboucher sur la guérison ou sur la mort, ou sur l'allostasie. Celle-ci définit un nouvel équilibre de vie durable, sans être un retour à l'état antérieur. L'angoisse est son moteur, la raison son guide, l'acquisition de compétences son moyen. Tel est l'objectif assigné officiellement à l'éducation thérapeutique. Mais nous connaissons moins l'homéostasie émotionnelle qui vise à éviter la dépression mortifère et l'angoisse paralysante quand les besoins primaires sont assurés. En effet, quand la faim, la soif, l'absence de douleur, le sentiment de sécurité… sont assurés, l'être humain donne la priorité à l'homéostasie émotionnelle à court terme quitte à prendre des risques pour sa santé, et même pour sa vie [START_REF] Damasio | L'Ordre étrange des choses : la vie, les sentiments et la fabrique de la culture[END_REF][START_REF] Jeammet | Quand nos émotions nous rendent fous -Un nouveau regard sur les folies humaines[END_REF]. Prendre le risque de mourir demain, plutôt que de sombrer dans la dépression aujourd'hui ! Pour maintenir son homéostasie émotionnelle face à un traumatisme psychique, chacun met en place des mécanismes de défense psychologique [START_REF] Ionescu | Les mécanismes de défense -Théorie et clinique[END_REF] : sublimation, héroïsation, mais aussi déni, dénégation, c'est-à-dire refus conscient de la maladie ou des contraintes du traitement, minimisation méthode Coué, pensée magique (d'où le succès des médecines dites douces ou parallèles), clivage, hyperactivité, conduites à risque, phobies, addictions, projections, bénéfices secondaires… Les questions qui se posent alors sont les suivantes : ces mécanismes de défense sont-ils transitoires, plastiques, susceptibles d'évoluer ou, au contraire, sont-ils figés, cristallisés ? Ont-ils des conséquences nuisibles pour le patient ou pour son entourage ? Bref, le patient, est-il « malade d'être malade » ? On sait qu'il y a deux fois plus de patients déprimés parmi les patients atteints de maladies chroniques, comme le diabète, que dans la population générale à âge et situation sociale comparables, mais on ne connaît pas la proportion de patients « malades d'être malade ». Il n'y a donc pas un vécu universel partagé de la maladie mais des vécus divers, si ce n'est singuliers.

Comment guérir de cette 2 e maladie ?

Pour guérir de cette 2 e maladie, il faut : 5 nous nous trouvons toujours de bonnes raisons à nos comportements déraisonnables.

(2) Qu'il accepte d'en parler, car comme le dit Albert Camus « parler répare » [START_REF] Camus | L'homme révolté[END_REF], mais Boris Cyrulnik fait justement remarquer « que les mots peuvent aussi faire saigner la mémoire » [START_REF] Cyrulnik | La nuit, j'écrirai des soleils[END_REF]. Pourquoi remuer le couteau dans la plaie ? (3) Qu'il entre dans un processus de remaniement, de réécriture, permettant un double mouvement de distanciation et de réappropriation : « en écrivant, j'ai raccommodé mon moi déchiré » [START_REF] Cyrulnik | La nuit, j'écrirai des soleils[END_REF]. En parler, mais à qui ? À quelqu'un qui peut écouter et donc qui a le temps ou donne le sentiment d'avoir le temps, quelqu'un qui peut non seulement écouter mais comprendre, non seulement comprendre mais ne pas juger, respecter la confidentialité et ne pas profiter de la confiance du patient pour développer son emprise. Un proche ? Oui, mais pas trop proche. Un psychologue ou un psychiatre ? Oui, mais cela suppose une préparation, car le plus souvent le patient n'y en voit pas la nécessité ou s'y refuse. Un soignant ? Oui, mais a-t-il le temps et peut-il comprendre que le patient ne suive pas ses bons conseils et n'observe pas ses prescriptions ? Un autre patient ayant la même maladie ? Oui, s'il a connu les mêmes difficultés ou du moins des difficultés similaires et qu'il a réussi à les surmonter, et s'il est prêt à aider sans pour autant se donner en modèle ou développer une emprise ou se comporter en soignant. Être expert de son propre vécu ne va pas de soi, pour un patient comme pour chacun d'entre nous. Il ne suffit pas pour être expert de son vécu de patient d'avoir acquis des compétences pratiques, transmissibles. Encore faut-il avoir fait un travail de deuil ayant permis la résilience, avoir réussi à intégrer la maladie à son identité narrative, sans lui donner toute la place, avoir analysé le chemin parcouru et pris distance avec les souffrances rencontrées et, finalement, se mieux connaître soi-même en étant devenu plus fort après qu'avant, comme le dit Philippe Barrier [START_REF] Barrier | La blessure et la force. La maladie et la relation de soin à l'épreuve de l'auto-normativité[END_REF].

Le patient « ressource »

Un patient expert de son vécu peut devenir un patient ressource pour d'autres patients, mais pas pour tous les patients. Cela suppose a priori qu'il ait la même maladie, mais surtout qu'il ait connu le même vécu et qu'il ait réussi à le dépasser. On dit qu'il doit pratiquer le « bilinguisme », en traduisant le jargon médical en langage courant et en se faisant l'interprète des interrogations que les patients n'osent pas formuler. Terrible accusation à l'encontre des soignants, prétendant par ailleurs pratiquer la « décision médicale partagée ». Il vaudrait mieux apprendre aux soignants à parler comme leurs patients ! La fonction du « patient ressource » n'est pas de « traduire », mais de permettre l'identification réciproque, ce que ne permet pas le statut de soignant. Le soignant ne doit d'ailleurs pas rechercher l'identification en arguant de son expérience personnelle de la maladie sur le thème du « moi aussi… ». Le patient demande en effet au professionnel compétence et empathie, pas un partage de vécus. Cela suppose une claire distinction de la place de chacun, même si une relation ancienne permet l'empathie réciproque : « vous n'avez pas l'air bien aujourd'hui docteur ! vous semblez fatigué… ». Le « patient ressource » doit donc être prêt à aider personnellement des patients en difficultés dans et hors l'hôpital, en établissant une relation équilibrée dans la durée. Jouant, en quelque sorte, le rôle de « tuteur de résilience », il doit être intégré à l'équipe de soins et bénéficier d'une « supervision ». Il doit être couvert par contrat avec l'institution, mais il est nécessairement bénévole sans contrat de travail, donnant de son temps autant qu'il le veut et autant qu'il le peut. Il doit pouvoir mettre un terme à son engagement, de même que l'équipe soignante doit pouvoir mettre fin à sa 6 assistante sociale, ni aide psychologue. C'est donner de soi. Autre chose est d'apporter une aide dans diverses activités d'éducation thérapeutique en fonction de compétences personnelles (activité physique, art-thérapie…), sans pour autant se substituer à des professionnels.

Les autres habits du « patient expert »

Les activités des « patients experts » ne se résument pas à l'aide à la résilience des patients. Ils peuvent assurer d'autres activités justifiant un dédommagement financier ou une rémunération.

(1) Le patient expert peut être un militant associatif, aidant, dans le cadre de l'association, des patients novices ou en difficultés, ou participant à diverses activités d'accompagnement ou à des actions communication grand public, ou encore s'investissant dans des comités de recherche, le plus souvent mixte associant patients et professionnels… [START_REF] Goupy | La médecine narrative : une révolution pédagogique ?[END_REF] Le patient expert peut participer à l'enseignement universitaire ou postuniversitaire, en particulier sur la relation soignant/soigné. Il doit alors être intégré à l'équipe enseignante sous la responsabilité de l'institution responsable de l'enseignement.

(3) Le patient expert peut être représentant des usagers au sein des différents établissements de soins (hôpitaux, centres de santé…) et des différentes instances du système de soins (Haute Autorité de santé [HAS], Agence régionale de santé [ARS], Caisse nationale de l'Assurance Maladie [Cnam], Agence nationale de sécurité du médicament et des produits de santé [ansm], Universités...), encore faut-il qu'il soit mandaté par une association de patients, qu'il n'ait pas de conflits d'intérêts, et qu'il ait acquis une compétence en Santé publique. (4) Il peut jouer le rôle de médiateur socioculturel au service de populations de migrants ayant des difficultés d'intégration et de recours au système de soins pour des raisons multiples, sociales, territoriales et culturelles. Toutefois, le plus souvent, ces médiatrices et médiateurs ne sont pas eux-mêmes patients.

Conclusion

Dans la tradition hippocratique moderne, le patient ressource est un tuteur de résilience bénévole intégré à l'équipe de soins, tandis que le médecin ne soigne ni une maladie ni un individu, mais une personne. Dans la « nov'langue », le patient expert est « un consommateur éclairé » devenu « un producteur de santé » pouvant vendre ses services. Dans le « nouveau monde » post-moderne, le patient expert et le médecin seraient des « prestataires de service » comme les autres, futurs autoentrepreneurs ubérisables.

Les points essentiels

 Le concept de « patient expert » recouvre différentes activités allant de la représentation des usagers dans les instances du système de santé à l'accompagnement médicosocial, en passant par la participation à la formation universitaire et post-universitaire, à la recherche, à l'information et à la promotion de la santé ou à des ateliers d'éducation thérapeutique. Pour cela, il doit avoir acquis en plus de son expérience, une compétence spécifique reconnue, et peut recevoir une rémunération ou un dédommagement financier.  Le patient expert peut trouver une place particulière au sein de l'équipe de soin pour aider les patients refusant leur maladie ou les contraintes du traitement,