Amir Daneshgar

Ramin Javadi

Laurent Miclo

On nodal domains of finite reversible Markov processes and spectral decomposition of cycles

Keywords: Reversible Markovian generator, spectral decomposition, Cheeger's inequality, principal Dirichlet eigenvalues, Dirichlet connectivity spectra, nodal domains of eigenfunctions, optimal partitions of state space, Markov processes on discrete cycles, exit times 60J27, secondary: 60J35, 60E15, 15A18, 49K35, 31C20, 05C38

Let L be a reversible Markovian generator on a finite set V. Relations between the spectral decomposition of L and subpartitions of the state space V into a given number of components which are optimal with respect to min-max or max-min Dirichlet connectivity criteria are investigated. Links are made with higher order Cheeger inequalities and with a generical characterization of subpartitions given by the nodal domains of an eigenfunction. These considerations are applied to generators whose positive rates are supported by the edges of a discrete cycle Z N , to obtain a full description of their spectra and of the shapes of their eigenfunctions, as well as an interpretation of the spectrum through a double covering construction. Also, we prove that for these generators, higher Cheeger inequalities hold, with a universal constant factor 48.

Introduction and results

Classical Cheeger inequalities for finite reversible Markov processes make a link between the spectral gap and the connectivity constants, which are obtained by minimizing isoperimetric-type quotients over decompositions of the state space into two disjoint parts. The purpose of this article is to obtain such inequalities between the whole spectrum and decompositions of the state space into several parts, when the underlying graph is a cycle. For this we keep on developing the general approach suggested in [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF], where the case of trees is treated, and is based on an intermediate Dirichlet connectivity spectrum in a corresponding continuous model which is defined through taking into account the first Dirichlet eigenvalues associated to the elements of the decompositions. We also investigate the relations between this intermediate spectrum and the nodal domains of the eigenfunctions of the finite reversible Markov process under consideration. Nevertheless, to deduce the shape of these eigenfunctions when the underlying graph is a cycle, new intermediate quantities will have to be considered.

While we were writing this article, we learned that the Dirichlet connectivity spectrum had already been studied in the continuous context of Laplace-Beltrami operators on Euclidian or Riemannian subdomains with Dirichlet boundary conditions (e.g. see [START_REF] Helffer | Nodal domains and spectral minimal partitions[END_REF] by Helffer, Hoffmann-Ostenhof and Terracini and the references therein), however, it seems that the motivations in their context are far from ours, since the regularity and the geometry of the boundaries of the elements of the minimal decompositions are important in their study, while our main motivation is Conjecture 3 described in the sequel, that can also easily be extended to the continuous state space situation 1 . In what follows, we present a thorough study of the minimizing decompositions for the different introduced spectra and we also study their relationships to nodal domains of the corresponding eigenfunctions. Up to our knowledge, the results on the spectral decomposition of Markov generators on cycles are new and they can be extended to diffusion generators on the cycle which can be written in divergence form (this corresponds to the reversibility assumption).

In the rest of this section we first go through some preliminary definitions and background and then we present an overview of what appears in the next forthcoming sections of this article.

Preliminary definitions and background

In what follows N and R are the sets of natural and real numbers, respectively, and for a, b ∈ N, we define a, b {a, a + 1, . . . , b} and b 1, b . Let V be a finite set of cardinal N ∈ N, and consider a Markovian generator L (L(x, y)) x,y∈V , i.e a matrix whose entries are non-negative outside the diagonal and whose row sums are all equal to zero, with |L| max x∈V |L(x, x)|. Also, we assume that there exists a positive (nowherezero) probability measure µ on V such that L is reversible with respect to µ, i.e ∀ x = y ∈ V, φ({x, y}) µ(x)L(x, y) = µ(y)L(y, x).

This assumption implies that L is diagonalizable in R. Let 0 = λ 1 ≤ λ 2 ≤ • • • ≤ λ N be the eigenvalues with multiplicities of -L. The motivation for the study of higher order Cheeger inequalities is to compare these eigenvalues with connectivity related quantities such as isoperimetric numbers (e.g. see [START_REF] Daneshgar | On the isoperimetric spectrum of graphs and its approximations[END_REF] and references therein).

As another consequence of reversibility of L, we have ∀ x = y ∈ V, L(x, y) > 0 ⇔ L(y, x) > 0 that leads us to endow V with an undirected and loopless graph structure2 whose edge set is E {{x, y} : L(x, y) > 0}.

Hereafter, this graph is denoted by G (V, E). Let D 1 (V) be the set of all non-empty subsets A ⊂ V and for k ∈ 2, N , consider D k (V) the set of k-tuples A (A 1 , . . . , A k ) of disjoint elements from D 1 (V), called k-subpartitions. To any A ∈ D 1 (V), we associate its connectivity defined by

ι(A) φ(∂A) µ(A)
where φ is considered as a positive measure defined on E as in Equation ( 1), and ∂A {{x, y} ∈ E : x ∈ A and y ∈ A}.

Hence, φ(∂A) should be interpreted as a measure of the discrete boundary of A. Now, for any k ∈ N , we introduce the k th -order isoperimetric constant as

I k min (A1,...,A k )∈D k (V) max j∈ k ι(A j ).
The family (I k ) k∈ N is sometimes called the isoperimetric spectrum of L. One may naturally ask about the relationship between these numbers and the usual spectrum (λ k ) k∈ N , and in particular one may ask about the correctness of the following higher order Cheeger inequalities.

Conjecture 1 For any k ∈ N, there exists a universal constant χ(k) > 0 such that for any finite reversible generator L as above, we have

∀ k ∈ N , χ(k) I 2 k |L| ≤ λ k ≤ 2I k . (2)
The interested reader is referred to [START_REF] Daneshgar | On the isoperimetric spectrum of graphs and its approximations[END_REF][START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] for some motivations and background in this regard. It is easy to verify the upper bound λ k ≤ 2I k using the variational formulation of eigenvalues for all k ∈ N . Also, the case k = 2 is well-known and corresponds to the traditional discrete Cheeger inequality with χ(2) = 1/2 (see Lawler and Sokal [START_REF] Lawler | Bounds on the L 2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality[END_REF]). 3 It is furthermore easy to verify that the bound I 2 N /|L| ≤ λ N is always true. Indeed, up to a change of indices, D N (V) is just the family of singleton subsets. But for any x ∈ V, we have ι({x}) = |L(x, x)| and it follows that I N = |L|. On the other hand, we have

λ N = max f =0 (-µ[fL[f]])/µ[f 2 ],
and consequently, by considering indicator functions of points, we have λ N ≥ |L|. Moreover, it can be seen that Conjecture 1 is true with the constant χ(k) ≡ 1/2 independent of k ∈ N, if the graph G is acyclic (see the results of Section 2 along with [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] that provide a complete proof. Also, see [START_REF] Daneshgar | On the isoperimetric spectrum of graphs and its approximations[END_REF] for a proof in the generic case).

In [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF], the spectrum (Λ k ) k∈ N is introduced, which in some sense is midway between (λ k ) k∈ N and (I k ) k∈ N . To recall its definition, we first associate a continuous graph G to the discrete graph G for which V

V and each edge {x, y} ∈ E is replaced by a "solid" segment [x, y] of length 1 and we define G ∪ {x,y}∈E [x, y] in which the boundary points of these edge-segments corresponding to a given vertex x ∈ V are all identified with a unique point still designated by x. Clearly the edge set of G is defined as E {[x, y] : {x, y} ∈ E}. Also, we refer to any general element of G as a point, while the elements of V = V are referred to as vertices. In this setup, the neighborhood of a point a ∈ G is defined as

N (a) {x ∈ V : ∃ {x, y} ∈ E, a ∈ [x, y]}.
As a general remark on the notations, we use Roman letters (e.g. V, E, f ) to refer to objects in the continuous model where Sans-serif letters (e.g. V, E, f) are used to refer to discrete objects. In this setup, by abuse of notation, we use the same notations for all operators that appear in both continuous and discrete models, where the operand will clarify the exact definition of these concepts (e.g. E(f) (defined below) stands for the energy of a (discrete) function f that is defined on the set of vertices V while E(f ) refers to the energy of a function defined on the continuous graph G). Also, if g is a function defined on the continuous model, then g which is defined on the vertex set V of the discrete model stands for the restriction g| V .

For any {x, y} ∈ E, the segment [x, y] ∈ E is endowed with the measure ν x,y φ({x, y})d x,y , where d x,y is the natural Lebesgue measure on [x, y]. We define d {x,y}∈E d x,y and ν {x,y}∈E ν x,y , which are non-negative measures whose total mass are |E| and 1/2

x∈V µ(x) |L(x, x)|, respectively. The measure ν enables us to define a Dirichlet form E on the space F (G) of absolutely continuous real functions defined on G (i.e. that are absolutely continuous on all edge-segments) via

∀ f ∈ F (G), E(f ) (f ) 2 dν ∈ R + {+∞}
where f stands for the weak derivative of f . Analogously, we may define a discrete Dirichlet form on the space F (V) of real functions defined on V as

∀ f ∈ F (V), E(f) {x,y}∈E |f(x) -f(y)| 2 φ({x, y}) ∈ R + .
The probability measure µ is naturally extended to G via the formula µ = x∈V µ(x)δ x (where we use the same notation for both discrete and continuous models), and for a function f ∈ F (G) we define

µ[f ] = µ[f] x∈V f(x)µ(x).
Following our notations, let D 1 (G) (or D 1 for short) be the set of subsets A ⊂ G which are open, connected and whose intersection with V is non-empty. For such a subset A ∈ D 1 (G), let ∂A denote the boundary of A (in the usual topological sense) and also let F 0 (A) be the subspace of F (G) consisting of functions that vanish on the complementary set G\A. Also, for a subset A ∈ D 1 (V), F 0 (A) can be defined analogously. Now, we are ready to introduce the (continuous and discrete) principal Dirichlet eigenvalue, λ 1 (A) and λ 1 (A), as follows.

∀ A ∈ D 1 (G), λ 1 (A) inf f ∈F0(A) : µ[f 2 ] =0 E(f ) µ[f 2 ] , (3)
∀ A ∈ D 1 (V), λ 1 (A) inf f∈F0(A) : µ[f 2 ] =0 E(f) µ[f 2 ] .
These quantities should be interpreted as a measurement of the easiness to get out of A or A for the underlying process (see [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] for a precise description in which one has to introduce instantaneous points to deal with the difference between G and G). Also, if A ∈ D 1 , then f A ∈ F 0 (A) stands for the unique minimizing positive function in (3) satisfying µ[f 2 A ] = 1 (its positivity and uniqueness come from the connected assumption for A and Perron-Frobenius theorem, see [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] for the details). Now, in order to get a better understanding of the minimizers of (3), first, we define L : V × G → R as an extension of L, in the following way.

