Keywords: force d'un graphe, matroïde, partition, connectivité, détection de communauté, graphe petit-monde

Nouveaux algorithmes pour le calcul de la force des graphes Résumé : Nous nous penchons sur le problème du calcul de la force d'un graphe. Nous décrivons la premième formulation polyhédrale pour le calcul de la force pondérée d'un graphe de taille polynomiale en la taille du problème, à savoir O(mn), où n est le nombre de sommets et m le nombre d'arètes du graphe. Nous décrivons aussi un FPTAS surprenamment simple qui donne la force d'un graphe à un facteur 1 + ǫ près en temps O(m log 2 (n) log( m n )/ǫ 2 ) et en espace O(m), dépassant d'un facteur d'environ min(n √ m, n 5/3 ) le meilleur algortihme connu de Trubin associé à l'algorithme postérieur de Goldberg and Rao pour le flot maximum et d'environ σ(G) le FPTAS de Plotkin, Shmoys, et Tardos.

Introduction

In this paper we investigate the strength of a graph. The notion was introduced by Cunningham to evaluate the resistance of a network under attack [START_REF] Cunningham | Optimal attack and reinforcement of a network[END_REF]. Moreover, it has a strong interest in the field of connectivity and community detection (small world) [START_REF] Gusfield | Connectivity and edge-disjoint spanning trees[END_REF][START_REF] Ou | Method for data clustering and classification by a graph theory model-network partition into high density subgraphs[END_REF]. We are given a graph G = (V, E), let Π be the set of all partitions over V , and for P ∈ Π, δP is the set of edges of G crossing between parts of P (also called the cocycle of P ), then the strength is given by min

P ∈Π |δP | |P | -1 . (1)
A weighted notion of strength can also be defined, if w(e) is the positive weight assigned to edge e, and w(X) is the sum of all edges X ⊆ E, as: min

P ∈Π w(δP ) |P | -1 . ( 2
)
If c is the minimum cut of G, note that the strength will be between c/2 and c. An important result on strength of graphs was found by Tutte and Nash-Williams [START_REF] Tutte | On the problem of decomposing a graph into n connected factors[END_REF][START_REF] Nash-Williams | Edge-disjoint spanning trees of finite graphs[END_REF]: Theorem 1 ( [START_REF] Tutte | On the problem of decomposing a graph into n connected factors[END_REF][START_REF] Nash-Williams | Edge-disjoint spanning trees of finite graphs[END_REF]) G contains k edge-disjoint spanning trees if and only if the strength of G is larger than or equal to k.

Most of the previous work that was found to evaluate the strength of a graph depends on the complexity M F (n, m) of finding a maximum st flow in a digraph with n vertices and m arcs. The best algorithm we know for that has a complexity of O(min( √ m, n 2/3 )m log(n 2 /m + 2)) [START_REF] Goldberg | Beyond the flow decomposition barrier[END_REF].

Given a max-flow algorithm, Cunningham gave the first algorithm for the strength, with a complexity of O(nm M F (n, n 2 )) [START_REF] Cunningham | Optimal attack and reinforcement of a network[END_REF]. Later, Gabow and Westermann gave an algorithm to computer the integer value of the strength in O min m m n (m + n log n) log m n , nm log m n [START_REF] Gabow | Forests, frames and games: algorithms for matroid sums and applications[END_REF]. Gusfield obtained a O(n 3 m) algorithm [START_REF] Gusfield | Computing the strength of a graph[END_REF]. The same year, a FPTAS for that problem is obtained in time O(m log 2 (n)σ(G)/ε 2 ) by Plotkin, Shmoys and Tardos [START_REF] Plotkin | Fast approximation algorithms for fractional packing and covering problems[END_REF]. The complexity of computing the strength of a graph was also found in O(n 2 M F (n, n 2 )) by Barahona [START_REF] Barahona | Separating from the dominant of the spanning tree polytope[END_REF]. Finally, Trubin, and after Cheng and Cunningham gave an O(n M F (n, m)) algorithm [START_REF] Trubin | ÈÖÓÕÒÓ×Ø Ö ÙÔ ÓÚ Ö Ú Ú Ú ØÚÐ Ò . à ÖÒ Ø Ë ×Ø ÑÒÝ Ò Ð Þ[END_REF][START_REF] Cheng | A faster algorithm for computing the strength of a network[END_REF]. For a general perspective on that topic, we point the reader to [15, Chapter 51] and [START_REF] Skoda | Force d'un graphe, multicoupes et fonctions sous-modulaires: aspects structurels et algorithmiques[END_REF].

The article is organized as follows. We recall in Section 2 the basics of the theory of strength of graphs, starting from an alternative definition and showing equivalence to [START_REF] Baiou | A linear programming approach to increasing the weight of all minimum spanning trees[END_REF]. We describe in Section 3 our approximation algorithm and give a proof of correctness. In Section 4 we show an original polyhedral approach of the problem, which is, to our knowledge, the first to be in polynomial size. Note that Sections 3 and 4 are completely independent and therefore Section 3 can be skipped to understand Section 4.

Some basic results

We start from an alternative definition for the strength that was used in [START_REF] Baiou | A linear programming approach to increasing the weight of all minimum spanning trees[END_REF][START_REF] Schrijver | Combinatorial optimization[END_REF][START_REF] Skoda | Force d'un graphe, multicoupes et fonctions sous-modulaires: aspects structurels et algorithmiques[END_REF], and prove that it is equivalent respectively to (1) and ( 2). Let T be the set of all spanning trees of the graph G.

Definition 1 σ(G) := max T ∈T λ T : ∀T ∈ T , λ T ≥ 0, ∀e ∈ E, T∋e λ T ≤ 1 (3)
and if there are weights on the edges :

σ w (G) := max T ∈T λ T : ∀T ∈ T , λ T ≥ 0, ∀e ∈ E, T∋e λ T ≤ w(e) (4)
By linear duality we can reformulate definition 1 as follows:

Fact 1 σ(G) = min e∈E y e : ∀e ∈ E, y e ≥ 0, ∀T ∈ T , e∈T y e ≥ 1 , (5)
and

σ w (G) = min e∈E w(e)y e : ∀e ∈ E, y e ≥ 0, ∀T ∈ T , e∈T y e ≥ 1 . (6)
Note that this simple fact can be used in practice to compute the strength of a graph. Computing a minimum spanning tree using the algorithm of Kruskal [START_REF]On the shortest spanning subtree of a graph and the travelling salesman problem[END_REF] takes O(m log m) steps, and since the associated linear program is of size O(m) × O(m), we can use the claimed result of Fomin [START_REF] Fomin | AEÓÚÝ ÔÖ Ð ÒÒÝ Ð ÓÖ ØÑ Ð Þ Õ ÔÓÐÓ Ø Ð Ð ÔÖÓ Ö ÑÑ ÖÓÚ Ò[END_REF] to obtain a complexity of O(m 2 log 2 (m)) per iteration.

Properties of the optimal solution

Fact 2 Let y * be an optimal solution in [START_REF] Gabow | Forests, frames and games: algorithms for matroid sums and applications[END_REF]. For each e with y e nonzero, there is a tree T i such that e ∈ T i and f ∈T y f = 1.

Proof. Suppose it is not the case. Then for some ǫ > 0, for each T i with e ∈ T i we have f ∈T y * f ≥ 1 + ǫ. Then replacing y * e by max(0, y eǫ) will improve the optimal solution. Fact 3 Let y * be an optimal solution in [START_REF] Gabow | Forests, frames and games: algorithms for matroid sums and applications[END_REF]. Removing the set {e ∈ E : y * e > 0} disconnects G.

Proof. Suppose on the contrary that the subgraph with the edges e such that y * e = 0 is connected. Then there is a spanning tree of weight 0, contradicting the definition of y * . Fact 4 Let y * be an optimal solution in [START_REF] Gabow | Forests, frames and games: algorithms for matroid sums and applications[END_REF]. Let P = {C 1 , . . . , C k } be the connected components obtained by removing the e such that y * e > 0. Then

Then construct a set W = T ∪{e : y * e = 0}. Since T is a tree on G, W connects all the vertices of G. We want to construct a tree T ′ of W with minimum e∈T ′ y * e . Since δP = {e : y * e > 0}, and

W = T ∪ δP , we need only |P | -1 edges of δP in T ′ to connect G. So |T ′ ∩ δP | = |P | -1 and |(T -T ′ ) ∩ δP | ≥ |T ∩ δP | -|P | + 1. As a consequence e∈T y * e = e∈T ′ y * e + e∈T -T ′ y * e ≥ 1 + y min (|T ∩ δP | -|P | + 1),
and replacing in (8), we have e∈T y ′ e ≥ 1. This is true for all tree T , therefore y ′ satisfies the optimization constraints of (6). Since y * is an optimal solution, So we obtain e∈E w(e)y * e ≥ w(δP ) |P |-1 , which completes with (7) the fact.