• For every (x, y) ∈ V × V we have L(x, y) = L(x, y).

• For any {x, y} ∈ E and any z ∈ G\V on the edge segment [x, y], we define

L(x, z) L(x, y)/d([x, z]),
where d is the natural measure on G introduced earlier (in the whole paper, d will only be used to measure distances inside edge segments). For any other x ∈ V \{x, y}, we let L(x , z) 0.

Moreover, define φ(x, z) µ(x) L(x, z) as an extension of φ to V × G. For any A ∈ D 1 , let A A ∩ V and construct the linear operator L A = ( L A (x, y)) x,y∈A defined on F 0 (A) as,

∀ x, y ∈ A L A (x, y)        L(x, y) x = y - x =z∈A∪∂A L(x, z) x = y. For a function f ∈ F (G), a subset A ⊆ G is said to be a nodal domain of f if it is a connected component of G \ {x ∈ V : f (x) = 0}
. Also, by a nodal domain4 of a function f ∈ F (V), we mean a nodal domain of the function f , the affine extension of f on edge segments of G. Now, let f A be the restriction to A of the unique minimizing non-negative function f A in (3) that satisfies µ[f 2 A ] = 1. We recall the following result from [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF].

Lemma 2 For any A ∈ D 1 , f A is the unique positive function defined on A A ∩ V satisfying µ[f 2 A ] = 1 and L A [f A ] = -λ 1 (A)f A . Also, we have λ 1 (A) = min f∈F0(A)\{0} -µ[f L A [f]] µ[f 2 ]
for which f A is a minimizing function whose affine extension is exactly the minimizer of (3), f A . In addition, if A is a nodal domain of an eigenfunction g = 0 associated to an eigenvalue λ of -L, then λ 1 (A) = λ and g is proportional to f A on A.

Now, for any k ∈ N , consider D k (G) (or D k for short) as the set of k-tuples A (A 1 , . . . , A k ) of disjoint elements from D 1 (G) (such k-tuples will be called k-subpartitions). The intermediate quantities mentioned before are defined, for any k ∈ N , by

Λ k inf (A1,...,A k )∈D k (G) max j∈ k λ 1 (A j ) . (4)
Hereafter, we refer to the family (Λ k ) k∈ N as the Dirichlet connectivity spectrum of L. Again, via the variational formulation of the eigenvalues, it is not difficult to see that the bounds λ k ≤ Λ k are always true, for all k ∈ N . But the following was left as a conjecture (see [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF]),

Conjecture 3 [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] For any k ∈ N, there exists a universal constant χ(k) > 0 such that for any finite generator L as above, we have

∀ k ∈ N , χ(k)Λ k ≤ λ k . (5)
Clearly by Perron-Frobenius theorem and Lemma 2, we have Λ 2 ≤ λ 2 and consequently Λ 2 = λ 2 . Also, by considering the N -subpartition corresponding to bisection of all edges, we have Λ N ≤ 2 |L| ≤ 2λ N . Furthermore, one of the main results of [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] states that if the graph G is a tree, then we have

∀ k ∈ N , Λ k = λ k . ( 6
)
Remark 4 In [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF], the definition of the continuous graph, say G, associated to G = (V, E) is slightly different. There, the segment [x, y] ∈ E has length 1/φ({x, y}) and is endowed with the corresponding Lebesgue measure and these conventions lead as above to a Dirichlet form E on the space F ( G) of absolutely continuous functions on G. But let ψ : G → G be the bijective mapping which, for any edge {x, y} ∈ E, transforms affinely the segment [x, y] ⊂ G into the corresponding segment [x, y] ⊂ G. The composition mapping

f ∈ F ( G) → f • ψ ∈ F (G)
is then an isomorphism of vector spaces and we have

∀ f ∈ F ( G), E(f ) = E(f • ψ).
This relation can be used to translate the results obtained in [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] for G into corresponding ones for G.

Organization of forthcoming sections

Here we introduce the sequence of results that we are going to prove in this article, which will appear in the next five sections each devoted to one of the main propositions described below. It was mentioned in [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF], without much hint of a proof, that Conjecture 3 implies Conjecture 1. Our first task will be to provide all the overlooked arguments in Section 2, where we show that to prove Conjecture 1, it is sufficient to prove Conjecture 3 for irreducible generators L (i.e. generators L whose associated graph G is connected). More precisely, Proposition 5 Given an integer k ∈ N and a generator L, if Inequality (5) is true for L and k, then Inequality (2) is true for L and k with χ(k) = χ(k)/2.

In particular, we recover that Conjecture 1 is true with the constant χ(k) ≡ 1/2 independent of k ∈ N, if we restrict its assertion to the class of generators whose associated graph is acyclic.

The fact underlying the equality (Λ k ) k∈ N = (λ k ) k∈ N for generators whose associated graph is a tree, is that a minimizing subpartition A ∈ D k in (4) corresponds (at least generically) to the nodal domains of an eigenfunction associated to λ k . For a better understanding of Conjecture 3, it seems important to be able to verify whether a subpartition A ∈ D k (G) corresponds to the nodal domains of an eigenfunction. To get a result in this direction, we need to introduce some notions.

A k-subpartition A = (A 1 , . . . , A k ) ∈ D k is said to be handy if for any pair of distinct indices i, j in k we have ∂A i ∩ ∂A j ∩ V 3 = ∅, where V 3 is the set of vertices of G whose degree are at least 3. An eigenfunction of a generator L is said to be handy if the collection of its nodal domains constitutes a handy subpartition. Also, the generator L itself is said to be handy if any eigenvalue λ of multiplicity m admits m independent handy eigenfunctions. It is instructive to note that if none of the eigenfunctions of a generator L vanishes on V then L is clearly a handy generator (in particular the former property also implies that all eigenvalues have multiplicity one, since in an eigenspace of dimension 2 it is always possible to construct a function that vanishes on x, for any given x ∈ V ).

The residual set A 0 of a given subpartition A = (A 1 , . . . , A k ) ∈ D k , with k ∈ N , is defined as the complementary set of the union of the closures of A i 's, for i ∈ k . The subpartition A is said to be a k-partition if its residual set A 0 is empty and for any x ∈ ∂A (when A is a subpartition, by convention its boundary is the union of the boundaries of its components), there exist i = j ∈ k such that x ∈ ∂A i ∩ ∂A j . We use P k (G) (or P k for short) to refer to the set of all such k-partitions.

The subpartition A = (A 1 , . . . , A k ) ∈ D k is said to be uniform if for any i = j ∈ k we have, λ 1 (A i ) = λ 1 (A j ), where this common value is denoted by λ 1 (A) (this is also the value of λ 1 (A 1 A 2 • • • A k ) if one directly uses the definition as expressed in (3)).

A pair of positive real numbers (r 1 , r 2 ) is said to be rectifying for a point a ∈ G with respect to (A

1 , A 2 ) ∈ D 2 if a ∈ ∂A 1 ∩ ∂A 2 , N (a) ∩ A 1 = {a -} and N (a) ∩ A 2 = {a + } such that r 1 f A1 (a -) φ A1 (a -, a) = r 2 f A2 (a + ) φ A2 (a + , a), (7)
where f A is defined as the minimizer of (3) 5 .

We say that the pair (r 1 , r 2 ) is rectifying for (A 1 , A 2 ) if it is rectifying for all points of the set ∂A 1 ∩ ∂A 2 . Also, a subpartition A ∈ D k , with k ∈ N , is said to be rectifiable, if there exists a family (r i ) i∈ k such that for any i = j ∈ k , (r i , r j ) is rectifying for (A i , A j ).

Finally, to a subpartition A = (A 1 , . . . , A k ) ∈ D k , we associate the graph G A whose vertex set is {A 1 , . . . , A k } and whose edge set consists of the {A i , A j },

with i = j ∈ k , such that ∂A i ∩ ∂A j = ∅. Then A is said to be bipartite if G A is a bipartite graph.
With all these definitions, we will show that, Proposition 6 Given k ∈ N , and a handy partition A ∈ P k , then this partition corresponds to the nodal domains of a handy eigenfunction of -L if and only if it is uniform, rectifiable and bipartite. This eigenfunction is then associated to the eigenvalue λ 1 (A).

Among the previous conditions, the rectifiability may seem to be the more difficult to check. That is why the Dirichlet connectivity spectrum (Λ k ) k∈ N is interesting, since its corresponding minimizing subpartitions provide rectifiable subpartitions. But there are other ways to find rectifiable subpartitions and one of them which will be fruitful for the study of Markov processes on cycles is the following. For k ∈ N define,

Λ k sup (A1,...,A k )∈P k min j∈ k λ 1 (A j )
There is no general comparison between Λ k and Λ k . But some relations can be deduced in special cases (see Proposition 17). Hereafter, we assume that G is connected, and we will prove that, Proposition 7 For k ∈ N , let A ∈ D k be either a minimizing subpartition for Λ k or a maximizing partition for Λ k . If A is handy, then A is a uniform and rectifiable partition in P k .

But there are some important differences between the optimizing subpartitions and partitions for Λ k and Λ k , respectively. It has been shown in [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] that a minimizer A ∈ D k for Λ k always exists and that it is possible to choose one which is uniform. However, the situation is not so nice for Λ k , since it may happen that there is no maximizing partition at all. In particular it is known that (see [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF]) if a minimizing subpartition for Λ k is a handy subpartition then it is actually a uniform partition in P k , and consequently, we only have to prove the rectifiability condition in the above proposition. Also, by Proposition 6, such a partition has all the required properties to correspond to the nodal domains of a handy eigenfunction of L, except being bipartite. In the continuous framework of Laplace-Beltrami operators in dimension 2, Helffer, Hoffmann-Ostenhof and Terracini [START_REF] Helffer | Nodal domains and spectral minimal partitions[END_REF] made a similar observation concerning the bipartiteness condition, under regularity and geometric requirements (in particular the nodal lines must intersect with equal angles).

In this article we focus on the case of handy subpartitions, and in order to be able to generalize our results to an arbitrary kernel we have to make sure that handy kernels are generic. More precisely, let the positive probability µ and the connected graph G = (V, E) be fixed. We denote by L(µ, G) the open and convex set of generators which are reversible with respect to µ and whose associated graph is G. We say that a property is generically true if it is satisfied for generators belonging to a dense subset of L(µ, G) (which is endowed with its natural pointwise topology). For instance we believe in the following assertions. The results of [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] and Proposition 17 imply that this conjecture is true if G is a tree. Note that the case k = N is not relevant, because, although, any partition in P N is necessarily handy, we will see in Section 5 that Λ N = +∞ if G is a cycle, and consequently, there is no maximizing partition A ∈ P N for Λ N in this case. If the above conjecture was to be true more generally, it would show that generically, only the bipartiteness condition is restrictive for a minimizing subpartition of Λ k or for a maximizing partition of Λ k to correspond to the nodal domains of a handy eigenvector of L.