Fact 5

We have that

σ w (G) = min Q∈π w(δ(Q)) |Q| -1 .
With this fact we can say that the defined σ w (G) corresponds to the weighted strength of (2). Simply setting w(e) = 1 shows that σ(G) is the strength of (1). Also facts 2, 3 and 4 hold when y * is the optimal solution of (5). Proof. Fact 4 shows that σ w (G) ≥ min Q∈π w(δ(Q))

|Q|-1 . The reverse is obtained by noticing that, for Q ∈ π, we can define z e by z e = 1/(|Q| -1) if e ∈ δQ, and z e = 0 otherwise. And we have:

e∈E w(e)z e = w(δQ) |Q| -1 ≥ σ w (G).

Antitonicity of the strength

We show here that the strength of a graph is always smaller than the strength of its induced subgraphs. We denote G(S) the subgraph induced by the vertices S ⊆ V . Note that we have the following important fact:

Fact 6 Let P = {S 1 , . . . , S p } be a partition of G that achieves the strength of G, that is σ w (G) = w(δ{S 1 , . . . , S p }) p -1
then, for all i ∈ {1, . . . , p}, we denote G(S i ) the restriction of G to S i , and we have:

σ w (G(S i )) ≥ σ w (G).
Proof. Indeed suppose on the contrary that there is one partition S 1 i , . . . , S k i of one S i with

σ w (G) > σ w (G(S i )) = w(δ{S 1 i , . . . , S k i }) k -1 .
Then consider the partition S 1 , . . . , S i-1 , S 1 i , . . . , S k i , S i+1 , . . . , S p of G. We have

w(δ{S 1 , . . . , S i-1 , S 1 i , . . . , S k i , S i+1 , . . . , S p }) k + p -2 = (p -1)σ w (G) + (k -1)σ(G w (S i )) p + k -2 < σ w (G),
which is absurd.

A fast approximation

We give in this section a fast algorithm in polynomial time to approximate the strength of a graph. This is inspired from the pre-push flow methods as in [START_REF] Young | Randomized rounding without solving the linear program[END_REF].

Note that similar method are applied by Plotkin, Shmoys and Tardos [START_REF] Plotkin | Fast approximation algorithms for fractional packing and covering problems[END_REF] but the particular techniques that we use here allow to remove the σ(G) factor of this previous work. We allow multiple edges in the following.

INRIA

Theorem 2 Given a connected graph G and a positive real ε ≤ 1/2, there exists an algorithm of computational time O(m log(n) 2 log( m n )/ε 2 ) and maximum memory space O(m) that returns a set of trees T 1 , . . . , T p of G, associated to real positive numbers λ 1 , . . . , λ p with ∀e ∈ E i∈{1,...,p}:Ti∋e

λ i ≤ 1 (9)
and i∈{1,...,p} λ i ≥ 1 1+ε σ(G).

We introduce the following simple definition coming out of matroid theory.

Definition 2 A subset F of E is called independent if it contains no cycle.
According the this definition, the independent subsets of E are the forests and trees are forests of size n -1. Then our algorithm, denoted in the following by A is as follows:

Step 1:

Set δ := (n(1 + ε)) -⌈ 3 ε ⌉ (1 + ε), k := ⌊ m⌈1+log 1+ε ( 1 δ )⌉ n-1 ⌋, T j := ∅, t j := 0 for j ∈ {1, . . . , k + 1}.
Step 2:

For i := 0 to ⌈log 1+ε ( 1 δ )⌉ do For each edge e ∈ E do begin Find the minimum j ∈ {1, . . . , k + 1} such that e / ∈ T j and T j ∪ {e} is independent. If j ≤ k Then Set t j := t j + 1 Set z(j, t j ) := i Set T j := T j ∪ {e} end

Step 3: Find the maximum r ∈ {1, . . . , k} such that t r = n -1.

Step 4: Find the minimum p ∈ {1, . . . , r} such that l∈{1,...,n-1}

δ(1 + ε) z(p,l) ≥ 1.
Step 5: Let ∀j ∈ {1, . . . , p} λ j := max

e∈E |{g ∈ {1, . . . , p} : e ∈ T g }| -1
.

Definition 3 We say that the independent set A ⊆ E dominates the independent set B ⊆ E if there is no edge in e in B such that e / ∈ A and A ∪ {e} is independent.

Lemma 1 The algorithm can be run in O(m) space size without increasing the computational time by more than a (small) constant factor.

Proof. This can be seen by repeating steps 2 to 3 restricting k over succesive intervals of size of ⌊ m n ⌋. When an edge cannot be inserted into the current interval, we store the index i in step 2 when it occurs and do not introduce it anymore in step 2 until next interval for k comes. We store that in a list of indexes i when such hits occurs, each i being associated by the edges in question. If steps 3 and 4 succeed to find respectively a proper maximum r and p, then we stop. Otherwise, we resume the computation by considering next interval for k. We then start resuming by the lowest index i for an edge where the computation was stopped, and only introduced edges with such i that have not been used before.

Notice that in each such phase, at least m n (n -1) edges are required to build the tree (i.e. we perform at least O(m) actual steps of the described algorithm) and the overhead of computation is at most O(m) (constructing the list of passive edges and reintroducing them as active in next phase).

Lemma 2 Suppose that A and B are independent sets, and A dominates B. The following assumptions are then true: (i) If there is a path in B between vertices u and v, there is also a path in A between u and v.

(ii) If for e ∈ E -B, B ∪ {e} is not independent then either e ∈ A or A ∪ {e} is not independent.

(iii) |A| ≥ |B|.

Proof. We show (i) by induction on the length l of the path in B between u and v. If l = 1, {{u, v}} ∈ B, then either e ∈ A or A ∪ {{u, v}} contains a cycle, and therefore there exists a path in A between u and v. Suppose (i) is true for some l, and there is a path between u and v in B of length l + 1. Then there is some w with a path in B between u and w of length l, and {w, v} ∈ B.

Then u is connected to w by a path in A, and w is connected to v by a path in A, which proves the induction. Now, B ∪ {{u, v}} is not independent if and only if there is a path in B between u and v, which proves (ii). (iii) comes by induction on |A| by noticing that the number of connected components induced by A is n -|A|.

Lemma 3 At each time in algorithm A, for i < j, T i dominates T j , therefore

t i = |T i | ≥ |T j | = t j .
Proof. An edge e can be added to T j only if e ∈ T i or T i ∪ {e} is not independent.

Lemma 4 Algorithm A runs in O(m log(n) 2 log( m n )/ε 2 ) time.
Proof.

Step 2: First note that log 1+ε ( 1 δ ) = O(log(n)/ε 2 ). So there is O(m log(n)/ε 2 ) iterations in step 2. By lemma 3 a simple dichotomy is enough to find j, INRIA therefore using Kruskal algorithm [15, pp. 98,99,858], required operations for given i and e are up to a constant less than log(n) log(k). Also using lemma 1 replacing k by k 0 = ⌊ m n ⌋ in enough. So an edge insertion is done in O(log(n) log( m n )) .

Step 3: For a given r, the value t r is the number of edges in tree T r . We have t r = n -1 if and only if T r is a spanning tree. Since a spanning tree is an independent subset of E that dominates all the other independent sets, we can also find T r by a simple dichotomy. Note also that since n -1 edges are necessary to build a spanning tree, and step 2 introduces in all m⌈log 1+ε ( 1 δ )⌉ edges, k is indeed the maximum possible number of spanning trees.

Step 4: During each operation in step 2, t j is decreasing j (see lemma 3).

Since i is increasing in step 2, for l ∈ {1, . . . , n -1} the quantity z(j, l) is increasing with j. Hence the value

v(j) = l∈{1,...,n-1} δ(1 + ε) z(j,l) ,
is also increasing with j. Moreover, in the iteration of step 2 where i = ⌈log 1+ε ( 1 δ )⌉, all the edges of E are added and therefore at most one tree is completed. This tree T j receives the weight δ(1 + ε) i which is more than 1, and verifies j ≤ r. Therefore p can be found by dichotomy in O(n log(k 0 )) = O(n log( m n )) computational time.

Lemma 5 For an edge e and an integer i ∈ {0, . . . , ⌈log 1+ε ( 1 δ )⌉} by β(e, i) the index j of the tree T j to which it is added in step 2. Consider ζ j (e) := δ(1 + ε) y where y = min i ∈ {0, . . . , ⌈log 1+ε ( 1 δ )⌉} : β(e, i) ≥ j .

Then for j ∈ {1, . . . , p} T j is a tree of minimum weight on G with weights ζ j .