Let us now come to the case of Markov processes on cycles. For them the graph G is isomorphic to the graph Z N endowed with its usual nearest neighbor structure. In this situation, every subpartition is handy and an interlacing property occurs, i.e. for k

∈ N -1 , we have Λ k ≤ Λ k < Λ k+1 ≤ Λ k+1 (see Proposition 17
). These features lead to the following properties for the spectral decomposition of L.

Proposition 9 When G is a cycle, we have,

∀ k ∈ N , λ k =        0 = Λ 1 = Λ 1 , if k = 1 Λ k , if k is even Λ k-1 , if k = 1 is odd
Moreover, for k ∈ N , k even, the eigenfunctions associated to λ k and to λ k+1 (if k + 1 ≤ N ) have exactly k nodal domains, so the equality λ k = λ k+1 is only possible for k even and it is equivalent to the equality

Λ k = Λ k .
In particular the multiplicities of the eigenvalues are less than or equal to 2.

As a consequence, the shape of eigenfunctions associated to generators on cycles can be easily described.

But more important for us, is the following result which proves Conjecture 3 when the graph G is a cycle, and consequently, one may deduce that all cycles admit a higher order Cheeger inequality for all of their eigenvalues with a universal constant 48.

Proposition 10 Assume that G is a cycle, then we have

∀ k ∈ N , Λ k ≤ λ k , if k = 1 or k is even 24 λ k , if k ≥ 3 is odd
Remark 11 While this paper was submitted for publication, we discovered from an article of Fernandes and Fosseca [START_REF] Fernandes | The inverse eigenvalue problem for Hermitian matrices whose graphs are cycles[END_REF] that the last assertion of Proposition 9 holds more generally for Hermitian matrices whose associated graph is a cycle. About the same time, we learned that variants of the notions of handiness and uniformity of partitions were also introduced (under the names of proper partitions and equipartitions) in a preprint by Band, Berkolaiko, Raz, and Smilansky [START_REF] Band | On the connection between the number of nodal domains on quantum graphs and the stability of graph partitions[END_REF], in order to study nodal deficiencies of quantum graphs. Despite the operators under study are not the same, they provided a criterion for partitions corresponding to nodal domains of eigenfunctions which shares some similarities with the one presented here, but it is rather based on the critical points of the mapping

P k A = (A 1 , . . . , A k ) → max i∈ k λ 1 (A i )
(see also Remark 21 below). In both articles the proofs are different.

On higher order Cheeger inequalities

Our main goal in this section is to prove the fact that to prove Conjecture 1, it is enough to prove Conjecture 3 for irreducible generators. For this, first we prove Proposition 5. The approach is based on a Cheeger-type lower bound on the principal Dirichlet eigenvalue, namely a relation between the latter and a Dirichlet isoperimetric constant, which seems interesting in itself.

More precisely for A ⊆ V, we define the isoperimetric constant inside A as

I(A) min B⊂A : B =∅ ι(B). (8)
The next result gives a "Dirichlet analogue" to the discrete "Neumann-oriented" Cheeger bound

I 2 2 2 |L| ≤ λ 2 .
Proposition 12 For any A ⊆ V, we have

I 2 (A) 2 |L| ≤ λ 1 (A).
To prove this proposition, let us introduce an L 1 -analogue E of the L 2 -Dirichlet form E as

∀ f ∈ F (V), E(f) {x,y}∈E |f(x) -f(y)| φ({x, y})
and recall the following lemma from [START_REF] Daneshgar | On the isoperimetric spectrum of graphs and its approximations[END_REF].

Lemma 13 [6, Lemma 4] For every 0 = f ∈ F (V) we have

E(f 2 ) µ[f 2 ] 2 ≤ 2 |L| E(f) µ[f 2 ] . (9)
Also, one may prove the co-area formula for I(A) as follows,

I(A) = min f∈F (A) f≥0,f =0 E(f) µ(f) . (10)
(e.g. it follows from [6, Lemma 5].) Now Proposition 12 follows immediately from Inequalities ( 9) and [START_REF] Kato | Perturbation theory for linear operators[END_REF]. Also, Proposition 5 follows immediately from the following corollary.

Corollary 14 For any reversible generator L given as in the introduction, we have

∀ k ∈ N , I 2 k 2 |L| ≤ Λ k . Proof For any C ⊆ V, define C {x,y}∈E x∈C [x, y) ⊆ G.
According to Proposition 12, for any A ∈ D 1 (G), we can find a non-empty set

B ⊂ A V ∩ A such that ι 2 (B) 2 |L| ≤ λ 1 (A) = λ 1 (A) ≤ λ 1 (A).
The last inequality follows from the facts that A ⊆ A and λ 1 is decreasing with respect to the set inclusion [12, Lemma 3]. It follows that for any k ∈ N and any

A = (A 1 , . . . , A k ) ∈ D k (G), we can find B = (B 1 , . . . , B k ) ∈ D k (G) such that (max i∈ k ι(B i )) 2 2 |L| ≤ max i∈ k λ 1 (A i ).
The announced bound follows at once.

In the rest of this section we focus on the case of reducible Markov generators and we show that as far as Conjectures 1 and 3 are concerned, one may confine oneself to the case of irreducible kernels whose base graphs are connected. Also, considering the reducibility condition, we will prove some relations between the parameters Λ k and Λ k in the special cases of trees, forests and cycles. We start with the following basic lemma.

Lemma 15 Let (a i ) i∈ n and (b i ) i∈ m be two non-decreasing families of numbers with a 1 = b 1 = 0. Denote by (c i ) i∈ n+m the non-decreasing ordering (with multiplicities) of the set {a

i : i ∈ n } ∪ {b i : i ∈ m } and define for all k ∈ 2, n + m , c k min l∈ n ∩ k-m,k-1 max(a l , b k-l ), c k max l∈ n ∩ k-m,k-1 min(a l , b k-l ).
with the convention c 1 = c 1 = 0. Then,

∀ k ∈ n + m c k ≤ c k = c k .

Proof

The equality

c 1 = c 1 = min(a 1 , b 1 ) = 0 is a direct consequence of our choice of c 1 . Fix k ∈ 2, n + m and without loss of generality assume that c k = a j with j ∈ n ∩ k -m, k -1 the smallest such index possible. Then, c k ≥ max({a 1 , . . . , a j } ∪ {b 1 , . . . , b k-j }),
and consequently, c k ≥ c k .

On the other hand, note that b k-j+1 ≥ c k , since otherwise, we would have max(a j-1 , b k-j+1 ) ≤ c k that contradicts our choice of j. Hence,

c k ≤ min{a j+1 , . . . , a n } = a j+1 and c k ≤ min{b k-j+1 , . . . , b m } = b k-j+1
which shows that c k ≤ c k , and we have c k = c k .

For the other inequality, let ã(t) and b(t) be the natural piecewise affine extensions of (a i ) i∈ n and (b i ) i∈ m as functions defined on real intervals [1, n] and [1, m], respectively. Then, for a fixed k ∈ 2, n + m we have the following two cases.

• If there exists a point u ∈ [max(1, k -m), min(n, k -1)] such that z ã(u) = b(k -u) then clearly we have c k ≤ z ≤ c k .
• Proposition 16 Conjecture 3 is true if it is true for finite irreducible Markov generators.

Proof

For i = 1, 2, let L (i) be Markov generators on finite sets V (i) , reversible with respect to some positive probability measures µ (i) . We denote by (λ

(i) k ) k∈ N (i) and (Λ (i) k ) k∈ N (i)
the corresponding usual and Dirichlet connectivity spectra, respectively. Consider V V (1) V (2) and let L be the generator that acts on V (i) as L (i) , for i = 1, 2. For a ∈ (0, 1), let µ = aµ (1) + (1 -a)µ (2) , and note that L is reversible with respect to µ. Also, define N N (1) + N (2) and let (λ k ) k∈ N and (Λ k ) k∈ N be the usual and Dirichlet connectivity spectra of L, respectively.

Without loss of generality assume that for a non-increasing sequence ( χ(k)) k∈N , we have

∀ i ∈ {1, 2} ∀ k ∈ N (i) , χ(k)Λ (i) k ≤ λ (i)
k . Since V (1) and V (2) are not linked by L, the spectrum of L is just the union of the spectra of L (1) and L (2) . It follows from Lemma 15 that

∀ k ∈ N , λ k = min l∈ N (1) ∩ k-N (2) ,k-1 max(λ (1) l , λ (2)
k-l ). ( 11
)
For k ∈ 2, N and l ∈ N (1) ∩ k -N (2) , k -1 , let A (1) ∈ D

(1) l be a minimizer for Λ

(1) l and also let

A (2) ∈ D (2)
k-l be a minimizer for Λ [START_REF] Bıyıkoglu | Laplacian eigenvectors of graphs[END_REF] k-l . Construct A ∈ D k as the disjoint union of A (1) and A (2) . It follows that

Λ k ≤ max(Λ (1) l , Λ (2) k-l ),
and taking the minimum over l ∈ N (1) ∩ k -N (2) , k -1 , we get

Λ k ≤ min l∈ N (1) ∩ k-N (2) ,k-1 max(Λ (1) l , Λ (2)
k-l ). [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] This along with [START_REF] Lawler | Bounds on the L 2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality[END_REF] and our assumptions show that

∀ k ∈ N , χ(k)Λ k ≤ λ k .
On the other hand, if there are more than two irreducible components, then by an iteration of the above argument we come to the same conclusion.

It is instructive to note that similarly one may show that Conjecture 1 is also true if it is proved for finite irreducible Markov generators.

In what follows we consider some basic inequalities that hold for the Dirichlet connectivity parameters introduced in the special cases of trees, forests and cycles.

Proposition 17 Let L be reversible generator on the graph G. We have,

a) If G is a cycle, then 0 = Λ 1 = Λ 1 , Λ N < Λ N = +∞ and for any k ∈ 2, N -1 , Λ k-1 < Λ k ≤ Λ k < Λ k+1 , b) If G is a tree, then for all k ∈ N we have λ k = Λ k = Λ k , c) If G is a forest, then for all k ∈ N we have λ k = Λ k ≥ Λ k .

Proof

Let G be a graph for which either there exists a minimizing uniform partition for Λ k or there exists a maximizing uniform partition for Λ k . Then,

Λ k = max i∈ k λ 1 (A i ) = min i∈ k λ 1 (A i ) ≤ Λ k .
For part (a), clearly 0 = Λ 1 = Λ 1 . Fix k ∈ 2, N -1 and note that by Proposition 7 handy minimizers of Λ k are uniform partitions. Since any subpartition of a cycle is handy, the inequality Λ k ≤ Λ k always holds for generators on cycles.

Also, given uniform partitions A = (A 1 , . . . , A k ) ∈ P k and B = (B 1 , . . . , B k+1 ) ∈ P k+1 , by applying the pigeonhole principle to the boundary points, there exists i ∈ k and j ∈ k + 1 such that B j is strictly included in A i . Let us recall Lemma 3 of [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] stating that if A, B ∈ D 1 with B strictly included in A, then λ 1 (A) < λ 1 (B). Therefore, by uniformity we get λ 1 (A) < λ 1 (B). Applying this with a minimizer for Λ k+1 and a maximizer for Λ k (its existence will be proved in Lemma 22 at the beginning of Section 5), we get Λ k < Λ k+1 .

To prove Λ N = +∞, consider the sequence of N -partitions (A (n) ) n∈N , where for any n ∈ N, ∂A (n) consists of the points (i + (2 + n) -1 ) i∈Z N . Then it is easy to verify that lim n→+∞ λ 1 (A (n) ) = +∞.

For part (b), the equality λ k = Λ k has already been proved in [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF]. On the other hand, assume that there exists a handy minimizer A = (A 1 , . . . , A k ) ∈ D k for Λ k . By Proposition 7, A is a uniform partition and consequently, we have Λ k ≤ Λ k by the argument presented in part (a).

To prove the reverse inequality, let B = (B 1 , . . . , B k ), be a given k-partition. Due to the fact that the underlying graph is a tree, G B is also a tree and it follows that |∂B| ≤ k -1. By the pigeonhole principle, there exists a component A i , i ∈ k , of the above minimizer A, that contains no point of ∂B. This means that there exists j ∈ k such that A i ⊂ B j , and we get min

l∈ k λ 1 (B l ) ≤ λ 1 (B j ) ≤ λ 1 (A i ) = λ 1 (A) = Λ k
since A is uniform. Thus, considering the supremum over B ∈ P k , it follows that Λ k ≤ Λ k , and consequently equality (b), holds if there exists a handy minimizer for Λ k .

But by Proposition 22 of [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF], minimizers of Λ k are generically handy for the tree G. Also, by a similar argument as one presented in Theorem 25 of [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] one may prove that Λ k and Λ k as real functions on the set L(µ, G) are continuous (i.e. with respect to the entries of the Markov generator). These two facts proves that equality (b) holds for all generators on trees.

For part (c), it is not difficult to see that a true equality always holds in [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF], and in a similar way, we get

Λ k = max l∈ N (1) ∩ k-N (2) ,k-1 min(Λ (1)
l , Λ

k-l ).

Hence, for any forest by Lemma 15 and part (b) we have

∀ k ∈ N , Λ k ≤ Λ k = λ k .

Remark 18

In what follows we discuss cases for which the inequalities of Proposition 17 are strict. To see this, using the situation and notations of the proof of Proposition 16 for a graph with two connected components, we have Λ k ≤ min{Λ

(1)

N (1) , Λ (2)
N (2) }, but by Lemma 15,

{Λ k : k ∈ N } = {Λ (1) k : k ∈ N (1) } ∪ {Λ (2) k : k ∈ N (2) }.
This shows that even the inequality max(Λ k , Λ k ) ≤ min(Λ k+1 , Λ k+1 ) can not be true in general. For instance, assume that one of the components is an empty graph with just one vertex and also let the other component be a tree, and note that for all k ∈ N we have Λ k = 0 while the parameter Λ k is nonzero for k ≥ 3. Moreover, the same example shows that the inequality Λ k ≤ Λ k can be strict for forests.

On the other hand, it is instructive to mention that if Conjecture 8 is true then by the first paragraph of the previous proof and the continuity of functions Λ k and Λ k on L(µ, G), one may deduce that the inequality Λ k ≤ Λ k is true for all irreducible generators.

Moreover, we would like to mention that the functions Λ k and Λ k are not necessarily continuous on the whole set of generators on a set V. To see this, consider the situation where N (1) = 1 and the graph of L (2) is a tree. Let V (1) = {x} and choose some vertex y in V (2) . For ≥ 0, let L( ) be deduced from L by imposing that L( )(x, y) = L( )(y, x) = and by leaving the other entries unchanged (except L( )(x, x) = L(x, x)and L( )(y, y) = L(y, y) -). Classical perturbation results (see for instance the book of Kato [START_REF] Kato | Perturbation theory for linear operators[END_REF]) imply that the usual spectrum (λ k ( )) k∈ N is continuous at = 0. Note that for > 0, the graph associated to L( ) is a tree and we have (Λ k ( )) k∈ N = (Λ k ( )) k∈ N = (λ k ( )) k∈ N . But due to the above considerations, Λ k = 0 for all k ∈ N . Thus, (Λ k ( )) k∈ N is not continuous at = 0, for k ≥ 3.

Characterization of handy spectral nodal domains

In this section we provide a proof of Proposition 6, as well as a criterium for the rectifiability of a given subpartition that will be useful to deduce Proposition 7.

Let g = 0 be an eigenfunction associated to an eigenvalue λ of -L, and let g be its affine extension to G with nodal domains A 1 , . . . , A k . Assume that A (A 1 , . . . , A k ) is a handy partition in P k . We show that it is uniform, rectifiable and bipartite.

First, note that Lemma 2 implies that for all i ∈ k , λ 1 (A i ) = λ, and consequently, A is uniform. To prove rectifiability and bipartiteness, for i ∈ k , define σ i ∈ {-1, +1} and choose r i > 0 such that g = σ i r i f Ai on A i . Let {A i , A j } be an edge in the graph G A defined before Proposition 6 and let a be a point in ∂A i ∩ ∂A j . By definition of the nodal domains, we have g(a) = 0 and σ i σ j = -1. It also follows that the couple (r i , r j ) is rectifying for a with respect to (A i , A j ) and since this is independent of the chosen a ∈ ∂A i ∩ ∂A j , (r i , r j ) is rectifying for (A i , A j ), and consequently, A is rectifiable by the family (r i ) i∈ k . It is also bipartite, because the edges of G A are only between the two independent sets {A i : i ∈ k with σ i = 1} and {A i : i ∈ k with σ i = -1}. This completes the proof of the direct implication in Proposition 6.

For the converse fix k ∈ N and assume that A (A 1 , . . . , A k ) ∈ P k is a handy, uniform, rectifiable and bipartite partition, and let (r i ) i∈ k be the corresponding rectifying family. Also, let (σ i ) i∈ k be a {-1, 1}-valued family, such that the graph G A is bipartite between the two parts {A i : i ∈ k with σ i = 1} and {A i : i ∈ k with σ i = -1}. We verify that g i∈ k σ i r i f Ai is an eigenvector of L associated to the eigenvalue -λ 1 (A). This will complete the proof of Proposition 6, since by bipartition, it is clear that up to a permutation of indices, A corresponds to the nodal domains of g.

Indeed, Lemma 2 implies that for any i ∈ k , by uniformity, on A i A i ∩ V we have,

L Ai [g] = σ i r i L Ai [f Ai ] = -λ 1 (A)σ i r i f Ai = -λ 1 (A)g.
Let a ∈ ∂A i ∩∂A j and first, assume that a ∈ V , which implies that [a -, a + ] is the unique edge in E containing a, where a -∈ A i and a + ∈ A j . Then, rectifiability and bipartiteness imply that

L(a -, a)g(a -) = L(a -, a + )(g(a -) -g(a + )).
This shows that L Ai [g] coincides with L[g] on A i . On the other hand, assume that a ∈ V , and note that by handiness [a -, a] and [a + , a] are the unique edges in E included in the closure of A i and A j , respectively. Thus, by rectifiability, bipartiteness and the fact that g(a) = 0, we have

L[g](a) = L(a, a -)g(a -) + L(a, a + )g(a + ) = 0 = -λ 1 (A)g(a)
. Now, since A ∈ P k , we conclude that L[g] = -λ 1 (A)g, as announced. This completes the proof of Proposition 6.

In the rest of this section we are going to present a convenient criterium for the rectifiability of a given subpartition A (A 1 , . . . , A k ) ∈ D k , for some k ∈ N . A finite family of points from the continuous graph G, (a j ) j∈ l , with l ∈ k , is said to be a necklace (with respect to A), if there exists a family (n j ) j∈ l of distinct indices from k such that for all j ∈ l , a j ∈ (∂A nj ∩ ∂A nj+1 ) (with the convention A n l+1 A n1 ). The necklace (a j ) j∈ l is said to be rectifiable, if we can find a family (r j ) j∈ l such that for all j ∈ l , (r j , r j+1 ) is rectifying for a j with respect to (A nj , A nj+1 ) (with the convention r l+1 r 1 ). The subpartition A itself is said to be necklace-rectifiable, if all its necklaces are rectifiable. Of course if A is rectifiable, then it is clearly necklace-rectifiable. The following lemma shows that the converse is also true.

Lemma 19 A subpartition A ∈ D k is rectifiable if and only if it is necklace-rectifiable.

Proof

Fix k ∈ N and let A (A 1 , . . . , A k ) ∈ D k be a necklace-rectifiable subpartition. We verify that this subpartition is also rectifiable. Let i = j ∈ k be such that {A i , A j } is an edge of G A and fix x ∈ ∂A i ∩ ∂A j . Let (r i , r j ) be a rectifying pair for x with respect to (A i , A j ) and consider x which is another point in ∂A i ∩ ∂A j . Then (x, x ) is a necklace for A (associated to the cycle A i → A j → A i of G A ) and the fact that it is rectifiable is equivalent to the statement that (r i , r j ) is also rectifying for x with respect to (A i , A j ), because all rectifying pairs are proportional. It follows that (r i , r j ) is rectifying for (A i , A j ).