Proof. Note that ζ j is well defined on each e because j ≤ p. Consider, from the point of view of T j , for some j, all the edges that would have been integrated to T j if e / ∈ T j or T j ∪ {e} would have been independent. Those are the edges such that at the begining of an iteration i on step 2, there is no j ′ < j such that e / ∈ T j ′ and T j ′ ∪ {e} is independent, i.e. those with β(e, i) ≥ j. Therefore ζ j defines an appropriate weight. Conclude saying that T j is built with the edges considered in increasing weight, as in the Kruskal algorithm.

α(ζ s+1 ) ≤ δn + ε σ(G) j∈{1,...,s} α(ζ j ). ( 10
)
We now show by induction on κ that

δn + ε σ(G) j∈{1,...,κ} α(ζ j ) ≤ δne κε σ(G) . (11)
It is clear for κ = 0. Note that for κ > 0, using the induction hypothesis and (10), we have

δn + ε σ(G) j∈{1,...,κ} α(ζ j ) = δn + ε σ(G) j∈{1,...,κ-1} α(ζ j ) + ε σ(G) α(ζ κ ) ≤ 1 + ε σ(G) δne (κ-1)ε σ(G)
.

And finaly, equation [START_REF] Magnanti | Handbooks in OR & MS, volume 7, chapter Optimal trees[END_REF] comes from the fact that 1 + x < e x for x > 0.

Putting together [START_REF]On the shortest spanning subtree of a graph and the travelling salesman problem[END_REF] and [START_REF] Magnanti | Handbooks in OR & MS, volume 7, chapter Optimal trees[END_REF] on the particular case of p (step 4), we have:

δne pε σ(G) ≥ α(ζ p ) ≥ 1,
which gives p ≥ σ(G) ε ln( 1 nδ ). Then we can bound the algorithm as follows:

j∈{1,...,p}

λ j = p max e∈E |{j ∈ {1, . . . , p} : e ∈ T j }| ≥ σ(G) ε ln( 1 nδ ) log 1+ε ( 1+ε δ ) = σ(G) ln(1+ε)(⌈ 3 ε ⌉-1) ln(n(1+ε)) ε⌈ 3 ε ⌉ ln(n(1+ε)) = σ(G) ln(1+ε)(1-1 ⌈ 3 ε ⌉ ) ε (see lemma 6) ≥ σ(G)(1-ε 3 ) ln(1+ε) ε ≥ σ(G) 1+ε since for ε < 1 2 ln(1 + ε) ≥ ε (1+ε)(1-ε 3 )
and we conclude the proof by noticing that ( 9) is guaranteed by step 5.

INRIA

A polyhedral approach

We consider the oriented symmetric graph of G, that is, let E be the set of arcs derived from E, that is an edge of E gives two arcs in E. We also denote e the non-oriented version of e. Let r be an arbitrary vertex of V .

Theorem 3 The value of σ w (G) is given by the solution of the following linear problem in the real variables y e , e ∈ E, γ k v , v, k ∈ V , µ k e , k ∈ V, e ∈ E, and ϕ:

Minimize e∈E w(e)y e -γ k v + γ k w + µ k -→ vw ≥ 0, ∀ -→ vw ∈ E, ∀k ∈ V -{r} ϕ - k∈V -{r} µ k e + y e ≥ 0 ∀ e ∈ E - k∈V -{r} γ k r + k∈V -{r} γ k k + (n -1)ϕ ≤ -1 µ k e ≥ 0 ∀ e ∈ E, ∀k ∈ V -{r} ϕ ≥ 0. ( 12
)
Moreover the minimum value verifies

RR n 6592

According to [11, pp.534-535], the set conv(S) can be described as follows. For e ∈ E and k ∈ V we introduce the positive variable f k e of flow of multicommodities.

e∈δ -(r)

f k e - e∈δ + (r) f k e = -1 ∀k = r e∈δ -(v) f k e - e∈δ + (v) f k e = 0 ∀v = r, v = k, ∀k = r e∈δ -(k) f k e - e∈δ + (k) f k e = 1 ∀k = r e∈ E z e = n -1 f k e ≤ z e ∀k = r ∀ e ∈ E, f k e ≥ 0 ∀k, ∀ e ∈ E. (16)
We introduce matrix A and vector b to write problem [START_REF] Skoda | Force d'un graphe, multicoupes et fonctions sous-modulaires: aspects structurels et algorithmiques[END_REF] as

A • f z ≤ b.
Let us fix for a while the values of y e , e ∈ E, and give some ε > 0. What are the conditions for which problem

   A • f z ≤ b
z e y e ≤ 1ε has no solutions in z and f ? Farkas lemma answers that there exists some vector x 0 ≥ 0 and ψ ≥ 0 with x t 0 • A + ψy = 0 and x t 0 • b + (1ε)ψ < 0. Suppose we have found such a (x 0 , ψ) with ψ = 0. Then x 0 ≥ 0 verifies x t 0 • A = 0 and x t 0 • b < 0, which means, by Farkas lemma again, there is no solution in (f, z) for A • f z ≤ b. This implies that the tree polytope of G is empty, which is absurd. So we have necessarily ψ > 0. By division of x 0 by ψ, we see that some x 1 verifies x t 1 • A + y = 0 and x t 1 • b + (1ε) < 0. If this is true for all ε > 0, since the polyhedron {x ≥ 0 : x t • A + y = 0} is a closed set, then there also exists a x 2 ≥ 0 with x t 2 • A + y = 0 and x t 2 • b + 1 ≤ 0. We have then the following equivalent propositions: (v) For all ε > 0, there exists a x ≥ 0 such that

x t • A + y = 0 x t • b + (1 -ε) < 0,
(vi) There exists a x ≥ 0 such that

x t • A + y = 0 x t • b + 1 ≤ 0.
Reformulating the variable x in µ, γ, and ϕ gives the linear program of theorem 3. Moreover the existence of such a x that verifies x t • A + y = 0 and x t • b + 1 ≥ 0, gives that, for any tree T of G, we have e∈T y e ≥ 1.

  w(δP ) |P |-1 = e∈E w(e)y * e . INRIA Proof. Define z e by z e = 1/(|P | -1) if e ∈ δP , and z e = 0 otherwise. Hence ∀T ∈ T e∈T z e ≥ 1. By optimality of y * , e∈E w(e)y * e ≤ e∈E w(e)z e , Let y min = min e:y * e >0 y * e . Let T be a tree such that e∈T y * e = 1. Since T connects all the components of P , |δP ∩ T | ≥ |P | -1. So we have 1 = e∈T y * e ≥ (|P | -1)y min . Therefore y min (|P | -1) ≤ 1. Let us distinguish two cases. Suppose that y min (|P | -1) = 1, then e∈E w(e)y * e ≥ y min w(δP ) = w(δP ) |P | -1 , which completes with (7) the fact. Suppose that, on the reverse, y min (|P | -1) < 1, then set for e ∈ E y ′ e = y * ey min χ(y * e > 0) 1 -(|P | -1)y min where χ(y * e > 0) equals 1 if y * e > 0, and 0 otherwise. Then, for a tree T on G, we have e∈T y ′ e = e∈T y * ey min |δP ∩ T | 1 -(|P | -1)y min .

  y ′ e = e∈E w(e)y * ey min w(δP ) 1 -(|P | -1)y min .

Lemma 6

 6 We have max e∈E |{j ∈ {1, . . . , p} : e ∈ T j }| ≤ log 1+ε 1 + ε δ . Proof. Step 2 can introduce an edge e only 1 + log 1+ε ( 1 δ ) times. Proof. [Theorem 2]. For each j ∈ {1, . . . , p -1} we have e∈E ζ j+1 (e) = e∈E ζ j (e) + ε e∈Tj ζ j (e), so we can conclude by lemma 5 that for s ∈ {1, . . . , p -1}, e∈E ζ s+1 (e)ζ 1 (e) = ε j∈{1,...,s} α(ζ j ), where α(w) = min{w(T ) : T ∈ T }. Note that, by fact 1, σ(G) = min e∈E ζ(e) α(ζ) : ζ ∈ IR E + . Therefore σ(G) ≤ e∈E ζs+1(e)-ζ1(e) α(ζs+1-ζ1) and we have (α(ζ s+1 )-δn)σ(G) ≤ α(ζ s+1ζ 1 )σ(G) ≤ e∈E ζ s+1 (e)ζ 1 (e). It gives:

e∈T y e ≥ 1

 1 for any spanning tree T of G.Proof. We can reformulate fact 1, writing σ w (G) = min( e∈E w(e)y e : ∀e ∈ E, y e ≥ 0, ∀T ∈ T , e∈E χ {e∈T} y e ≥ 1),[START_REF] Ou | Method for data clustering and classification by a graph theory model-network partition into high density subgraphs[END_REF] where χ {e∈T } is equal to 1 if e ∈ T , and 0 otherwise.Consider the set of IR E given by:S = {z ∈ IR E : ∃T ∈ T ∀e ∈ E z e = χ {e∈T } }.Now we can say:σ w (G) = mine∈E w(e)y e : ∀e ∈ E, y e ≥ 0, ∀z ∈ S, e∈E z e y e ≥ 1 , (14) or σ w (G) = min e∈E w(e)y e : ∀e ∈ E, y e ≥ 0, min z∈conv(S) e∈E z e y e ≥ 1 .

y e z e ≥ 1

 1 ∀z ∈ conv(S),(iii) e∈E y e z e ≥ 1 ∀(z, f ) such that A • f z ≤ b, INRIA(iv) For all ε > 0, there are no solution for e y e ≤ 1ε,

RR n 6592

Acknowledgements. I would like to thank A. Laugier, J.-C. Bermond, J. Fonlupt and C. Caspar for many helpful remarks. This paper was done in the scope of the Orange Labs/INRIA/CNRS/I3S contract Corso2. This paper is also an output of discussions done in the European COST 293 project (GRAAL) and the AEOLUS project.


V N Grebenev
email: vngrebenev@gmail.com

S B Medvedev

S V Nazarenko
email: sergey.nazarenko@unice.fr

B V Semisalov

Steady states in dual-cascade wave turbulence

Keywords: numbers: 47.27.Eq, 47.27.ed, 02.60Lj

We study stationary solutions in the differential kinetic equation, which was introduced in [1] for description of a local dual cascade wave turbulence. We give a full classification of single-cascade states in which there is a finite flux of only one conserved quantity. Analysis of the steady-state spectrum is based on a phase-space analysis of orbits of the underlying dynamical system. The orbits of the dynamical system demonstrate the blow-up behaviour which corresponds to a "sharp front" where the spectrum vanishes at a finite wave number. The roles of the KZ and thermodynamic scaling as intermediate asymptotic, as well as of singular solutions, are discussed.

Introduction

Wave turbulence kinetic equation and the differential approximation model

Weak wave turbulence, a broadband system of random weakly interacting waves, is usually modeled by a kinetic equation for the spectral wave action density, n k ≡ n(k, t), which describes how the excitations in the system are distributed among different wave vectors k at time t. The specific form of the wave kinetic equation depends on the linear and nonlinear properties of the medium, in particular the dispersion relation for the wave frequency, the leading-order of the resonant wave-wave interaction and the scaling properties of the nonlinear interaction term in PDE describing the medium dynamics. For example, a system dominated by four-wave (2 → 2) interactions is described by the following kinetic equation [START_REF] Dyachenko | Optical Turbulence: Weak Turbulence[END_REF][START_REF] Zakharov | Kolmogorov Spectra of Turbulence I[END_REF][START_REF] Nazarenko | Wave turbulence[END_REF],

∂n k ∂t = |T k,k 1 ,k 2 ,k 3 | 2 n k n k 1 n k 2 n k 3 1 n k + 1 n k 1 - 1 n k 2 - 1 n k 3 × (1)
δ(k + k 1 -k 2 -k 3 )δ(ω k + ω k 1 -ω k 2 -ω k 3 ) dk 1 dk 2 dk 3 ,
where T k,k 1 ,k 2 ,k 3 is an interaction coefficient which depends on a particular wave system. Assuming that T k,k 1 ,k 2 ,k 3 is strongly localised at the values with

k ∼ k 1 ∼ k 2 ∼ k 3 , equation (1)
can be approximated by a differential equation

ω d α -1 ∂n ω ∂t = I ∂ 2 ∂ω 2 ω s n 4 ω ∂ 2 ∂ω 2 1 n ω , (2)
where

n ω = n(k(ω), t), (3)
s = (2γ + 3d)/α + 2 (4)
d is the physical space dimension and I is a dimensional constant which depends on the particular physical system. Here γ is the degree of homogeneity of the interaction coefficient defined via T λk,λk 1 ,λk 2 ,λk 3 = λ γ T k,k 1 ,k 2 ,k 3 where λ is a constant.

Physical applications

Let us briefly list several important physical examples of four-wave systems.

Wave turbulence in Bose-Einstein condensates and in Nonlinear Optics [START_REF] Dyachenko | Optical Turbulence: Weak Turbulence[END_REF]. In this case the underlying PDE is the Nonlinear Schrödinger (NLS, a.k.a Gross-Pitaevskii, GP) equation, and the resulting parameters are: α = 2, γ = 0, d = 2 or 3. Respectively, s = 5 for 2D and s = 13/2 for 3D systems.

Wave turbulence on surface of deep water. This is a classical and most celebrated example of wave turbulence [START_REF] Zakharov | Kolmogorov Spectra of Turbulence I[END_REF][START_REF] Nazarenko | Wave turbulence[END_REF][START_REF] Nazarenko | Wave Turbulence on Water Surface Annual Review of Condensed Matter Physics[END_REF]. In this case α = 1/2, γ = 3, d = 2 so that s = 26.

Wave turbulence in self-gravitating dark matter. Frequently used model for selfgravitating dark matter is based on the so-called Schrödinger-Newton equations (SNE) [START_REF] Lee | In-gyu Koh 1996 Galactic halos as boson stars[END_REF]. Wave turbulence theory for such a system, including description within the differential approximation model, was recently developed in [START_REF] Skipp | Wave Turbulence in Self-Gravitating Bose Gases[END_REF]. In this case the parameters are: α = 2, γ = -2, d = 2 or 3. Respectively, s = 3 for 2D and s = 9/2 for 3D systems.

Turbulence of gravitational waves in vacuum. Wave turbulence theory for such a system was recently developed from the Einstein vacuum field equations in [START_REF] Galtier | Turbulence of Weak Gravitational Waves in the Early Universe[END_REF], and the differential model was further suggested in [START_REF] Galtier | Nonlinear diffusion models for gravitational wave turbulence[END_REF]. In this case we have α = 1, γ = 0, so for 2D and 3D we have s = 8 and s = 11 respectively.

Turbulence of Langmuir plasma waves and spin waves. In this case we have α = 2, γ = 2, d = 3. Respectively, s = 17/2.

General properties of the differential approximation model

Differential approximation model [START_REF] Zakharov | Kolmogorov Spectra of Turbulence I[END_REF], is a rather drastic and not fully justified as a quantitative description for most applications of weak turbulence. Nevertheless retains many qualitative properties of the full kinetic equation [START_REF] Dyachenko | Optical Turbulence: Weak Turbulence[END_REF]. Differential kinetic equation ( 2) has the conservation laws admitted within its original integro-differential form, namely the conservation of the total energy,

E = ω d α n ω dω, (5)
and the total number of particles,

N = ω d α -1 n ω dω. (6)
It also has the same the scaling and homogeneity as the original kinetic equation. Consequently, the pure scaling solutions of the kinetic equation, the equilibrium thermodynamic spectra and the non-equilibrium Kolmogorov-Zakharov (KZ) cascade spectra, are also solutions of the differential kinetic equation [START_REF] Zakharov | Kolmogorov Spectra of Turbulence I[END_REF]. These solutions are of the form n(ω) = c • ω -x where x takes one of the following values:

x = 0 (thermo N-equipartition), x = 1 (thermo E-equipartition), (7)
x = 2γ + 3d 3α (KZ inverse N-cascade), x = 2γ + 3d -α 3α (KZ direct E-cascade). ( 8
) Quantity Q = - ∂ ∂ω K (9)
has the meaning of the local flux of particles through ω. We also define the local flux of energy [START_REF] Dyachenko | Optical Turbulence: Weak Turbulence[END_REF][START_REF] Connaughton | Non-stationary Spectra of Local Wave Turbulence[END_REF]:

P = K -ω ∂K ∂ω , (10)
where

K = I ω s n 4 ∂ 2 ∂ω 2 1 n . (11)

Outline