Assume temporarily that G A is connected. We define a family (r i ) i∈ k in the following way. We arbitrarily choose r 1 = 1. Then, for i ∈ 2, k , let (n j ) j∈ l be a path going from 1 to i, i.e. n 1 = 1, n l = i, all its elements are distinct and for all j ∈ l -1 , {A nj , A nj+1 } is an edge of G A . Recursively, on j ∈ 2, l , we define r nj uniquely by imposing that (r nj-1 , r nj ) is rectifying for (A nj-1 , A nj ) (this can be done, according to the first part of this proof). We end up with a definition for r j and it is not difficult to check that the value obtained is not dependent on the choice of the path going from 1 to j, due to the fact that A is necklace-rectifying (consider all the cycles induced by the concatenation of two paths going from 1 to j, the second one in reverse order). Let us verify that for any edge {A i , A j } of G A , (r i , r j ) is rectifying for (A i , A j ). Indeed, this is a consequence of the above construction and of the fact that there exists a path (n m ) m∈ l starting from 1 and satisfying either n l-1 = i, n l = j or n l-1 = j, n l = i.

Note that if G A is not connected, it is sufficient to proceed as before separately on each of its connected components.

this necklace the quantity

C j∈ l f Aj (a - j ) φ(a - j , a j ) f Aj+1 (a + j ) φ(a + j , a j )
, where the meaning of the expressions φ and f Aj is recalled from the paragraph preceding Lemma 2 and a - j , a + j are defined to be the unique vertices in A j ∩ N (a j ) and A j+1 ∩ N (a j ), respectively (the indices are taken modulo l). Then we have Lemma 20 The necklace (a j ) j∈ l is rectifiable if and only if C = 1.

Proof

Assume that r j > 0 is given, for some j ∈ l -1 . The requirement that (r j , r j+1 ) is rectifying for a j with respect to (A j , A j+1 ) uniquely determines r j+1 . Indeed by definition it amounts to the equality

r j f Aj (a - j ) φ(a - j , a j ) = r j+1 f Aj+1 (a + j ) φ(a + j , a j ).
Starting from r 1 , we construct iteratively r 1 , . . . , r l . The only obstruction for (r j ) j∈ l to be rectifying for the necklace (a j ) j∈ l is that (r l , r 1 ) must be rectifying for a l with respect to (A l , A 1 ). Let r > 0 be such that (r l , r) is rectifying for a l with respect to (A l , A 1 ), according to the above computation we have r = Cr 1 . Hence, the equality r = r 1 is equivalent to C = 1.

Rectifiability of optimizers for Λ k and Λ k

Our goal here is to prove Proposition 7, which indicates two ways to produce rectifiable subpartitions.

We begin with the case of a minimizing handy subpartition A = (A 1 , . . . , A k ) ∈ D k for Λ k , for some k ∈ N . Since G is assumed to be connected, by results of [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] and the hypothesis we know that A is a uniform k-partition. Indeed, the argument behind this fact is simple, because if A is not uniform, then it is possible (due to the fact that all boundary vertices have degree two) to enlarge infinitesimally such A i 's such that λ 1 (A i ) = max j∈ k λ 1 (A j ) and to move the other ones appropriately to produce a better partition, which contradicts the minimality of A (see [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF]). The same idea can be applied to prove that any handy maximizer partition A ∈ P k for Λ k is uniform.

Therefore, it remains to prove the rectifiability of handy optimizers. We will use Lemmas 19 and 20 to prove that any handy minimizer for Λ k is rectifiable. The same arguments can prove the assertion for handy maximizers of Λ k .

Thus, let (a j ) j∈ l , with l ∈ k be a necklace. We adopt again the notations of the previous section, in particular that the necklace induces the cycle

A 1 → A 2 → • • • → A l → A 1 in G A and a j ∈ ∂A j ∩ ∂A j+1 , for j ∈ l . We want to show that C = 1. ( 13
)
The basic idea of the proof is to perturb infinitesimally the positions of the boundary points (a j ) j∈ l and to take advantage of the minimizing property of A. For this let (t j ) j∈ l be a family of positive real numbers and a small enough number > 0. For j ∈ l , we consider a j ( ) ∈ [a j , a + j ] such that d([a j ( ), a + j ]) = d([a j , a + j ])-t j . Hence, for small enough, one may define the subpartition A ( ) = (A ( ) 1 , . . . , A ( ) k ) ∈ D k which is similar to A, except the boundary points (a j ) j∈ l have been moved to the points (a j ( )) j∈ l (in particular we have

A ( ) j = A j , for j ∈ l + 1, k ).
Now, we want to evaluate the infinitesimal influence of this perturbation on the principal Dirichlet eigenvalues. For this, fix the arbitrary family of positive real numbers (r j ) j∈ l and define the function

f ( ) j ∈ F 0 (A ( ) j ) for each j ∈ l , such that it concides with f Aj on the vertices in A j ∩ V , f ( ) j (a j ) r j , vanishes outside of A ( ) j
and is affinely extended on A ( ) j . Then, for all j ∈ l we have (indices are taken modulo l)

E(f ( ) j ) = E(f Aj ) + f 2 Aj (a + j-1 ) t j-1 d([a + j-1 , a j-1 ]) -t j-1 φ(a + j-1 , a j-1 ) + f Aj (a - j ) -r j 2 φ(a - j , a j ) + (r j ) 2 d([a + j , a j ]) t j φ(a + j , a j ) -f Aj (a - j ) 2 φ(a - j , a j ). Thus ∂ ∂ E(f ( ) j ) =0 = t j-1 f 2 Aj (a + j-1 ) φ(a + j-1 , a j-1 ) d([a + j-1 , a j-1 ]) -2r j f Aj (a - j ) φ(a - j , a j ) + r 2 j t j φ(a + j , a j )d([a + j , a j ]).
Now, for the arbitrary family of positive real numbers (s j ) j∈ l let

t j s j d([a + j , a j ]) φ(a + j , a j ), r j s j f Aj (a - j ) φ(a - j , a j ).
Hence,

∂ ∂ E(f ( ) j ) =0 = s j-1 f 2 Aj (a + j-1 ) φ 2 (a + j-1 , a j-1 ) -s j f 2 Aj (a - j ) φ 2 (a - j , a j ).
If C = 1, we can assume that C > 1 (otherwise consider the reverse necklace (a l+1-j ) j∈ l ). Take s 1 1 and define iteratively for j ∈ 2, l ,

s j s j-1 f Aj (a + j-1 ) φ(a + j-1 , a j-1 ) f Aj (a - j ) φ(a - j , a j ) 2 C 2 l .
These are compatible modulo l, since

s l+1 = s 1 j∈ l f Aj+1 (a + j ) φ(a + j , a j ) f Aj (a - j ) φ(a - j , a j ) 2 C 2 = s 1 ,
and consequently we end up with

∀ j ∈ l , ∂ ∂ E(f ( ) j ) µ[(f ( ) j ) 2 ] =0 = ∂ ∂ E(f ( ) j ) =0 1 µ[f 2 Aj ] < 0.
Thus, for > 0 small enough, we get

max j∈ l+1 λ 1 (A ( ) j ) < max j∈ l+1 λ 1 (A j ).
Since λ 1 (A ( ) j ) = λ 1 (A j ) for j ∈ l + 1, k , it follows that the subpartition A ( ) is a minimizer for Λ k (in particular to avoid an immediate contradiction, we must have l + 1 ≤ k). But, note that this minimizing subpartition is still handy, and by Proposition 7 of [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF], it must be uniform. This is not the case and we conclude that indeed C = 1.

Thus we have shown that if the handy subpartition A is minimizing for Λ k , then its necklaces are rectifiable according to Lemma 20. Now, Lemma 19 implies that A is rectifiable. This ends the proof of Proposition 7.

Remark 21 If Conjecture 8 is true, it appears that generically, for any k ∈ N , there is two ways of generating a handy, uniform and rectifiable k-partition. One is by looking for a minimizer of the mapping

P k A = (A 1 , . . . , A k ) → max i∈ k λ 1 (A i )
and the other one is by looking for a maximizer of the mapping

P k A = (A 1 , . . . , A k ) → min i∈ k λ 1 (A i ).
It would had been more satisfying if we could have played with only one mapping. More precisely, endow P k with a differential structure (which is the gluing of several differential manifolds with boundaries, whose dimensions can be computed from the acceptable infinitesimal increasing and decreasing simultaneous moves of the boundaries of the elements of the partition at hand). We are wondering if there exists a "natural" mapping from P k to R whose critical points are (generically) handy, uniform and rectifiable partitions. The first candidates which come in mind are the mappings

L p,k : P k A = (A 1 , . . . , A k ) → 1 k i∈ k λ p 1 (A i )
where k ∈ N and p ∈ [1, +∞). A careful look at the above arguments shows that if a partition A is handy and is also a critical point for one of the above mappings L p,k (even with p ∈ R \ {0}), then A is uniform and rectifiable (the proof of Proposition 7 of [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] is also valid for such critical partitions).

In the case of the usual 2-dimensional Laplacian on some rectangles or on the equilateral triangle, Helffer and Hoffmann-Ostenhof [START_REF] Helffer | On spectral minimal partitions: the case of the sphere[END_REF] have shown that the minimizers of the mapping L 1,k (respectively for k = 3 and k = 2) are not uniform. This is not really contradictory with the above assertions, because the symmetries of their examples suggest that they are typically not working with what we would call a generical situation.

Despite its obvious interest, the investigation of the properties of the mappings L p,k are outside the scope of the present paper.

Spectral decomposition of cycles

As announced before, in this section we restrict our attention to reversible generators whose underlying graph is a cycle. Our main goal is to prove Proposition 9.

For this let L be a given generator, reversible with respect to a positive probability µ and whose underlying graph G is a cycle, that in what follows is identified with the usual nearest neighbors graph structure of Z N . The continuous graph G can be seen as the cycle of length N obtained by identifying the points 0 and N of the segment [0, N ].

First step toward Proposition 9 is to check that a maximizer does exist for the quantity Λ k , for all k ∈ N -1 . Note that for the cycle Z N , by Proposition 17(a), we have Λ N = +∞. Also, note that the equality Λ N = +∞ does not hold in general. For instance, Λ N is finite for generators whose graph is a tree due to Proposition 17(b).

Lemma 22 For any k ∈ N -1 , there exists A = (A 1 , . . . , A k ) ∈ P k such that Λ k = min i∈ k λ 1 (A i ).

Proof

First note that due to Proposition 17(a), Λ k is finite for k ∈ N -1 . Let (A (n) ) n∈N be a sequence of elements of P k which is maximizing for Λ k , i.e.

lim n→∞ min i∈ k λ 1 (A (n) i ) = Λ k .
Taking into account the compactness of the Hausdorff topology on the set of compact subsets of R/(N Z), we can extract a subsequence of (∂A (n) ) n∈N (still denoted (∂A (n) ) n∈N for notational convenience) and a compact subset

B ⊂ G such that lim n→∞ ∂A (n) = B.
Necessarily, we have l card(B) ≤ k (and l ≥ k/2), and let A 1 , . . . , A l be the connected components of G \ B. The family A (A 1 , . . . , A l ) is covering, in the sense that G is the union of the closures of the A i , but A may not be a partition of P l , because some of its components may not intersect Z N . Indeed, consider A 1 , . . . , A l the subsets A i , with i ∈ l , which satisfy A i ∩ Z N = ∅. Denoting A = (A 1 , . . . , A l ), we have that A is an l -subpartition and

min i∈ l λ 1 (A i ) = Λ k .
This is a consequence of the fact that the mapping

G 2 (x, y) → λ 1 ((x, y)) ∈ R + {+∞}
is easily seen to be continuous (see for instance [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF]Lemma 6]), where in the rhs (x, y) is the interval of G obtained by going from x to y "anti-clockwise". By convention if (x, y) ∩ Z N = ∅, we let λ 1 ((x, y)) = +∞. Note that l = 0. This comes from the assumption k ≤ N -1, which implies that Z N ⊂ B and thus there exist i ∈ Z N and j ∈ l such that i ∈ A j . If A ∈ P l , let us show that we can find A ∈ P l with

min i∈ l λ 1 (A i ) ≥ min i∈ l λ 1 (A i ). (14)
Indeed, if A ∈ P l , necessarily l < l and A i , with i ∈ l , which have been removed from A to obtain A are of the form (x, x + 1) with x ∈ Z N . For ∈ (0, 1) small enough, we have for all such x,

λ 1 ((x, x + 1 + )) ≥ min i∈ l λ 1 (A i ),
because the lhs goes to infinity when goes to zero, this is a consequence of the above continuity property. Still for such x, consider the set (x+ , x+1+

), if x ∈ ∂A (remark that λ 1 ((x+ , x+1+ )) > λ 1 ((x, x+1+ ))) and (x, x + 1 +
), if x ∈ ∂A , and call these sets A l +1 , . . . , A l . Now, diminish a little the A i , with i ∈ l , so that they do not overlap with the above sets, to get the A i , for i ∈ l (one would have noticed that since [START_REF] Montenegro | Mathematical aspects of mixing times in Markov chains[END_REF]. If A was to belong to P l , we have in fact A = A and l = l. In this case, just take A A. Now, we will modify A to obtain A ∈ P k such that

A i ⊂ A i , we have λ 1 (A i ) ≥ λ 1 (A i )). The l-partition A (A 1 , . . . , A l ) satisfies
min i∈ k λ 1 (A i ) ≥ min i∈ l λ 1 (A i ). ( 15
)
It will follow that

min i∈ k λ 1 (A i ) ≥ Λ k
and thus A will be the wanted maximizer. If l = k, there is nothing to do, we just take A A . Otherwise, namely if l < k, first consider the case where ∂A ∩ Z N = ∅ and choose x ∈ ∂A ∩ Z N . We create a new component (x -, x + ), with ∈ (0, 1) small enough so that

λ 1 ((x -, x + )) > min i∈ l λ 1 (A i ).
In the same time we diminish a little the A i which admit x as boundary point. We get a (l + 1)-partition whose minimal principal Dirichlet eigenvalue is not less than min i∈ l λ 1 (A i ). If l + 1 < k and if this (l + 1)partition still admits a boundary point in Z N , we start again the above procedure. Repeating such kind of transformations, we end up with a m-partition A with

min i∈ m λ 1 ( A i ) ≥ min i∈ l λ 1 (A i ), such that either m = k or ∂ A ∩ Z N = ∅.
In the first case, we just take A A. Otherwise there exists i ∈ m such that A i contains two consecutive points of Z N (because m < k ≤ N -1). Then we cut A i at the middle of the edge separating the consecutive points, to get two elements of D 1 , whose principal Dirichlet eigenvalues are larger than λ 1 ( A i ). Replacing A i by these two subsets, we get a (m + 1)-partition whose minimal principal Dirichlet eigenvalue is not less than min i∈ m λ 1 ( A i ). By repeating this procedure, we end up with a k-partition A satisfying (15).

Remark 23

The existence of a maximizer for Λ k , for k ∈ N -1 , is not true in general. Consider the generator on 4 whose matrix is given by

    -4 1 1 2 1 -1 0 0 1 0 -1 0 2 0 0 -2    
A maximizer for Λ 2 would be ([2, 1), [START_REF] Band | On the connection between the number of nodal domains on quantum graphs and the stability of graph partitions[END_REF][START_REF] Chen | Eigenvalues, inequalities, and ergodic theory[END_REF]∪ [START_REF] Band | On the connection between the number of nodal domains on quantum graphs and the stability of graph partitions[END_REF][START_REF] Chen | Speed of stability for birth-death processes[END_REF]) (also ([3, 1), [START_REF] Band | On the connection between the number of nodal domains on quantum graphs and the stability of graph partitions[END_REF][START_REF] Bıyıkoglu | Laplacian eigenvectors of graphs[END_REF]∪ [START_REF] Band | On the connection between the number of nodal domains on quantum graphs and the stability of graph partitions[END_REF][START_REF] Chen | Speed of stability for birth-death processes[END_REF]) and the partition ([4, 1), [2, 1]∪ [START_REF] Band | On the connection between the number of nodal domains on quantum graphs and the stability of graph partitions[END_REF][START_REF] Chen | Eigenvalues, inequalities, and ergodic theory[END_REF]) would provide a non-uniform maximizer), unfortunately the second component is not open, contrary to our requirements. A maximizing sequence (A (n) ) n∈N can be constructed, by imposing that for all n ∈ N, ∂A (n) = {x n }, where (x n ) n∈N is a sequence of points from (2, 1) (or from (3, 1)) converging to 1. Note that ([2, 1), [START_REF] Chen | Eigenvalues, inequalities, and ergodic theory[END_REF][START_REF] Band | On the connection between the number of nodal domains on quantum graphs and the stability of graph partitions[END_REF]) is a minimizing subpartition for Λ 2 and we recover that Λ 2 = Λ 2 (=1 here) for trees, as it was proved in Proposition 17. Heuristically speaking, this example is typically not "generical", due to the identity L(1, 2) = L(1, 3).

Next step is to prove that actually the parameters Λ k , k ∈ N and Λ k , k ∈ N -1 are eigenvalues of -L when k is even.

Proposition 24 Let k ∈ N be an even integer. Then, Λ k is an eigenvalue of -L and also if k = N , Λ k is also an eigenvalue of -L.

Proof

Due to the fact that the degree of the vertices of Z N is two, all subpartitions are handy. Thus, for k ∈ N , Proposition 7 implies that a minimizer A for Λ k as well as a maximizer B for Λ k (provided k = N ) are necessarily uniform and rectifiable k-partitions. If furthermore k is even, it appears that A and B are also bipartite. Then, Proposition 6 yields that Λ k = λ 1 (A) and Λ k = λ 1 (B) are eigenvalues of -L.

Proposition 24 shows that the spectrum of -L is given by Λ 1 = 0, (Λ k ) k∈ 2,N ,k even and (Λ k ) k∈ 2,N -1 ,k even , if all these values are distinct. Indeed, if N is even, we get 1 + N/2 + N/2 -1 = N values, while if N is odd, we obtain 1 + (N -1)/2 + (N -1)/2 values. So if for all k ∈ 2, N -1 , k even, Λ k = Λ k , by Proposition 17(a) and 24 we deduce that the spectrum of -L is as described in Proposition 9. The general case will be an immediate consequence of the following result.

Proposition 25 Let k ∈ 2, N -1 , k even, be given and assume that Λ k = Λ k . Then the eigenvalue Λ k of -L has multiplicity 2 and the associated eigenvectors have exactly k nodal domains.

Proof

Let A = (A 1 , . . . , A k ) ∈ P k be a minimizer for Λ k , with k as in the proposition. We adopt the convention that

A 1 = (b 1 , b 2 ), A 2 = (b 2 , b 3 ), . . . , A k = (b k , b 1 )
, where the boundary points satisfy 0

≤ b 1 < b 2 < • • • < b k < N in G = R/(N Z) identified with [0, N ).
First, assume that one of A i , with i ∈ k , contains two elements of Z N . Up to a shift of indices, we can assume that 1, 2 ∈ A 1 . Let y 1 ∈ (1, 2) be given and consider the mapping

F : (0, N ) s → λ 1 ((y 1 , y 1 + s)) ∈ R + {+∞}
(where y + s has to be interpreted as a point of G = R/(N Z)). We have F (s) = +∞ for s ∈ (0, 2 -y 1 ], but on the interval [2 -y 1 , N ), F is (strictly) decreasing. Since y 1 ∈ A 1 , we have (y 1 , b 2 ) ⊂ A 1 and A 2 ⊂ (y 1 , b 3 ) and these inclusions are strict. Thus there exists a unique point y 2 ∈ A 2 such that λ 1 (y 1 , y 2 ) = λ 1 (A). Iterating this procedure, we can find y 3 ∈ A 3 such that λ 1 (y 2 , y 3 ) = λ 1 (A) etc. We end up constructing y k ∈ A 1 such that λ 1 (y k-1 , y k ) = λ 1 (A). A priori there are three possibilities for this last point, either y k < y 1 , either y k = y 1 , or y k > y 1 . Let us show that the assumption Λ k = Λ k implies that y k = y 1 . First the case y k < y 1 is always impossible. Indeed, if we denote B i (y i , y i+1 ) for i ∈ k , then B (B 1 , . . . , B k ) is a minimizing subpartition for Λ k . According to Proposition 7, it should be a partition, but it is not the case, so we end up with a contradiction which implies that y k ≥ y 1 . Now, assume that y k > y 1 . It is then possible to transform the points y i , i ∈ k , into new points y i , i ∈ k , with y k = y 1 = y 1 , in such a way that if B (B 1 , . . . , B k ) is the partition for which ∂B = {y i : i ∈ k }, we get

∀ i ∈ k , λ 1 (B i ) > λ 1 ((y i , y i+1 ))
Indeed, in the covering R of G, this can be achieved by diminishing continuously the points y i , i ∈ 2, k , in a manner that the intervals beetween consecutive points have the same principal Dirichlet eigenvalue with respect to the periodization of the generator. When the point starting from y k reach y 1 , we get the points y i , i ∈ k . We deduce that