The differential kinetic equation ( 2) was simulated numerically in [START_REF] Connaughton | Non-stationary Spectra of Local Wave Turbulence[END_REF] to find evolving spectra arising from decay of an initial data concentrated in a finite frequency range. It was found that the qualitative behaviour previously observed for a wave kinetic equation by Galtier et al in [START_REF] Galtier | A weak turbulence theory for incompressible MHD[END_REF] is also present in this model in the finite capacity case. In particular, in a direct cascade setup, these simulations show that the propagating front is sharp in the sense that n(ω) ≡ 0 for ω > ω * (t) for t < t * < ∞. The front position ω * (t), as well as the evolution of the spectrum, were found numerically to possess properties of self-similarity of the second kind, so that ω * (t) → ∞ as t → t * . In our future work, we will return to the study of the evolving self-similar solutions of the model ( 2). In the present paper, we will concentrate on a detailed study and classifications of the stationary solutions of this model. We are interested in an analysis full classification of the one-flux solutions equation [START_REF] Newell | Wave turbulence and intermittency[END_REF] for for different values of the problem parameter s. More exactly, we introduce a (KZ index) parameter k = (s -2)/3 for the direct cascade solutions and k = (s -3)/3 for the inverse cascade solutions, and show that there are three different types of behaviour in cases k > 1, k = 1 and k < 1. Further, in each of these cases, different qualitative behaviour of spectra is shown to correspond to different sectors on the phase-plane of a respective 2D dynamical system, including KZ and thermodynamic spectra, as well as sharp cut-offs and blow up behaviour on the frequency boundaries of the ranges occupied by the spectra.

The organisation of the article is as follows. In section 2, after some rearrangements of independent and dependent variables of equation [START_REF] Newell | Wave turbulence and intermittency[END_REF], we present the equation together with the dynamical systems both for the direct and indirect cascade solutions which make it suitable for finding the stationary solutions. Sections 3-5 are devoted to an analysis of the dynamical systems based on phase portraits for different values of k. Namely, we consider the following range of parameters k > 1, k = 1 and 0 < k < 1. The full classification is given in terms of sets of the qualitatively different orbits. A summary and discussion of results is given in section 6.

Stationary solutions

In this paper, we study the stationary solutions of the differential kinetic equation (2), i.e. solutions to the following stationary version of this equation:

I ∂ 2 ∂ω 2 ω s n 4 ∂ 2 ∂ω 2 1 n = 0. ( 12
)
Integrating this equation twice, we obtain

I ω s n 4 ∂ 2 ∂ω 2 1 n = P -Q ω, (13)
where P and Q are arbitrary constants having the meanings of the energy and the particle fluxes given by formulae [START_REF] Galtier | A weak turbulence theory for incompressible MHD[END_REF] and [START_REF] Connaughton | Non-stationary Spectra of Local Wave Turbulence[END_REF]. Therefore the investigation of steady states of equation ( 12) is reduced to the study of equation ( 13) for different choices of the constant fluxes P and Q. In the present work, we will restrict ourselves to the cases where either P = 0 or Q = 0. Moreover, having in mind physically realistic situations only, with n ≥ 0, we must take P ≥ 0 and Q ≤ 0, which a version of the Fjørtoft-Kraichnan dual-cascade statement [START_REF] Fjørtoft | On changes in the spectral distribution of kinetic energy for two-dimensional nondivergent flow[END_REF][START_REF] Kraichnan | Inertial ranges in two-dimensional turbulence[END_REF][START_REF] Newell | Wave turbulence and intermittency[END_REF]. ‡ The solutions with P = 0, Q ≥ 0 (or P ≤ 0, Q = 0) can be obtained from the solutions considered in the present paper using the symmetry in the equation ( 13) with respect to P → -P, Q → -Q, n → -n. Thus, in such solutions n ≤ 0 which makes them unphysical. Note that in the cases when one of the fluxes is zero, equation ( 13) is of the Emden-Fowler type i.e.

d 2 y dx 2 = ±x β |y| σ sgn y ( 14
)
after a change of variable y = 1/n and identifying ω = x. The asymptotic behavior of y(x) as x → ±∞ was extensively studied in many works, see e.g. [START_REF] Bellman | Stability theory of differential equations[END_REF]. This equation is integrable under σ + β = 0 and the solution is given in terms of the hypergeometric function, see for details [START_REF] Mehta | A note on a form of the Emden-Fowler equation[END_REF]. The generalized form of ( 14) (which extends on the equation ( 13) with arbitrary fluxes) is

d n y dx 2 = p(x)|y| σ sgn y, (15)
and the asymptotic analysis of solutions with respect to the growth properties of p(x) as x → ±∞ were presented in [START_REF] Samovol | On solutions of Emden-Fowler-type equations[END_REF].

To study the one-flux steady states for equation [START_REF] Newell | Wave turbulence and intermittency[END_REF], we perform the following transformations both for independent and dependent variables,

τ = ln ω, u = 1 ω k n , k = s -2 3 ( 16
)
for the cases with Q = 0, P ≥ 0 (direct cascade). Respectively, for P = 0, Q ≤ 0 (inverse cascade) we transform as

τ = ln ω, u = 1 ω k n , k = s -3 3 . ( 17
)
As a result, we get an autonomous semi-linear ODE for both one-flux situations (Q = 0, P ≥ 0 and P = 0, Q ≤ 0) of the form

u τ τ + (2k -1)u τ + k(k -1)u = Bu 4 , ( 18
)
where B is always a non-negative number, B = PI -1 for Q = 0 and B = -QI -1 for P = 0. ‡ The Fjørtoft-Kraichnan dual-cascade statement is that, in turbulent systems with two positive quadratic invariants, one of the invariants cascades downscale and the other-upscale from the forcing scale. In general, this statement is asymptotic: it applies to situations where the forcing and the dissipation regions are separated by large inertial intervals. In the differential models case, the inertial ranges do not have to be large: either P or Q vanish right outside of the forcing range, provided that there is only one such range. Mixed state with simultaneous P, Q = 0 can occur only in between of two (or more) forcing regions.

For equation ( 18) with B > 0, we are interested in full classification of solutions with different behaviours of u(τ ) (and, respectively, the spectrum n(ω)) both for finite and infinite ranges of τ or ω. Settings of the boundary value problems and analysis of existence of their solutions are based on a phase-space analysis of orbits of the underlying dynamical system.

It will be convenient to write down equation ( 13) with B = 1,

u τ τ + (2k -1)u τ + k(k -1)u -u 4 = 0, (19)
taking into account the fact that equation ( 18) admits a scaling group of transformations of independent variable τ and dependent variable u.

The easiest way to investigate solvability of boundary value problems for equation ( 19) is to consider the phase space plot of the respective autonomous dynamical system associated with equation ( 19):

du dτ = v, (20)
dv dτ = -(2k -1)v -k(k -1)u + u 4 . (21)
For equilibria we have either

u = v = 0 or u = (k(k -1)) 1 3
, v = 0. Therefore, we always have fixed point P 1 = (0, 0), and sometimes also fixed point P 2 = ((k(k -1)) 1 3 , 0). The latter exists only for k > 1 and k < 0 since from the physics u must be a nonnegative function. The linearised version of the dynamical system near the fixed point P 1 = (0, 0) reads

d dτ u v = 0 1 -k(k -1) -(2k -1) u v (22) with eigenvalues λ 1 = 1 -k and λ 2 = -k and eigenvectors ξ 1 = (1, 1 -k) ≡ (1, λ 1 ) and ξ 2 = (1, -k) ≡ (1, λ 2 )
. Correspondingly, near P 2 we have the following linearised system,

d dτ u v = 0 1 3k(k -1) -(2k -1) u v . ( 23
)
The eigenvalues are given by λ

1 = -k + 1 2 + 1 2 16k(k -1) + 1, λ 2 = -k + 1 2 - 1 2
16k(k -1) + 1 and eigenvectors ξ 1 = (1, λ 1 ) and ξ 2 = (1, λ 2 ). To analyse the behavior of orbits, we supplement equation ( 19) by the initial conditions

Phase space analysis for

u(0) = u 0 > 0, d dτ u τ =0 = 0. ( 24
)
These initial conditions mean that we study the orbits of the dynamical system which start on the u-axis of the phase plane (u, v). Notice that the direction of velocity (du/dt, dv/dt) on the u-axis is directed into the fourth quadrant for u < (k(k -1))

1 3
i.e. to the left from the stable-node fixed point P 1 (only u > 0 half-plane is physically relevant), and this vector field is directed out side of the fourth quadrant when u > (k(k -1))

1 3
i.e. to the right from the equilibria P 1. Correspondingly, the vector field (du/dt, dv/dt) is directed outside of the fourth quadrant on the v-axes for v < 0 and inside of the first quadrant on the v-axes for v > 0. Notice that equation ( 19) has an exact positive solution (u, v) = (u P 2 , 0) with u P 2 = (k(k -1))

1 3
which corresponds to the saddle point P 2 on the phase plane and also exists the trivial solution (u, v) = (u P 1 , v P 1 ) = (0, 0) which corresponds to the stable node P 1. Solution (u, v) = (u P 2 , 0) is the famous KZ spectrum with n ∼ ω -k .