Λ k ≥ min i∈ k λ 1 (B i ) > min i∈ k λ 1 ((y i , y i+1 )) = λ 1 (A) = Λ k
which is in contradiction with our main assumption. Thus, as announced, y k = y 1 and the partition B, defined by B i (y i , y i+1 ) for i ∈ k , is minimizing for Λ k . According to Proposition 6, there exists an eigenfunction f associated to the eigenvalue -Λ k = -Λ k of L whose nodal domains are given by the elements of B. Similarly, there exists an eigenfunction g associated to the eigenvalue -Λ k whose nodal domains are given by the elements of A. Let us check that f and g are not proportional. This comes from the choice of y 1 , which insures that g has the same sign on the vertices 1 and 2, while f has opposite sign on these points. Thus, the equality Λ k = Λ k implies that the dimension of the eigenspace of -L associated with Λ k is at least 2. It cannot be strictly larger than 2, or otherwise we would end up with too much independent eigenfunctions. Indeed, here is the counting, taking into account Proposition 17(a) to insure we are not counting twice the same eigenvalue. First, Λ 1 = 0 is an eigenvalue of multiplicity one and for any l ∈ 2, N , l even, if Λ l = Λ l , we get two different eigenvalues of multiplicity 1 (except if N is even and l = N , then only Λ N is an eigenvalue, of multiplicity 1) and if Λ l = Λ l , we get one eigenvalue of multiplicity 2. Whatever N is (odd or even), this produces N eigenvalues (with multiplicities).

It remains to check the assertion about the nodal domains of any arbitrary eigenfunction f associated to Λ k , when Λ k = Λ k with k even. Let l be the number of nodal domains of f and let B be the l-subpartition consisting of these domains. First, we show that f cannot vanish on two consecutive vertices. Let x ∈ Z N be such that f(x) = 0, then the equality 0 = Λ k f (x) = -L[f ](x) implies that f(x -1) and f(x + 1) must have different signs and in particular none of them can vanish or both of them vanish. But in the latter case, the relation 0 = Λ k f (x + 1) = -L[f ](x + 1) would lead to f (x + 2) = 0 and by iteration we would end up with the contradiction f = 0. As a consequence B is a partition and l is even. Note also that B is uniform and λ 1 (B) = Λ k . Necessarily l = k, because otherwise, via the pigeonhole principle, we would end up with the conclusion that one element of B is strictly included into one element of A (case l > k) or one element of A is strictly included into one element of B (case l < k), facts in contradiction with λ 1 (B) = λ 1 (A). It appears also that the construction given at the beginning of this proof gives all the eigenvectors associated to Λ k , up to a factor, by letting y 1 wander inside [b 1 , b 2 ).

Let us give some precisions about the sentence following Proposition 9. We have seen in [START_REF] Miclo | On eigenfunctions of Markov processes on trees[END_REF] that the first Dirichlet eigenvector f A ≥ 0 associated to a segment A (path), with absorption only at the ends of the segment, has the following shape. Starting from zero at the lhs absorbing point, it increases until it reaches the highest value of f A , maybe it stays at the same value at the next vertex, but after it decreases until reaching zero at the rhs absorbing point. The construction considered in the above proof then enables to see that any eigenvector f associated to Λ k or Λ k , with k ∈ 2, N even, has the following shape. It is a succession of increasing phases and decreasing phases and between each of them, f attains its local minima or maxima in one vertex or two consecutive vertices. There are exactly k/2 increasing (respectively decreasing) phases and during each of them, f cross zero (either at a true vertex of V or at a "virtual" point of G).

This behavior was well-known in the homogeneous case (namely for the generator L whose diagonal entries are either 1/2 or 0, depending if they correspond to nearest neighbors or not, on the discrete cycle Z N ), because then the eigenvectors are described as follows.

-the eigenvector 1 (always taking the value 1) is associated to the eigenvalue 0, -the eigenspace associated to the eigenvalue 1 -cos(2πk/N ), for k ∈ (N -1)/2 , is generated by the mappings Z N x → cos(2πkx/N ) and Z N x → sin(2πkx/N ), -if N is even, Z N x → cos(πx) is also an eigenvector, associated to the eigenvalue -1.

Thus there is a universal qualitative behavior for the eigenvectors of generators whose associated graph is a cycle, whether or not there are double eigenvalues (as in the homogeneous case).

Proof of Conjecture 3 for cycles

In this section we prove Proposition 10 which implies that Conjecture 3 and then Conjecture 1 (a generalized Cheeger inequality) are valid with a universal constant for all k ≥ 1 and all generators on cycles.

Fix k ∈ N odd (if k is even, there is nothing to prove, due to the equality Λ k = λ k of Proposition 9). Let A = (A 1 , . . . , A k ) ∈ P k be a minimizing partition for Λ k which is uniform and rectifiable. For such a partition, we adopt the same convention as before that A

1 = (b 1 , b 2 ), A 2 = (b 2 , b 3 ), . . . , A k = (b k , b 1 ), where the boundary points satisfy 0 ≤ b 1 < b 2 < • • • < b k < N , with G = R/(N Z) identified with [0, N ). It is also convenient to use periodic notations: b k+1 = b 1 , A 0 = A k , A k+1 = A 1 etc. The main step will consist in finding i ∈ k such that λ 1 (A i {b i+1 } A i+1 ) ≥ (1/24) λ 1 (A) (16)
Indeed, assuming this is true and, to simplify the notations, that i = k, consider the partition A (A 1 , . . . , A k-1 ) ∈ P k-1 given by

∀ l ∈ k -1 , A l A k {b 1 } A 1 , if l = 1 A l , if l ∈ 2, k -1 .
Taking into account Proposition 9, we get

(1/24) Λ k = (1/24) λ 1 (A) ≤ λ 1 (A 1 ) = min l∈ k-1 λ 1 (A l ) ≤ Λ k-1 = λ k .
To find the index i ∈ k such that ( 16) is satisfied, we need some preliminaries. First, we recall the following lemma from [START_REF] Chen | Speed of stability for birth-death processes[END_REF] about approximating the first Dirichlet eigenvalue of generators on paths (birthdead processes) with Dirichlet conditions at both ends of the path. For more on this and its relationships to Poincaré and weighted Hardy inequalities see [START_REF] Chen | Eigenvalues, inequalities, and ergodic theory[END_REF][START_REF] Chen | Speed of stability for birth-death processes[END_REF].

Lemma 26 [4, Corollary 7.8] Let (L, µ) be a reversible generator on a path G = (V, E) with state space V = {x 0 , . . . , x N +1 } and edge set E = {{x i , x i+1 } : 0 ≤ i ≤ N }. Also, let λ 1 λ 1 ({x 1 , . . . , x N }), then we have κ

-1 /4 ≤ λ 1 ≤ κ -1 , where κ -1 min 1≤n≤m≤N   n-1 i=0 1 φ i -1 + N i=m 1 φ i -1     m j=n µ(x j )   -1 , in which φ i φ({x i , x i+1 }) = µ(x i ) L(x i , x i+1 ), for 0 ≤ i ≤ N .
Let G be a continuous path and as in Section 1.1, define two measures µ and ρ on G as follows,

µ x∈V µ(x)δ x , ρ {x,y}∈E ρ x,y , (17)
where for each edge {x, y} ∈ E, ρ x,y d x,y /φ({x, y}), in which d x,y is the natural Lebesgue measure on [x, y]. Note that, one may think of ρ as a measure of resistance on the edges of G. Now, it is straightforward to generalize Lemma 26 to the continuous model as follows.

Lemma 27 Let G be a continuous path endowed with the reversible generator (L, µ). Then, for every interval

A (a, b) ⊂ G, we have (1/4) κ -1 (A) ≤ λ 1 (A) ≤ κ -1 (A), where
κ -1 (A) inf a<x≤y<b 1 ρ((a, x)) + 1 ρ((y, b)) 1 µ([x, y]) , (18)
where the measures µ, ρ are defined as in (17).

Proof

Assume that the infimum in (18) occurs for the points x 0 , y 0 ∈ G. To prove the lemma, it is enough to show that {x 0 , y 0 } ⊆ V (G) and apply Lemmas 2 and 26. By contradiction and without loss of generality assume that x 0 ∈ G\V (G). Then choose x 0 next to x 0 such that ρ(a, x 0 ) > ρ(a, x 0 ) and (x 0 , x 0 ) contains no vertices of V (G). Then µ([x 0 , y 0 ]) = µ([x 0 , y 0 ]) and hence We prove the bound (16) through the following 3 cases. and let π : V (2) → V and σ : V (2) → {-1, +1} be the associated canonical projections. Also, for each x ∈ V define the index I(x) as follows.

1 ρ((a, x 0 )) + 1 ρ((y 0 , b)) 1 µ([x 0 , y 0 ]) < 1 ρ((a, x 0 )) + 1 ρ((y 0 , b)) 1 µ([x 0 , y 0 ]) ,
∀ x ∈ V, I(x) i if x ∈ A i , min{i, j} if x ∈ ∂A i ∩ ∂A j . Now, define the generator L (2) on V (2) as ∀ x, y ∈ V (2) , L (2) It can be verified that L (2) as defined in ( 19) is actually a double covering of L. At the level of processes, the intertwining relation L (2) • π = π • L implies that if (X

t ) t≥0 is a Markov process whose generator is L (2) , then (π(X (2) t )) t≥0 is a Markov process admitting L as its generator. The above relation also implies that the space of "even" functions (namely the functions on V (2) which can be written under the form f • π, where f is a function defined on V) is left stable by L (2) and that its restriction to this space can be put in conjugacy with L. In particular, the spectrum of L is included in the spectrum of L (2) .

Let G (2) be the continuous graph associated to the generator L (2) as in the introduction. The mapping π : V (2) → V admits a natural extension from G (2) to G, still denoted by π. It is straightforward to see that for any i ∈ k , π -1 (A i ) ⊂ G (2) consists of two connected components, one, say B 2i-1 is such that

B 2i-1 ∩ V (2) ⊂ {x ∈ V (2) : σ(x) = -1}
and the other one, say B 2i , satisfies B 2i ∩ V (2) ⊂ {x ∈ V (2) : σ(x) = +1}.

The sets B i , for i ∈ 2k , are clearly disjoint, open and connected, and by definition of L (2) , B (B i ) i∈ 2k is a handy 2k-partition of G (2) . In what follows, we prove that B is also bipartite, uniform and rectifiable, and consequently, the proof follows from Proposition 6.

As it was remarked in the definition of B, for any i ∈ k , the restriction of the mapping σ to B i ∩ V (2) is constant (with value (-1) i ). This leads to define the mapping Σ on the vertex set V(G B ) as Σ(B i ) = (-1) i which shows that G B is bipartite, with two parts {B ∈ V(G B ) : Σ(B) = -1} and {B ∈ V(G B ) : Σ(B) = +1}. Moreover, for i ∈ 2k , the operator L (2) Bi , defined on B i ∩ V (2) (as defined preceding Lemma 2) is just the operator L A i/2 defined on A i/2 ∩ V, if functions on A i/2 ∩ V are identified with functions on B i ∩ V (2) via the operator π. We deduce that λ 1 (B i ) = λ 1 (A i/2 ) and that B is uniform with λ 1 (B) = λ 1 (A).

For rectifiability, let (r i ) i∈ k be a rectifying family for A and consider the family (r

(2) i ) i∈ k given by ∀ i ∈ 2k , r (2)
i r (i+1)/2 .
Then it is easy to verify that Equality [START_REF] Fernandes | The inverse eigenvalue problem for Hermitian matrices whose graphs are cycles[END_REF] naturally lifts to the covering space G (2) and consequently, (r

i ) i∈ k is a rectifying family for B.

Remark 30

The above construction is valid for a general partition to give rise to a bipartite partition relatively to a double covering of the initial generator.

If Conjecture 8 was true, we could conclude that generically, for any k ∈ N there exists a double covering L (2) of L such that -Λ k is an eigenvalue of L (2) (and there exists another double covering of L which admits Λ k as an eigenvalue). If these double coverings exist, they depend on the value of k ∈ N , as it is the case for cycles. But in the following proposition, we will see that for the generator L on the cycle Z N , all parameters (-Λ k ) k∈ N and (-Λ k ) k∈ 2,N -1 appear in the spectrum of a double covering of L.

Proposition 31 Let L be a generator on the cycle Z N . Let L (2) be the unique irreducible double covering of L. Denote (Λ k ) its Dirichlet connectivity spectra. The ordinary spectrum of L (2) is given by

0 = Λ 1 < Λ (2) 2 ≤ Λ (2) 2 < Λ 2 ≤ Λ 2 < Λ 3 ≤ Λ 3 < . . . < Λ N -1 ≤ Λ N -1 < Λ N .

Conjecture 8

 8 If G is connected, and k ∈ N -1 , the following statements are generically true 6 . a) Any minimizing subpartition A ∈ D k for Λ k is handy. b) There exists a maximizing partition A ∈ P k for Λ k which is handy. c) Any generator L ∈ L(µ, G) is handy.

  Otherwise, on the interval [max(1, k -m), min(n, k -1)] we either have ã(t) ≤ b(t) or b(t) ≤ ã(t) which shows that c k ≤ c k . It should be noted that for all k ∈ n + m , we have c k ≤ min(a n , b m ), and consequently, all the elements of the set {a k : k ∈ n } ∪ {b k : k ∈ m } which are larger than min(a n , b m ) will not appear in the family (c k ) k∈ n+m .

  which is impossible. Now, let us come back to the minimizing partition A = (A 1 , . . . , A k ) ∈ P k for Λ k considered at the beginning of this section. For all i ∈ k , we denote by c i the unique middle point of A i , in the sense that ρ((b i , c i )) = ρ((c i , b i+1 )) = ρ(A i )/2. Consider the k-partition B (B 1 , . . . , B k ) such that ∀ i ∈ k , B i (c i , c i+1 ) (with the convention b k+1 = b 1 ). There exists at least one index i ∈ k such that λ 1 (B i ) ≥ Λ k = λ 1 (A).Indeed, otherwise we would getmax i∈ k λ 1 (B i ) < Λ kwhich would be in contradiction with the definition of Λ k . The next result shows that this index i is the one we were looking for.Proposition 28 The bound (16) is satisfied if i ∈ k is such that λ 1 (B i ) ≥ λ 1 (A).ProofWithout loss of generality assume that i = k, define A 1 A k {b 1 } A 1 and consider the same notations as beforeA 1 = (b 1 , b 2 ), A k = (b k , b 1 ), B k = (c k , c1). Let x 0 , y 0 ∈ A 1 be two points that minimize (18) achieving κ -1 (A 1 ). Thus κ -1 (A 1 ) = 1 ρ((b k , x 0 )) + 1 ρ((y 0 , b 2 )) 1 µ([x 0 , y 0 ]) .

Case 1 .

 1 ρ((b k , x 0 )) ≥ (3/5) ρ(A k ) and ρ((y 0 , b 2 )) ≥ (3/5) ρ(A 1 ). Then c k < x 0 < y 0 < c 1 and we compute thatρ((c k , x 0 )) = ρ((b k , x 0 )) -ρ(A k ) 2 ≥ ρ((b k , x 0 )) 6 Similarly ρ((y 0 , b 2 )) ≤ 6ρ((y 0 , c1)) and we deduce via Lemma 27 that λ 1 (A 1 )

Case 2 .

 2 ρ((b k , x 0 )) < (3/5) ρ(A k ) and ρ((y 0 , b 2 )) < (3/5) ρ(A 1 ). Choose the points d 1 , d 2 ∈ A 1 as the middle points of the intervals (c k , b 1 ) and (b 1 , c 1 ), respectively, i.e.ρ((ck , d 1 )) = ρ((d 1 , b 1 )) = (1/4) ρ(A k ), ρ((b 1 , d 2 )) = ρ((d 2 , c 1 )) = (1/4) ρ(A k ).Then, we have x 0 < d 1 < d 2 < y 0 and by Lemma 27 we haveλ 1 (A) ≤ κ -1 (A k ) ≤ 1 ρ((b k , x 0 )) + 1 ρ((d 1 , b 1 )) 1 µ([x 0 , d 1 ]) , λ 1 (A) ≤ κ -1 (B k ) ≤ 1 ρ((c k , d 1 )) + 1 ρ((d 2 , c 1 )) 1 µ([d 1 , d 2 ]) , λ 1 (A) ≤ κ -1 (A 1 ) ≤ 1 ρ((b 1 , d 2 )) + 1 ρ((y 0 , b 2 )) 1 µ([d 2 , y 0 ]).

  (x), π(y)) if I(π(x)) = I(π(y)) and σ(x) = σ(y), L(π(x), π(y)) if I(π(x)) = I(π(y)) and σ(x) = σ(y),

The finite graph context seems more convenient to approach this problem and if Conjecture 3 is true in its present form, then via usual approximation procedures, it will also be satisfied in a general Markov process framework encompassing diffusion generators.

Note that this graph structure is not a random walk graph but is just a graph that contains the information of positive entries of L. Moreover, note that φ as a measure on the set E also defines a flow on this graph.

It should be noted that recently the bound has been improved to χ(2) = 1 (see[START_REF] Montenegro | Mathematical aspects of mixing times in Markov chains[END_REF]).

This is defined by abuse of language in this article and is different from the standard definition of the discrete nodal domain (e.g. see[START_REF] Bıyıkoglu | Laplacian eigenvectors of graphs[END_REF]).

The concept of rectifiability can be generalized to the case where card(N (a) ∩ A1) > 1 or card(N (a) ∩ A2) > 1. However, this will not be of any use in the sequel, since we will be dealing with just handy subpartitions.

Actually, in both parts (a) and (b), we believe that generically all boundary points are in G\V .

Now, we quantify the rectifiability of a necklace. Hence, let (a j ) j∈ l , with l ∈ k , be a given necklace with respect to A ∈ D k . Up to a change of indices, we assume that a j ∈ ∂A j ∩ ∂A j+1 for j ∈ l . We associate to

Acknowledgments

We would like to thank Mehrdad Shahshahani and the hospitality of the School of Mathematics at the IPM, Tehran, where much of this work was done. We are also grateful to Bernard Helffer who pointed out to us the reference [1].

.

This along with Lemma 27 imply that

Again, let d 1 be the middle point of the interval (c k , b 1 ) and similar to Case 2, we have

.

Thus,

and the result follows.

Appendix: double coverings

In this appendix we present a spectral interpretation of parameters (Λ k ) k∈ N and (Λ k ) k∈ N via a double covering construction that helps to lift partitions to bipartite partitions on a covering space. In this regard, a generator L (2) on a set V (2) is said to be a double covering of L, if there exists a mapping π :

• any x ∈ V admits two pre-images by π,

• for any x ∈ V (2) , the restriction of π on

• for any x, y ∈ V (2) , either

The first two conditions shows that the graph G (2) associated to L (2) is a double covering of G in the usual graph theory sense and the third one (in conjunction with the second one) says that L (2) • π = π • L, where π is seen as acting on functions f ∈ F (V) through π[f ] = f • π. It should be noted that if L is reversible with respect to the invariant measure µ, then L (2) is also reversible with respect to the invariant measure µ (2) on V (2) defined as µ (2)

In what follows we prove that Proposition 29 Let A be a handy rectifiable and uniform partition. Then there exists a double covering L (2) of L such that -λ 1 (A) is an eigenvalue of L (2) .

Proof

For this fix k ∈ N and let A = (A 1 , . . . , A k ) ∈ P k be a handy, rectifiable and uniform partition. Now, we construct a double covering L (2) of the underlying generator L such that λ 1 (A) is an eigenvalue of L (2) . We define

Moreover, we have

Proof

Let k ∈ N be an integer and A = (A 1 , . . . , A k ) ∈ P k be a minimizing partition for Λ k and consider the double covering L (2) defined as in (19). Note that in general this construction strongly depends on the partition A, however, in the case of a cycle, up to an isomorphism, the generator L (2) only depends on the parity of k, i.e. if k is odd, L (2) is L (2) , the periodic doubling of L on Z 2N introduced in the statement of the above proposition, and if k is even, L (2) just acts as L on two disconnected copies of V = Z N . Now, for k ∈ 3, N an odd integer Propositions 7 and 29 imply that -Λ k is an eigenvalue of L (2) . Also, since the double covering for an odd k is independent of k, the spectrum of L (2) contains -Λ k and -Λ k for every odd k ∈ 3, N . Furthermore, since the spectrum of L is included in the spectrum of L (2) , the parameters -Λ 1 = 0 and -Λ k and -Λ k for even k ∈ 2, N (except -Λ N ) also appear in the spectrum of L (2) . On the other hand, the same arguments as those used in the proof of Proposition 25 give rise to the fact that if -Λ k = -Λ k , this eigenvalue has multiplicity at least two for L (2) . Hence, the spectrum of L (2) contains (with multiplicity) both Dirichlet connectivity spectra (Λ k ) k∈ N and (Λ k ) k∈ 2,N -1 . Only two eigenvalues are missing in this description, Λ

(2) 2 and Λ

(2) 2 , namely those admitting eigenfunctions with two nodal domains. Therefore, the first statement follows from Proposition 17. Moreover, the last statement follows from Proposition 9 applied to L (2) .

Clearly to get a spectral interpretation of Λ