We begin with a preliminarily analysis of the behaviour of orbits of the dynamical system (20), (21) which start to left from the fixed point P 2. This assertion is natural considering the fact that the system (20), (21) can be interpreted as a motion of Newtonian particle is a system with potential Φ(u) = k(k -1)u 2 /2 -u 5 /5 (with a minimum at u = 0 and a maximum at u = u P 2 ) and a positive friction. To prove this Lemma, we show that for equation (19) the maximum (minimum) principle holds in the following form. Proposition 3.1 For any τ min < ∞, solutions u(τ ) of the Cauchy problem (19), (24) cannot achieve a non-negative minimum at τ = τ min with 0 ≤ u min = u(τ min ) < (k(k -1))

1 3 .
If u min > 0 then the assertion of this proposition immediately follows from a simple analysis of signs of terms of equation ( 19). For u min = 0 and since this is a minimum, u τ | τ =τ min = 0, we have (u min , v min ) = (0, 0). However, since this is a fixed point, it cannot be reached at a finite "time", τ min < ∞. The proof of this assertion is evident.

Proposition 3.3 Derivative u τ is a uniformly bounded function on the set {τ : u(τ ) ≥ 0, u(0) ≤ (k(k -1)) 1 3 }.
In order to prove it, we multiply equation ( 19) by u τ and integrate over [0, τ ], τ ≤ τ * * with u(τ * * ) = 0. As a result, we get the following integral (energy balance) identity,

1 2 u τ (τ ) 2 + (2k -1) τ 0 u 2 s ds + Φ(u(τ )) = Φ(u 0 ), (25)
where

Φ(u) = k(k-1)u 2 2 -1 5 u 5 . We have Φ(u) > 0 for 0 < u < 5 2 k(k -1)
1 3 and Φ(u) < 0 for u > 5 2 k(k -1) 1 3 . Φ(u) achieves a positive maximum at u = (k(k -1))

1 3 . It follows from Proposition 3.1 that Φ(u(τ )) ≥ 0, since u 0 ≤ (k(k -1)) 1 3 . Therefore u 2 τ (τ ) is an uniformly bounded function for τ ∈ [0, τ * * ].
To proceed with the proving Lemma 3.1, we assume the contrary i.e. that there exists an orbit U u 0 which does not achieve the fixed point P 1. By Proposition 3.1, it is evident that U u 0 has to approach the v-axis, and due to Proposition 3.3 the orbit has to intersect the v-axis at a finite point with v < 0. Further, with an inverse time direction τ = -τ , take an orbit U ξ 1 which goes out of P 1 along the eigenvector ξ 1 : then U ξ 1 is above the orbit U u 0 on the phase plane. Considering the fact that in the fourth quadrant the vector field at infinity is pointing into the fourth quadrant, by the Poincaré-Bendixon theorem U ξ 1 always intersects the u-axis. In terms of solutions of the Cauchy problem (19), (24), the orbit U ξ 1 (U u 0 ) corresponds to u ξ 1 (u u 0 ), a solution of (19), (24). u ξ 1 (t) is a positive function which monotonously decreases to zero as τ → ∞. The latter property follows from Proposition 3.1. In fact, u ξ 1 (τ ) is a sub-solution for u u 0 (τ ). It means that u u 0 (τ ) is a monotonously decreasing function such that u u 0 (τ ) → 0 as τ → ∞. Hence U u 0 intersects v-axis at P 1 only, which proves Lemma 3.1.

Consider a family O a I , the orbits U u 0 with 0 < u 0 < (k(k -1))

1 3 . This family depends continuously on u 0 that follows from the continuous dependence of solutions u(τ ; u 0 ) of the Cauchy problem (19), (24) with respect the initial data. Moreover, the first-order derivatives of u(τ ; u 0 ) are uniformly bounded functions with respect to u 0 . Hence there exist the limit of U u 0 as u 0 goes to (k(k -1)) 1 3 and this is exactly the heteroclinic orbit H which connects the fixed points P 1 and P 2.

For analysing the other orbits from the fourth quadrant of the phase space (u, v), we will use the fact that the vector field (du/dτ, dv/dτ ) is directed out of the fourth quadrant on the v-axis. The slope of this vector on the v-axis is always constant i. e. du/dv = -1/(2k -1). We denote the corresponding orbits by O II . With the inverse time τ , these orbits cannot leave the fourth quadrant of the phase plane due to the fact that on the u-axis for u > (k(k -1)) 1 3 , the vector field (du/d t, dv/d t) is directed inside the fourth quadrant: we call these orbits O a III . Therefore there exists an orbit S II,III which separates the families O II and O a III . This is exactly a separatrix passing through the saddle point P 2. By the Poincaré-Bendixon theorem it follows that the separatrix S II,III goes to infinity never approaching the u-or v-axes.

To complete analysing the phase-space plot of the dynamical system (20),(21), we turn our attention to the orbits in the first quadrant of the phase plane. We will use the fact that on the v-axis the vector field (du/dτ, dv/dτ ) is directed into the first quadrant. With this and using the information about the behavior of the vector field (du/dτ, dv/dτ) on the u-axis, we get that there exists an orbit S IV,I intersecting P 2 separating the orbits which cross and do not cross the u-axis respectively. In the inverse time direction, τ = -τ , the separatrix S IV,I has to intersect the v-axis at a finite point. The proof follows from analysing again the integral identity (25) which also holds for S IV,I . Therefore there exist orbits intersecting the v-axis, O b I , which enter the first quadrant, in the positive time direction, and then intersect the u-axis with u ≤ (k(k -1)) Indeed, assuming the contrary we get that Φ(u(τ )) is finite and therefore u τ (τ ) < ∞ as τ → ∞ that guarantees that the orbit under consideration does not approach the line u = const with time.

We will now put together the classification of the orbits, see Figure 1.

. 1 3 . In part O II orbits goes from infinity of the fourth quadrant intersecting the v-axis (never intersecting u-axis). In part O III orbits emerge with (u, v) → (∞, -∞), go down along S III,IV separatrix, intersecting u-axis with u ≥ (k(k -1)) 1 3 , and then turn up to extending into the first quadrant never intersecting v-axis. The O IV orbits enter into the first quadrant intersecting the v-axis above S IV,I separatrix and then extend with (u, v) → (∞, ∞) never intersecting the u-axis. Now we will consider how the orbits classified in Theorem 3.1 could be linked to the classification of solutions of the original equation. First, we note that on the u-axis the profiles u(τ ) reach maxima, which corresponds to minima of the "compensated" spectrum ω k n(ω). In the other words, on the u-axis the spectrum n(ω) changes from being steeper than KZ (above the axis) to being shallower than KZ.

We proceed by considering spectra corresponding to the separatrix S III,IV and show that u(τ ), which corresponds to S III,IV , blows up at a finite time τ * i.e. u(τ ) → ∞ as τ → τ * . We know that S III,IV goes to infinity in both u and v. Further, for u ≫ 1 and v ≫ 1, the dynamics of this separatrix in the leading order is governed by

du dτ = v, (27)
dv dτ = u 4 (28)
since v ∼ u 5/2 ≪ u 4 for u ≫ 1. The system (27, 28) is a Hamiltonian type with the Hamilton function H = v 2 /2 -u 5 /5. Integrating in the asymptotic limit u 5 /5 ≫ H, we get

u(τ ) = (2/3) 2/3 (5/2) 1/3 (τ * -τ ) -2/3 , τ < τ * < ∞. (29)
Respectively, for the spectrum n(ω), we have

n(ω) = ω -2/3 (3/2) 2/3 (2/5) 1/3 ln 2/3 (ω * /ω) ≈ ω -4/3 * (4/15) 1/3 (ω * -ω) 2/3 , ω < ω * < ∞, (30)
i.e. a sharp front on the right. The behaviour of u(τ ) which corresponds to the separatrix S II,III is analysed similarity. It can be done in terms of the reverse time τ . As a result, we get the asymptotic solution

u(τ ) = (2/3) 2/3 (5/2) 1/3 (τ * * -τ ) -2/3 , τ < τ * * < ∞ (31)
and in the original variables ω, n we have

n(ω) ≈ ω -4/3 * * (4/15) 1/3 (ω -ω * * ) 2/3 , ω * * < ω < ∞, (32)
i.e. a sharp front on the left. Similarly, we consider the orbits located between the separatrices S III,IV and S II,III i.e. the ones belonging to O III . It follows from above that the spectrum n(ω) corresponding to these orbits realises profiles with finite supports (i.e. with sharp fronts on both right and left).

Consider behaviour near the v-axis.

In the leading order, the dynamical system (20,21) is reduced to

du dτ = v, (33)
dv dτ = -(2k -1)v ( 34
)
for u ≪ v. Solving this system, we have

u = v 0 2k -1 e -(2k-1)τ 0 -e -(2k-1)τ , n = 2k -1 v 0 (ω 1-2k 0 -ω 1-2k )ω k ≈ ω k 0 v 0 1 (ω -ω 0 ) . ( 35
)
We see that spectrum n(ω) blows up at a finite point ω 0 : at its left boundary for for v > 0 (O I orbits) and at its right boundary for for v < 0 (O II orbits).

To complete, we consider orbits near the equilibrium point P 1,

u = c 1 e (-k+1)τ + c 2 e -kτ , (36)
where c 1 , c 2 = const. This corresponds to a thermodynamic Rayleigh-Jeans spectrum

n = T µ + ω , ( 37
)
where T and µ are constants having meanings of a temperature and a chemical potential respectively. In fact, since the close vicinity of P 1 corresponds to τ, ω → ∞, we have n ≈ T /ω, except for a single orbit (entering P 1 along the second eigenvector direction) for which n =const. Positivity of n for ω → ∞ dictates that T > 0.

Easy to see that spectra (35) are also thermodynamic-they can be written in the form (37) after a suitable choice of constants T and µ. In particular spectra with v 0 > 0 correspond to T > 0, µ < 0 and spectra with v 0 < 0 -to T < 0, µ < 0. Note that the solution corresponding to the separatrix H has µ = 0.

For the separatrix S IV,I , the corresponding solution u(τ ) is a function monotone increasing from zero to u = (k(k -1)) 1/3 , i.e. to the equilibrium P 2 which corresponds to the KZ spectrum n = (k(k -1)) -1/3 ω -k .

The behavior of the spectra corresponding to the separatrices H, S IV,I , S II,III and S III,IV are presented on Figure 2 and Figure 3.

Correspondingly, the orbits from O I lying close to the separatrices S IV,I and H correspond to spectra n(ω) which start at a sharp front like in (35), continue with an intermediate KZ asymptotic and then asymptote to the thermodynamics spectrum (37) (see Figure 4, left). Note that presence of an intermediate KZ asymptotic is observed for all orbits passing close enough to the fixed point P 2 in the O I , O II , O III or O IV sectors.

The orbits from O II represent spectra vanishing at a finite point ω on the left boundary of the spectrum support. They have an intermediate KZ asymptotic (if the orbit pass close enough to P 2). Further, n(ω) blows up at a finite point ω on the right boundary of the spectrum support (see Figure 4, right).

The orbits from O III represent spectra vanishing at a finite points ω on both the left and the right boundaries of the spectrum support. Again, they have an intermediate KZ asymptotic (if the orbit pass close enough to P 2).

The orbits from O IV which start on the v-axis, which corresponds to a spectrum which has a left-boundary blowup of the form (35). Then the spectrum asymptotes to the KZ spectrum (if the orbit passes close enough to P 2) and finally n(ω) vanishes at a finite wave number (see Figure 5, right).

Phase analysis for k = 1

The case k = 1 corresponds to the example of the direct cascade in the 2D NLS wave turbulence. This case is degenerate since the KZ scaling n ∼ ω -k coincides with the thermodynamic scaling n ∼ ω -1 .

The dynamical system reads

du dτ = v, (38)
dv dτ = -v + u 4 (39)
and we have only a single fixed point P 1 = (0, 0). The differential matrix of the righthand side of (38, 39) at P 1 is

∆(0, 0) = 0 1 0 -1 . (40)
Therefore P 1 is a saddle-node with the eigenvalues λ 1 = 0, λ 2 = -1. The stable manifold S lies on the line u + v = 0 while the central (slow

) manifold U near P 1 is v = u 4 ; (41)
it expands from the origin into the half-plane u > 0. Nontrivial dynamics of the dynamical system near by P 1 can be described locally as s restriction of the phase flow to the central (slow) manifold, see [START_REF] Carr | Applications of Center Manifold Theory[END_REF]. Namely, for small values of ω, near P 1, the stable manifold of P 1 will dominate the dynamics and will quickly bring the orbits very close to its slow manifold unless the initial point is already on the slow manifold.

The dynamics (38) in the vicinity of P 1 on the slow manifold (41) is governed by

du dτ = u 4 , (42)
which can be easily integrated,

u = 1 3 1/3 (τ 0 -τ ) 1/3 , n = 3 1/3 ln 1/3 (ω 0 /ω) ω . (43)
This is the log-corrected KZ spectrum. The thermodynamic spectrum in this case corresponds to the motion along the stable manifold giving n ∼ 1/ω. Lemma 4.1 All orbits of the dynamical system (38), (39) starting in the first quadrant of the phase plane expand into the first quadrant never intersecting the u and v-axes and without being bounded in either u or v.

The latter assertion immediately follows from the observation that the vector field (du/dτ, dv/dτ ) restricted on these axes is directed into the first quadrant. Since there are no fixed points apart from P 1, by the Poincaré-Bendixon theorem it follows that the orbits must go to infinity in time τ . The orbits cannot be bounded in u: this follows from the integral identity

1 2 u τ (τ ) 2 + τ 0 u 2 s ds = Φ(u 0 ) -Φ(u(τ )), (44)
where Φ(u) = -1 5 u 5 , and the right-hand side of (44) is always positive quantity. If u(τ ) was a bounded function for all τ then u τ (τ ) 2 would also be a bounded quantity. Now suppose v is bounded and u is unbounded. Then for u → ∞ one can neglect the first terms on the left-hand and the right-hand sides of (44). Differentiating the remaining equation, we get u τ = u 4 , i.e. v = u τ → ∞ which is a contradiction. Thus v is unbounded and this completes the proof of Lemma 4.1.

Consider the orbits from the fourth quadrant of the phase plane. Their behavior is analysed similar by the change of the time direction τ as τ = -τ . With this, the orbits from the fist and fourth quadrants (which are the only ones physically admitted because u is non-negative) are divided into the three different classes: O I , O II and O III . The orbits O I and O III are separated by the orbit U which, near P 1, is v = u 4 (the slow manifold). The orbits O II of the fourth quadrant are the ones that intersect the v-axes for v < 0 with slope -1. The stable manifold separatrix S separates the orbits O II and O III . S goes from infinity to the equilibrium P 1. The orbits from O III are located between U and S. These orbits go from infinity of the fourth quadrant always intersecting the u-axis and then approaching the separatrix U.

Summarising, we have the following classification of the orbits, see Figure 6. Having this classification, we can proceed to the classification of solutions n(ω) as in section 3. Consider the orbits from O I and their dynamics near the v-axis:

du dτ = v, (45)
dv dτ = -v, (46)
Solving this system, we have

u = v 0 e -τ 0 -e -τ , n = ω 0 v 0 (ω -ω 0 ) (47)
or in terms of the thermodynamical spectrum

n = T (µ + ω) . ( 48
)
For v > 0 we have T > 0, µ < 0, ω > -µ (left front blowup) and for v < 0 we have T < 0, µ < 0, ω < -µ (right front blowup). The existence of central (slow) manifold leads the intermediate asymptotic (43) for orbits passing close enough to P 1.

Finally as τ → ∞ i.e. for u ≫ 1 and v ≫ 1, the dynamics is reduced to

du dτ = v, (49)
dv dτ = u 4 . (50)
Again, u(τ ) blows up at a finite time τ * . Respectively, spectrum n(ω) vanishes at ω * < ∞,

n(ω) ∼ (ω -ω * ) 2/3 (51)
as ω → ω * and ω < ω * . Similarly for for u ≫ 1 and -v ≫ 1, using the the inverse time direction τ , we get that spectrum n(ω) vanishes at ω * * < ∞,

n(ω) ∼ (ω * * -ω) 2/3 . (52)
The behaviour of spectrum n(ω) described above is summarised in Figures 7 and8.

Phase analysis for 0 < k < 1

The case 0 < k < 1 is realised for the 3D NLS inverse cascade (k = 7/6), and the SNE turbulence in all the cases -the 2D direct cascade (k = 1/3), the 3D direct cascade (k = 5/6), the 2D inverse cascade (k = 0) and the 3D inverse cascade (k = 1/2). This is the case when the pure KZ spectrum cannot be realised because it formally corresponds to a negative spectrum, n = (k(k -1)) -1/3 ω -k < 0 § With k < 1 we have only a single fixed point of the dynamical system (20), (21) in the right half plane of the phase plot, u ≥ 0: P 1 = (0, 0). The eigenvalues of the linearised matrix at P 1 equal λ 1 = -k < 0 and λ 2 = -k + 1 > 0, i.e. P 1 is the saddle point. The eigenvectors are ξ 1 = (1, λ 1 ) and ξ 2 = (1, λ 2 ). Lemma 5.1 All orbits of the dynamical system (20), (21) starting in the first quadrant of the phase plane expand into the first quadrant never intersecting the u and v-axes and without being bounded in either u or v.

The proof of this Lemma completely repeats the proving Lemma 4.1 -now using the integral identity (26). Again similarly, we analyse the fourth quadrant.

Thus, similar to how it was done in section 4, the orbits from the first and fourth quadrants are divided into three different classes: O I , O II and O III . Let us denote the stable and unstable manifolds of P 1 by S and U. The orbits O I and O III are separated by the orbit U, whereas the orbit S separates the orbits O II and O III . With this, we get the following classification of the orbits, see Figure 9.

Theorem 5.1 The stable and unstable manifolds of P 1, S and U, divide the phase plane to O I , O II and O III parts with different behaviour of orbits. The orbits from O I (above U) approach the separatrix U with (u, v) → (∞, ∞) as τ evolves. Between U and S, i.e. in O II , the orbits arrive from infinity along S towards P 1 intersecting the u-axes and then turn back asymptoting to the separatrix U in τ . In part O III (below S) § Alternatively, one could say that the spectrum is positive but the flux is in a "wrong" direction, P < 0. This becomes evident if we rescale our solution to consider cases with arbitrary values of B = P/I, which gives n = (k(k -1)P/I) -1/3 ω -k . The behaviour of spectrum n(ω) for u, v ≪ 1 i.e. near P 1 is

n ∼ ω -1 . (58)
Summarising, the orbits O I start on the v-axis with the spectrum which has the form (57). Then they asymptote to the separatrix U as τ evolves and finally n(ω) vanishes at a finite frequency; see the left panel of Figure 11. The orbits form O II has the spectrum behaviour in the reverse order with respect to O I ; see the centre panel of supported i.e. n(ω) > 0 only on a bounded interval (ω * , ω * * ), see the right panel of Figure 11. They intermediately asymptote to the pure thermodynamical spectrum ω -1 if their orbits pass near the equilibrium P 1. Note that passing close to P 1 means that the forcing and the dissipation scales are well separated (since the motion is very slow near P 1).

Discussion

In this paper, we have presented an exhaustive study and a full classification of all possible one-flux steady states for both the direct and inverse cascade solutions of the differential kinetic equation of local wave turbulence (19). The behaviour is shown to be qualitatively different in three cases: k > 1, k = 1 and k < 1 where k = (s -2)/3 is the KZ exponent.

In particular, the KZ scaling can be observed (in its pure form or as an asymptotic) only for k > 1. "Warm" cascades realising states with mixed thermodynamic and flux components are also possible in this case. They are represented by a great variety of spectra with different values of thermodynamic potentials T and µ, some of them characterised by a sharp front or/and a blowup near the forcing or/and dissipation scale. The spectrum blowup behaviour could be interpreted as a condensation phenomenon. Which of the spectrum is realised is determined by the type of forcing and dissipation in each particular case.

Case k = 1 is degenerate: the KZ and the thermodynamic exponents coincide. Thus, a log-corrected spectrum is realised instead of the pure power-law KZ spectrum. No KZ scaling can be realised in the case k < 1, neither in its pure form nor as an asymptotic. All spectra are "warm" in this case: they are close to the pure thermodynamic Rayleigh-Jeans spectrum deeply in the inertial range if the forcing and the dissipative scales are well-separated.

Finally, for any k the solutions are divided into distinct classes corresponding to the orbits of the phase plane divided by separatrices which connect fixed points of the corresponding dynamical system with each other or with infinity. There are four of such classes in the case k > As a concluding remark we note that, in spite of a great variety of the found solutions, there exist also stationary solutions in which both fluxes P and Q are present simultaneously. These solutions are important in cases where forcing is present at two or more different scales. Unfortunately in such cases the respective dynamical system is not autonomous and cannot be analysed by the phase-plane method presented in this paper. However, it would be interesting in future to analyse such solutions, for instance numerically.

k > 1

 1 Physical examples with k > 1 include: 3D NLS direct cascade (k = 3/2), 3D NLS inverse cascade (k = 7/6), deep water gravity wave direct cascade (k = 8) and inverse cascade (k = 23/3), gravitational waves direct cascade (k = 2 in 2D and k = 3 in 3D) and inverse cascade (k = 5/3 in 2D and k = 8/3 in 3D), Langmuir and spin waves direct cascade (k = 13/6) and inverse cascade (k = 11/6).

Lemma 3 . 1 1 3

 311 The orbits of the dynamical system (20), (21) intersecting the u-axis with u ≤ (k(k -1)) go to the fixed point P 1.

Proposition 3 . 2

 32 Monotone decreasing solution u(τ ) cannot asymptote to a constant c as τ → ∞ excepting the values of c equals 0 or c = (k(k -1)) 1 3 .

1 3 . 1 3

 31 Since the fixed point P 2 is a saddle point then there exists a separatrix S III,IV which expands into the first quadrant. S III,IV separates the orbits with different behaviours, O b III and O IV . Lemma 3.2 The orbits of the dynamical system (20), (21) intersecting the u-axis with u ≥ (k(k -1)) go to infinity never asymptoting the line u = const i.e. these orbits extend indefinitely. The proof follows immediately from the integral identity 1 2 u τ (τ ) 2 + (2k -1) τ 0 u 2 s ds + Φ(u(τ )) = Φ(u 0 ). (26)

Figure 1 .

 1 Figure 1. Phase portrait of the dynamical system for k = 3/2. The separatrixes are shown by different color lines.

Figure 2 .Figure 3 .

 23 Figure 2. Sketches of spectra in case k > 1. Left: separatrix H. Right: separatrix S IV,I .

Figure 4 .

 4 Figure 4. Sketches of spectra in case k > 1 for orbits passing near P 2. Left: orbits from O I . Right: orbits from O II .

Figure 5 .

 5 Figure 5. Sketches of spectra in case k > 1 for orbits passing near P 2. Left: orbits from O III . Right: orbits from O IV .

Figure 6 .

 6 Figure 6. Phase portrait of the dynamical system for k = 1. The separatrices U and S are shown by different colour lines.

Theorem 4 . 1 U

 41 and S divide the phase half plane (0 < u < ∞, -∞ < v < ∞) into parts O I , O II and O III with the different behaviours of orbits. In part O I (above U) the orbits intersecting the u-axis (never intersecting v-axis) asymptote to the separatrix U as τ → ∞. In part O II (below S) the orbits emerge out infinity of the fourth quadrant and go down along S always intersecting the v-axis for v < 0. Between U and S, i.e. in O III , the orbits go from infinity along S emerging at the first quadrant and approaching U as τ → ∞.

Figure 7 .

 7 Figure 7. Sketches of spectra in the case k = 1. Left: the separatrix U . Right: the separatrix S.

Figure 8 .

 8 Figure 8. Sketches of spectra in the case k = 1. Left: O I orbits. Centre: O II orbits. Right: O III orbits.

1 Figure 10 .

 110 Figure 10. Sketches of spectra in the case k = 2/3. Left: separatrix S. Right: separatrix U .

Figure 11 .Figure 11 .

 1111 Figure 11. Sketches of spectra in case k = 2/3. Left: spectrum behaviour for the orbits O I . Centre: spectrum behaviour for the orbits O II . Right: spectrum behaviour for the orbits O III .

  1 (O I , O II , O III and O IV ) and three classes for k ≤ 1 (O I , O II , O III ).

Acknowledgements

Sergey Nazarenko is supported by the Chaire D'Excellence IDEX (Initiative of Excellence) awarded by Université de la Côte d'Azur, France, Simons Foundation Collaboration grant Wave Turbulence (Award ID 651471), the European Unions Horizon 2020 research and innovation programme in the framework of Marie Skodowska-Curie HALT project (grant agreement No 823937) and the FET Flagships PhoQuS project (grant agreement No 820392). Vladimir Grebenev's, Boris Semisalov's and work on this project was partially supported by the "chercheurs invités" awards of the Fédération Doeblin FR 2800, Université de la Côte d'Azur, France. Sergey Medvedev's and work on this project was partially supported by CNRS "International Visiting Researcher" award.

the orbits emerge out infinity in the fourth quadrant always intersecting the v-axis for v < 0. Similarly to how it was done in the case k > 1 the dynamics of the separatrix U as τ → ∞ in the leading order is governed by the dynamical system (27, 28). It means that

The spectrum n(ω) behaves as

The separatrix S for u ≫ 1 and v ≪ -1 is analysed similarly by changing the direction of time τ as τ . As a result, we get

Then the spectrum n(ω) behaves as

The corresponding spectra are presented on Figure 10. Behaviour of the orbits near the v-axis, u ≪ v, is again derived from the system (33, 34) i.e. using the formula (35)

where T = ω k 0 /v 0 and µ = -ω 0 < 0. For the orbits from O I we have T > 0 (left boundary blowup) and for the orbits from O II we have, respectively, T < 0 (right boundary blowup).

Note that formula (35) was obtained for k = 1/2, but it is easy to see that the same asymptotic formula appears in the case k = 1/2 too.