Ément Cl

Rau

EXISTENCE OF GRAPHS WITH SUB EXPONENTIAL TRANSITIONS PROBABILITY DECAY AND APPLICATIONS

).

In the second part, we give an application of the existence of such graphs. We obtain bounds of the correct order for some functional of the local time of a simple random walk on an infinite cluster on the percolation model. Contents 1. Introduction and results 1 1.1. Example of application of proposition 1.2. 2 2. Proof of proposition 1.2 3 2.1. Wreath products and explanation of our method 3 2.2. case 1 3 ≤ α < 1 4 2.3. case 0 ≤ α ≤ 1 3 16 2.4. Complement on satisfactory points 23 3. Applications: study of some functionals 30 3.1. Kind of problems, case of the lattice Z d 30 3.2. In an infinite cluster of the percolation model 30 References 46

Introduction and results

A graph G is a couple (V (G), E(G)), where V (G) stands for the set of vertices of G et E(G) stands for the set of edges of G. All graphs G which are considered here are infinite and have bounded geometry and we denote by ν(g) the number of neighbors of g in G.

We study the following random walk X on G defined by:

X 0 = g, P(X n+1 = b|X n = a) = 1 ν(a)+1 (1 {(a,b)∈E(G)} + 1 {a=b} ) (1)
The random walk X jumps uniformly on the set of points formed by the point where the walker is and his neighbors. Thus X admits reversible measures which are proportionnal to m(x) = ν(x) + 1.

In this context, the transition probabilties are linked by the isoperimetric profile. For a graph G and for a subset A of G, we introduce the boundary of A relatively to graph G defined by

∂ G A = {(x, y) ∈ E(G); x ∈ A et y ∈ V (G) -A}.
Actually, we will rather work with Følner function to deal with isoperimetry. Let G be a graph, we note F ol G the Følner function of G defined by:

F ol G (k) = min{|U |; U ⊂ V (G) et |∂ G U | |U | ≤ 1 k }.
If G ′ ⊂ G is a subgraph of G, we will use the Folner function of G ′ relatively to G defined by:

F ol G G ′ (k) = min{|U |; U ⊂ V (G) et |∂ G U | |U | ≤ 1 k }.
We have the following proposition (see coulhon [START_REF] Coulhon | Ultracontractivity and Nash Type inequalities[END_REF])

Proposition 1.1. Let m 0 = inf V (U) m > 0 and X be the random walk defined by [START_REF] Coulhon | Ultracontractivity and Nash Type inequalities[END_REF]. Assume that F ol(n) ≥ F (n) with F a non negative and non decreasing function, then sup

x,y

P(X n = y|X 0 = x) v(n),
where v satisfies :

v ′ (t) = - v(t) 8(F -1 (4/v(t))) 2 , v(0) = 1/m 0 .
(We recall that a n b n if there exists constants c 1 and c 2 such that for all n ≥ 0, a n ≤ c 1 b c2n and a n ≈ b n if a n b n and a n b n .) For example, we retrieve that in Z d , the random walk X defined above has transitions decay at time n less than n -d/2 and in F 2 the Cayley graph of the free group with two elements, the transition decay of the random walk are less than e -n . A natural question is to know if there exists graphs with intermediate transitions decay. Some others motivations can be found in section 3.

From Z, one can perhaps adjust some weigths on edges to get the expected decay but we look after a graph with no weigths.Indeed, there are combinatorics arguments in section 3 that will not work if any weigths are present.

Our main result is :

Proposition 1.2. Let α ∈ [0; 1[, F := e x 2α
1-α and σ(n) := e -n α . There exists a graph D F = (V (D F ), E(D F )) with bounded valency such that : (i) F ol DF ≈ F , (ii) there exists a point d 0 ∈ V (D F ) such that, for all n, p DF n (d 0 , d 0 ) ≈ σ(n), where p DF n ( , ) stands for the transitions probability of the random walk X defined above when G = D F .

1.1. Example of application of proposition 1.2. With the help of these graphs and with some good wreath products, we will be able to find upper bound of functional of type:

E(e -λ F (Lx,n,x) ) where L x,n = #{k ∈ [0; n]; X k = x} on the graph C g get after a surcritical percolation on edges of Z d , where edges are kept or removed with respect Bernouilli independant variables. The points of C g are the point of the infinite connected component C which contains the origin, we will give more details in section 3. In particular, we will prove the following property: Theorem 1.3. Consider a simple random walk X on the infinite cluster of Z d that contains the origin Q a.s on the set |C| = +∞, and for large enough n we have:

∀α ∈ [0, 1] E ω 0 (e -λ z;Lz;n>0 L α z;n 1 {Xn=0} ) ≈ e -n η , (2) ∀α > 1/2 E ω 0 ( z;Lz;n>0 L -α z;n 1 {Xn=0} ) ≈ e -n d d+2 ln(n) 2 d+2 , (3)
where η = d+α (2-d) 2+d(1-α) . The constants present in the relation ≈ do not depend on the cluster ω.

Remark 1.4. If we take α = 0 in equation (2), we retrieve the Laplace transform of the number of visited points N n (see [6]),

E ω
0 (e -λNn ) ≈ e -n d/d+2 . In the whole article, C, c are constants which value can evolve from lines to lines.

Proof of proposition 1.2

In this section, we first recall the definition of the wreath product of two graphs and we explain our strategy aimed at the construction of our expected graphs. This leads naturally towards two cases corresponding to the two last subsections.

2.1. Wreath products and explanation of our method. Let A a graph and (B z ) z∈A a family of graphs. This graph can be interpreted as follow: imagine there is a lamp in each point a of A such that each point of B a defined a different intensity of the lamp. The different intensity of each lamp can be represented by a configuration f : A → ∪ a B a which encodes the intensity of the lamp at point a by the value f (a). A point in the wreath product is the couple formed by the position of a walker in graph A and the state of each lamp. A particular case is when the graph B a (called the fiber) is the same for all a ∈ A.

Let us now explain the way we construct graph D F of proposition 1.2. Consider the wreath product of the Cayley graph of (Z, +) by the Cayley graph of Z 2Z with 1 as generator. By the Theorem 1 in [START_REF] Ershler | On isoperimetric profiles of finitely generated groups[END_REF] (or Proposition 3.2.1 in [6]) we immediatly deduce that the Folner fonction of this wreath product is like e n . So this graph answers to proposition 1.2 in the case 2α 1-α = 1. ie : α = 1/3. In the case α = 1/3, it would be rather natural to think that we can get the expected graph, by considering the wreath product of Z by fibers with variable sizes.

• If α ≥ 1/3, the return probability in the graph D F should be in e -n α so less than in the graph Z ≀ Z 2Z ( in e -n 1/3 ) . Thus to force the walk to come back rarely at the origin, an idea is to make the size of the fibers grow when we move away the origin in order to force the walk to loose time in the fiber. Note that for α ≥ 1 condition (ii) is always satisfied (in a graph with bounded geometry).

• If α ≤ 1/3, the return probability in the graph D F should be larger than in e -n 1/3 . The idea is to add some links (some edges by example) to force the walk to come back often to the origin. Suppose all lamps are identified then we get a decay in n -1/2 and if all lamps are independent we get a decay in e -n 1/3 , so it remains to find an identification of lamps which implies an intermediate decay. We are going to construct a wreath product where the walker (at a certain point) is allowed to change the value of the configuration at differents points. Such graphs are sometimes called generalized wreath products.

To prove isoperimetric inequality on wreath product ( point (i) of the proposition 1.2) we use idea of Erschler and the concept of "satisfactory" points. We begin to introduce this notion in section 2.2. At the beginning of section 2.3, we explain why an improvement is needed in the definition of "satisfactory" points. The improvement takes place through the introduction of a new and more theoretical way of defining the notion of "satisfactory" points than in section 2.2. For simplicity, we use the same words for this concept in the two sections but notions which appear in sections 2.3 and 2.2 are independent.

case

(z) = |V (B ′ z )| = F (|z|+1) F (|z|) , (F is defined at proposition 1.2). Notice that since α ∈ [1/3, 1], the fonction z → l(z) is increasing on R + . Finally put D F = A ′ ≀ B ′ z .
Let us prove that this graph answers to propostion 1.2.

We begin by proving (i).

The proof is similar to the Theorem 1 in [START_REF] Ershler | On isoperimetric profiles of finitely generated groups[END_REF] or proposition 3.2.1 in [6].

Let ψ(n) = F ol A ′ (n) = min U⊂Z |∂ A ′ U | |U | ≤1/n |U | = 2n. Take U ⊂ V (D F ) = V (A ′ ≀ B ′ z ) such that |∂D F U| |U|
≤ 1/n for some n. We want to find a lower bound on |U |.

• For each set U , we attach an hypergraph K U = V (K U ), ξ(K U ) such that:

-the vertices of K U are the configurations f which belong to the set {f ; ∃a ∈ Z (a, f ) ∈ U }, -let us now define the edges of K U : for all f ∈ V (K U ) and a ∈ Z, we link f to all configurations g satisfying:

   (a, g) ∈ U and ∀x = a f (x) = g(x),
by a multidimensional edge l of dimension d where

d = dim a f := #{g; (a, g) ∈ U and ∀x = a f (x) = g(x)}.
We say that the edge l is associated to point a.

• To each hypergraph K U we associate a graph called the " one dimensional skeleton", noted by

Γ(K U ) = Γ U = (V (Γ U ), E(Γ U )
) and defined by: -

V (Γ U ) = V (K U ),
-two configurations f 1 and f 2 are linked by an edge if they belong to a same multidimensional edge in K U .

Let w be the weight defined by w(e) = 1/d for e belonging to E(Γ U ) and coming from a multidimensional edge in K U of dimension d. Notice that this choice of weights gives :

|U | ≥ 2 e∈E(ΓU ) w(e), (4)
and if we assume moreover that for all (x, f ) ∈ U, dim x f ≥ 1 (U has no separeted points) then the equality holds in 4 Let p be the projection Z ≀ B ′ z → Z. Let us now introduce some notations. Denote λ = (λ a ) a∈p(U) ∈ R p(U) and b ≥ 0.

• For f ∈ V (K U ), we say that f is (λ, b) -satisf actory if : #{a ∈ p(V ); dim a f ≥ λ a } ≥ b.
ie : f is (λ, b)satisf actory if there exists at least b multidimensional edges attached to f in K U of dimension at least λ a at point a. We denote by S U (λ, b) the set of these points. Most of the time, in order to simplify notations we will drop the subscript U when there is no ambiguity.

• Otherwise we tell that f is (λ, b)nonsatisf actory and we denote by N S(λ, b) the set of nonsatisfactory points.

• An edge of Γ U is (λ, b) -satisf actory if it links two (λ, b) -satisf actory con- figurations otherwise it is said (λ, b) -nonsatisf actory . We denote S e (λ, b) [resp N S e (λ, b)] the set of (λ, b) -satisf actory [resp (λ, b) -nonsatisf actory] edges. • A point u = (x, f ) ∈ U is (λ, b) -satisf actory [resp (λ, b) -nonsatisf actory] if f ∈ S(λ, b) [resp N S(λ, b)]. We denote by S p (λ, b) and N S p (λ, b) the set of points which are (or are not ) (λ, b) -satisf actory. • A point u = (a, f ) ∈ U is said b -good if dim a f ≥ b otherwise it is b -bad.
Let us now explain the main steps of the proof. We take U ⊂ V (D F ) such that

|∂D F U| |U| ≤ 1 n .
We begin to prove that there exists some value of b and some sequence λ such that there are few points (λ, b)nonsatisf actory. Then, we extract a subgraph of Γ U where all points are ( λ 30 , b 30 )satisf actory and this allows us to obtain a lower bound of |U |. We begin by the following lemma.

Lemma 2.2. Let U ∈ V (A ′ ≀ B ′ z ) such that |∂D F U| |U| ≤ 1 1000n then (i) #{u=(x,f )∈U; u is λx(n)-bad} #U ≤ 1 1000n (ii) #{u=(x,f )∈U; u∈N S p (λ(n)/3,ψ(n)/3) } #U ≤ 1 500 , where λ = (λ x ) x with λ x (n) = F ol B ′ x (n) and ψ(n) = F ol A ′ (n). Proof.
For (i) we notice that we can associate to certain bad points, some point of the boundary of U . Indeed, for (x, f ) a point, we call: Px,f = {g(x); (x, g) ∈ U and ∀y = x g(y) = f (y)} and

P x,f = {(x, g); g(x) ∈ Px,f } . Note that | Px,f | = |P x,f |. F 0 stands for a set of configurations such that: ˙ x∈A ′ ,f ∈F0 P x,f = {u = (x, g) ∈ U ; u is F ol B ′ x (n) -bad}.
Take note that, for a point u = (x, f ) which is F ol B ′ x (n)bad, by the definition of a Folner function, we have:

| Px,f | < F ol B ′ x (n). So, |∂ Bx Px,f | ≥ 1 n | Px,f | Now the application ˙ x∈A ′ ,f ∈F0 ∂ Bx Px,f -→ ∂ DF U is injective, (g 1 , g 2 ) → (x, f x,g1 ), (x, f x,g2 ) where (g 1 , g 2 ) ∈ ∂ Bx Px,f and f a,h : v → f (v) for v = a. a → h
Hence, we have :

|U | 1000n ≥ |∂ DF U | ≥ x∈A,f ∈F0 |∂ B Px,f | ≥ 1 n x∈A,f ∈F0 | Px,f | = 1 n #{u = (a, f ) ∈ U ; u is F ol B ′ a (n) -bad}.
For (ii), the proof splits into three parts.

A. Let,

N eud = {u ∈ U ; u ∈ N S p ( λ 3 , F ol A ′ (n) 3 ) } = {u = (x, f ) ∈ U ; f ∈ N S( λ 3 , F ol A ′ (n) 3 )},
and let:

N eud(f ) = {(x, f ); (x, f ) ∈ U }. Notice that p(N eud(f )) = {x; (x, f ) ∈ U }.
For F a set of configurations, we call

N eud(F ) = ∪ f ∈F N eud(f ).
Note well that it is a disjointed union.

B. Now take f ∈ N S( λ 3 , F ol A ′ (n) 3
), and look at the set p(N eud(f )). There are only two possibilties: -either, it gives a large part of boundary in 'base', -either, it gives a few part of boundary in 'base'. If this is the case, taking into account that f is not satisfactory, we retrieve boundary in 'configuration'. Anyway, we get some boundary of U , but our assumptions restrict this contribution.

So we differentiate two cases:

First case : f ∈ F 1 := {f ∈ N S( λ 3 , F ol A ′ (k) 3 ); #∂ A ′ p(N eud(f )) #p(N eud(f )) > 1 n }. The application ˙ f ∈F1 ∂ A ′ p(N eud(f )) -→ ∂ DF U is injective. (x, y) -→ (x, f ) ; (y, f )
So, we get:

(5)

|∂ DF U | ≥ f ∈F1 |∂ A ′ p(N eud(f ))| ≥ 1 n f ∈F1 |p(N eud(f ))| ≥ 1 n |N eud(F 1 )|. Second case : f ∈ F 2 := {f ∈ N S( λ 3 , F ol A ′ (n) 3 ); #∂ A ′ p(N eud(f )) #p(N eud(f )) ≤ 1 n }. Since f ∈ N S( λ 3 , F ol A ′ (n) 3
) it follows that :

#{x ∈ p(N eud(f )); dim x f ≥ λ x 3 } < 1 3 F ol A ′ (k).
Hence,

#{x ∈ p(N eud(f )); dim x f < λ x 3 } ≥ |N eud(f )| - 1 3 F ol A ′ (n) (We use that |p(N eud(f )| = |N eud(f )|.)
Since f ∈ F 2 and by definition of a Folner fonction:

|N eud(f )| ≥ F ol A ′ (n).
As a result, we have:

#{x ∈ p(N eud(f ); dim x f < λ x 3 } ≥ 2 3 |N eud(f )|. ie : |P f | ≥ 2 3 |N eud(f )|, ( 6
) with P f = {x ∈ p(N eud(f ); dim x f < λx 3 }. Let Px,f = {g(x); (x, g) ∈ U and ∀y = x g(y) = f (y)}. To each point of ∂ B ′
x Px,f we can associate, by the same way as before, a point of ∂ DF U . So, we have:

|∂ DF U | ≥ x∈P f ,f ∈F2 |∂ B ′ x Px,f |. Now for x in P f , dim x f = | Px,f | < λ x = 1 3 F ol B ′ x (n) < F ol B ′ x (n). So |∂ B ′ x Px,f | > 1 n | Px,f |, ie: |∂ B ′ x Px,f | ≥ 1. Then, x∈P f ,f ∈F2 |∂ B Px,f | ≥ f ∈F2 2 3 |N eud(f )| by (19), ≥ 2 3 |N eud(F 2 )|
We have thus

|∂ DF U | ≥ 1 n |N eud(F 2 )| for n ≥ 2.
C. Adding [START_REF] Ershler | On isoperimetric profiles of finitely generated groups[END_REF] and this last equation and using the inequality

|∂D F U| |U| < 1 1000n
, we obtain :

|N eud| |U | < 1 500
.

Lemma 2.3. Let (Γ U , w) be the one dimensional skeleton with weights w, constructed from

K U . Let η = (η a ) a∈p(U) . Assume that E(Γ U ) = ∅ and ∀(a, f ) ∈ U dim a f ≥ η a > 0.
If the following condition is satisfied : w(e) < 1/2, then there exists a not empty subgraph

Γ ′ = V (Γ ′ ), E(Γ ′ ) of Γ U such that all
edges are S e U (η/10, b/10).

Proof. In the gaph V (Γ U ), E(Γ U ) , we remove all points N S p U (η/10, b/10) and the adjacent edges. After this step, it may appear new points which are N S P U1 (η/10, b/10), where U 1 = U -N S p U (η/10, b/10). We remove once again these points and adjacent edges and we reiterate this process. Let U i be the set of points still present at step i.

U 0 = U, for i ≥ 1 U i+1 = U i -N S p
Ui (η/10, b/10). It is sufficient to prove that this process stops before the graph becomes empty. Let If we show that C 2 ≤ C 1 , the propostion is proved, since :

C 0 ≤ C 1 + C 2 ≤ 2C 1 < e∈E(ΓU )
w(e). Proof. It would be useful to notice that for a multidimensional edge e, the sum of the weights (in the skeleton) of edges coming from e and adjacent to a point, is always equal to 1. This is implied by our choice of the weight.

Indeed
The proof is divideds into five parts.

A. Let N 0 the number of multidimensional edges at step 0. Since L is S p U (η, b), there are at least b multidimensional edges attached to L. So, N 0 ≥ b. [START_REF] Saloff-Coste | A survey on the relationships between volume growth, isoperimetry, and the behaviour of simple random walks on Caley graphs[END_REF] Note that: We have: C. Since L becomes N S p U k (η/10, b/10), there are less than b/10 multidimensional edges associated to each point x, of dimension at least η x /10. Call them f 1 , ..., f q , with q < b/10.

L ↓ = L 1 ↓ ∪ L 2 ↓ ,
(Initially this last sum was equal to 1, but after removing some edges, this sum value becomes less than 1.) D. Let g 1 , ..., g h be the other multidimensional edges attached to L at step k associated to a point x, and with dimension strictly less than η x /10. We have h ≤ N 0q. Consider an edge e coming from a multidimensional edge associated to a point x. For all k = 1...h we have:

e coming f rom g k w(e) ≤ 1 η x η x 10 ≤ 1 10 . (9)
Indeed, firstly since all configurations (relatively to this edge e) have initially dimension at least η x we deduce that w(e) ≤ 1/η x . And secondly a multidimensional edge of dimension less than η x /10 gives less than η x /10 edges in the skeleton.

E. Finaly by ( 8) and (9), we get:

e∈L ↓ w(e) = e∈L1 ↓ w(e) + e∈L2 ↓ w(e) ≤ q + (N 0 -q) 1 10 = 1 10 N 0 + 9 10 q = 19 100 N 0 .
(q < b/10 ≤ N 0 /10 by ( 7).)

So, e∈A ↓ w(e) ≤ 19 100 N 0 and e∈A ↑ w(e) ≥ N 0 - 19 100 N 0 = 81 100 N 0 . So, e∈A ↓ w(e) ≤ 19 81 e∈A ↑ w(e) ≤ 1 2 e∈A ↑ w(e).
To finish the proof, let us consider: D 1 = { vertices removed at step 1}, and for i ≥ 2

D i = {vertices S p U (η, b) removed at step i}, F i = {edges between D i and D i-1 }, F ′ i = {edges leaving D i-1 }.
Note that F i ⊂ F ′ i and that the edges of

F ′ i are removed. D1 D2 } F2 F3 } D3
The proof ends up in four parts: A. Apply sublemma 2.13 to each point of D i , in the graph staying

at step i -2. (Each point of D i is S(η, b).) We get : ∀i ≥ 2 e∈F ′ i+1 w(e) ≤ 1 2 e∈Fi w(e).
So,

e∈F ′ i+1 w(e) ≤ ( 1 2 ) i-1 e∈F2
w(e).

(We use that

F i ⊂ F ′ i .) Hence, e∈ ∪ i≥3 F ′ i w(e) ≤ ( i≥1 ( 1 2 ) i ) e∈F2 w(e) = e∈F2
w(e).

B. Now, an edge of

F 2 is N S e U (η
w(e) ≤ e∈ ∪ i≥3 F ′ i w(e).
D. Hence, C 2 ≤ C 1 , which achieves the proof. Now, we use the following lemma to get a lower bound of the volume of U .

Lemma 2.5. Let N : R + -→ R + , a non decreasing function.

Let us take b ∈ N * and A a not empty set of configurations such that :

∀f ∈ A ∃x 1 , x 2 , ..., x b ∈ Z such that ∀i ∈ [|1; b|] g i ∈ A
where g i is one of the following functions, defined from f by :

g i (x) = f (x) if x = x i , there are N (|x i |) possibilities for g i (x i ) if x = x i , then |A| ≥      N (0) N (1)N (2)...N ( b-1 2 ) 2 if b is odd, N (0) N (1)N (2)...N ( b-2 2 ) 2 N ( b 2 ) if b is even.
Proof. We will proceed by induction on b.

If b = 1 it is true, since N is non decreasing on R + .
Assume b ≥ 1 and consider a point x 0 in the base such that:

•|x 0 | ≥ b-1 2 if b is odd and |x 0 | ≥ b 2 if b is even. • And there exists f 1 , ..., f N (|x0|) ∈ A satisfying ∀i ∈ [|1; N (|x 0 |)|] f i (x 0 ) range among the N (|x 0 |) possible images. For i ∈ [|1; N (|x 0 |)|], we denote by A i the set {f ∈ A; f (x 0 ) = f i (x 0 )}, which is not empty. We have A = ˙ 1≤i≤N (|x0|) A i .
Besides, the A i satisfies the induction assumption with constant b -

1. So, if for example b is odd, N (|x 0 |) ≥ N ( b- 1
2 ) and we have:

|A| = 1≤i≤N (|x0|) |A i | ≥ 1≤i≤N (|x0|) N (0) N (1)...N ( b -3 2 ) 2 N ( b -1 2 ) ≥ N (0) N (1)...N ( b -3 2 ) 2 N ( b -1 2 )N (x 0 ) ≥ N (0) N (1)...N ( b -1 2 ) 2 .
The proof unfolds the same way when b is an even number.

Proof of (i) of the proposition 1.2 :

• Lower bound of Folner function.

For the lower bound of F ol DF , take

U ⊂ V (A ′ ≀ B ′ z ) such that |∂D F U| |U| ≤ 1 1000n Let K = V ( K), ξ( K) the subhypergraph of K U constructed with points (x, f ) which are F ol B ′ x (n)/3 -good. K is not empty, since by the part (i) of the lemma 2.2 |V ( K)| ≥ (1 -1 1000n )|U |.
Then we have:

e∈E(Γ( K))∩N S e ( λ(n) 3 , ψ(n) 3 ) w(e) ≤ 1 2 #{u ∈ U ; N S p λ(n) 3 , ψ(n) 3 } by remark (4) ≤ 1 1000 |U | by lemma 2.2(ii) ≤ 1 1000 -1 n #{u = (x, f ) ∈ U, λ x (n) 3 -good} by lemma 2.2(i) = 2 1000 -1 k e∈E(Γ( K)) w(e) ≤ θ e∈E(Γ( K))
w(e).

with θ = 2 999 < 1 2 , so lemma 2.3 can be applied to K, to deduce there exists a subgraph

K ′ = (V (K ′ ), E(K ′ )) of K such that all edges are S e (λ(n)/30, ψ(n)/30).
Then by lemma 2.5 applied with N (|x|) = F ol Bx (n)/30 to the set of configurations relatively to K ′ , we deduce for large enough n :

|U | ≥ l(0) l(1)...l( ψ(n) 40 ) 2 = F (1) F (0) F (2) F (1) ... F (n/40 + 1) F (n/40) 2 . (We use that for k ≥ 3, F ol B ′ x (k) = |B ′ x | = l(|x|) = F (|x|+1) F (|x|) .) So, |U | ≥ cF (n/40) 2 F (k). (Since F (x) = e cx 2α 1-α we have F ≈ F 2 .) ie : F ol DF (k) F (k).
•Upper bound of Folner function.

For the upper bound of the Folner fonction of D F , we take:

U = {(a, f ); 0 ≤ a ≤ n ; supp(f ) ⊂ [|0; n|]}. On a |U | = nF (n) et |∂ DF U |/|U | ≤ c/n, so, F ol DF (n) ≤ nF (n) F (n).
• So the graph D F has the expected Folner function on the case α > 1/3. 2.2.3. Proof of (ii) of the proposition 1.2 : We proceed in 5 steps.

A. Let d 0 = (0, f 0 ) where f 0 is the null configuration.

Let H n = (K n , g n ) the random walk on D F starting from d 0 which jumps uniformly on the set of points formed by the point where the walker is and its neighbors. This random walk admits a reversible measure µ defined by µ(x) = ν DF (x) + 1.

Note that for all x ∈ V (D F ), µ(x) ≤ 5.

B. Using reversiblity, we can write,

p DF 2n (d 0 , d 0 ) = z p DF n (d 0 , z)p DF n (z, d 0 ) ≥ z∈A p DF n (d 0 , z) 2 µ(d 0 ) µ(z) ≥ µ(d 0 ) µ(A) [ z∈A p DF n (d 0 , z)] 2 ≥ µ(d 0 ) µ(A) [P DF d0 (H n ∈ A)] 2 , where A is some subset of V (D F ). Choose A = A r = {(a, f ) ; |a| ≤ r and supp(f ) ⊂ [-r, r]}.
C. The structure of edges on D F implies:

P DF d0 (H n ∈ A r ) ≥ P DF d0 (∀i ∈ [|0, n|] |K i | ≤ r) ≥ P K 0 (∀i ∈ [|0, n|] |K i | ≤ r),
where P K 0 is the law of (K i ) which is again a random walk with probability transitions that can be represented for n large enough by :

n-1 n n+1 1/5 3/5 1/5
Indeed, as soon as l(|n|) > 3, the point (n, f ) has 2 neighbors in "configuration", 2 neighbors in "base" and itself as neighbor. For this walk we can prove (as in proposition 5.2 in [6]) that :

∃c > 0, ∀n ≥ 0 P K 0 (∀i ∈ [|0, n|] |K i | ≤ r) ≥ e -c(n/r 2 +r) .
In fact, a better bound holds

P K 0 (∀i ∈ [|0, n|] |K i | ≤ r) ≥ e -cn/r 2 (see lemma 7.4.3 of [7]
) but it is not necessary here. Thus,

P DF d0 (H n ∈ A r ) ≥ e -c(n/r 2 +r) . (10)
D. Compute now µ(A r ), we have:

µ(Ar) ≤ |Ar| max Ar µ ≤ (2r + 1) F (1) F (0) ( k=1..r F (k + 1 F (k) ) 2 × 5 ≤ CrF (r + 1) 2 F (r).
( This last inequality comes from the form of F (r) in e cr 2α 1-α .) E. Gathering the results, by inequality (10) and the fact that 2α 1-α ≥ 1, we deduce that it exists c > 0 such that:

p DF 2n (d 0 , d 0 ) ≥ e -c( n r 2 +r 2α 1-α ) . The function r → n r 2 + r 2α 1-α is minimal for r like n 1-α
2 . So , it exists c > 0 such that:

p DF 2n (d 0 , d 0 ) ≥ e -cn α .
Remark 2.6. Note that by proposition 1.1 and with our estimate of F ol DF , we have for all x, y in

D F , p DF 2n (x, y) e -n α . So p DF 2n (d 0 , d 0 ) ≈ e -n α 2.3. case 0 ≤ α ≤ 1 3 . 2.3.1.
Construction of the graph and preliminary lemmas. Consider the general following context: let A and B two graphs and φ an application A → A ′ . Now we look at the graph such that:

-the points are elements of (A × B A ′ ), -edges are couple ((a, f ); (b, g)) such that : Such graphs are called generalized wreath products. If A ′ = A and φ = id we retrieve our ordinary wreath products.

(i) either ∀x ∈ A ′ , f (x) = g(x)

Case which interest us is when

A = A ′ = (Z, E(Z)
) and B is the Cayley graph of Z 2Z with 1 as generator. To define φ : Z → Z, it is sufficient to give the following sets A i = {x; φ(x) = i}, which should form a partition of φ(Z) (which is here Z). Let A = {A i }, we note A≀ A B the generalized wreath product considered.

Let β = 2α 1-α < 1.
If we want a Folner function like e n β , we should construct φ (or the partition A) with some redundancies. Suppose for example that Folner sets are :

U n = {(a, f ); a ∈ [-n; n] et supp(f ) ∈ [-n; n]}, (11) we should have #φ([| -n; n|]) = {i; A i ∩ [-n; n] = ∅} ≈ n β .
For Ω ⊂ A, it would be useful to introduce:

N A (Ω) = #{i; A i ∩ Ω = ∅}, and S j (Ω) = #(A j ∩ Ω).
In particular, let:

N A (k, k + m) = N A ([k, k + m]) et S j (k, k + m) = S j ([k, k + m[).
The following lemma gives us the construction of the partition which answers to our problem.

Lemma 2.7.

Let g : N → N increasing with g(1) = 1 such that for all n in N,

g(2n) ≤ 2g(n).
Then there exists a partition A g = {A i } of Z satisfying: (i) for all m ≥ 0 and for all k in Z,

N Ag (k, k + m) ≈ g(m),
(ii) there exists K > 0 such that for all m ≥ 0, for all k in Z and for all i, j in

S j (k, k + m) = 0: S i (k, k + m) S j (k, k + m) ≤ K.

Proof.

A. We first define partition on intervals [1, 2 s ] (s ≥ 0) by induction on s, such that :

(P s ) N Ag (1, 2 s ) = g(2 s ), Si(1,2 s ) Sj (1,2 s ) ≤ 2 for S j (1, 2 s ) = 0.
• For s = 0, we put the point 1 in some A i , since g(1) = 1 (for example A 1 ).

• Let s ≥ 1 and suppose now the partition is built on [1, 2 s ]. We extend this partition to ]2 s , 2 s+1 ]. Let A 1 , A 2 , ..., A g(2 s ) the partition on [1, 2 s ] given by induction assumption. Rank by decreasing cardinal these sets:

A i1 , A i2 , ..., A i g(2 s ) . (*) ie: #(A i1 ∩ [1, 2 s ]) ≥ #(A i2 ∩ [1, 2 s ]) ≥ ... ≥ #(A i g(2 s ) ∩ [1, 2 s ]). (*) is only to get (ii). Let j ∈]2 s , 2 s+1 ], there exists i k such that j -2 s ∈ A i k , -if k > g(2 s+1 ) -g(2 s ), we put j in A i k , -otherwise, we put j in a "new " class, j ∈ A g(2 s )+k .
Thus we have :

N Ag (1, 2 s+1 ) = N Ag (1, 2 s ) + #{k ∈ [1, g(2 s )]; k ≤ g(2 s+1 ) -g(2 s )} = g(2 s ) + g(2 s+1 ) -g(2 s ) = g(2 s+2 ).
Besides, note that by construction either S i (1, 2 s+1 ) = S i (1, 2 s ) or either S i (1, 2 s+1 ) = 2S i (1, 2 s ). So the second assertion of (P) is well satisfied at the rank s + 1, except when S i (1, 2 s+1 ) has doubling and S j (1, 2 s+1 ) is unchanged. But in this case, by (*) we have #(

A i ∩ [1, 2 s ]) ≤ #(A j ∩ [1, 2 s ]), that could be written S i (1, 2 s ) ≤ S j (1, 2 s ). So, S i (1, 2 s+1 ) S j (1, 2 s+1 ) = 2 S i (1, 2 s ) S j (1, 2 s ) ≤ 2.
B. We end up the construction of the partition on Z as follow: for j ≤ 0, we put j ∈ A i where -j + 1 ∈ A i . we call A g this partition.

C. Let us check conditions (i) and (ii). First, notice that for all integers A and for all s ≥ 0, partitions on[1, 2 s ] and [A2 s + 1, (A + 1)2 s+1 ] are equivalents. And in particular we have:

N Ag (0, 2 s ) = N Ag (2 s A, 2 s (A + 1)), (12) et S i (2 s A, 2 s (A + 1)) S j (2 s A, 2 s (A + 1)) ≤ 2. (13) Consider k ∈ Z and m ≥ 0. Let s ≥ 0 be such that 2 s-2 < m ≤ 2 s-1 and let A = min{D; k ≤ D2 s-2 }. We have [A2 s-2 , (A + 1)2 s-2 ] ⊂ [k, k + m] and then N Ag (k, k + m) ≥ N Ag (2 s-2 A, 2 s-2 (A + 1)) = N Ag (0, 2 s-2 ) = g(2 s /4) ≥ g(m/4) g(m). Let B = max{D; D2 s-1 ≤ k}, we have [k, k + m] ⊂ [B2 s-1 , (B + 2)2 s-1 ]. So, N Ag (k, k + m) ≤ N Ag (B2 s-1 , (B + 2)2 s-1 ) = N Ag (B2 s-1 , (B + 1)2 s-1 ) + N Ag ((B + 1)2 s-1 , (B + 2)2 s-1 ) = 2g(2 s-1 ) ≤ 2g(2m) g(m).

That proves (i).

Let now C = max{D; D2 s-3 ≤ k}, by the definition of s, it is easy to verify that :

[(C + 1)2 s-3 , (C + 2)2 s-3 ] ⊂ [k, k + m] ⊂ [C2 s-3 , (C + 5)2 s-3 ]. (14) k k+m s-3 s-3 c2 (c+1)2 (c+2)2 s-3 2 s-3 2 s-3 (c+5)2 s-3
Let i, j be the subscript which index the partition such that S i (k, k + m) = 0 and S j (k, k + m) = 0, we can write,

S i (k, k + m) ≤ S i (C2 s-3 , (C + 5)2 s-3 ) ≤ 2S j (C2 s-3 , (C + 5)2 s-3 ) par (13) = 2[S j (C2 s-3 , k) + S j (k, k + m) + S j (k + m, (C + 5)2 s-3 )]. ( 15
)
Consider the terms S j (C2 s-3 , k) and S j (k + m, (C + 5)2 s-3 ). First we have S j (C2 s-3 , k) ≤ S j (C2 s-3 , (C + 1)2 s-3 ). Besides, there exists j 1 such that

S j (C2 s-3 , (C + 1)2 s-3 ) = S j1 ((C + 1)2 s-3 , (C + 2)2 s-3 ).
We deduce

S j (C2 s-3 , (C + 1)2 s-3 ) = S j1 ((C + 1)2 s-3 , (C + 2)2 s-3 ) ≤ 2S j ((C + 1)2 s-3 , (C + 2)2 s-3 ) by (13) ≤ 2S j (k, k + m)
by the first inclusion of ( 14) By using the same approach, we prove,

S j (k + m, (C + 5)2 s-3 ) ≤ 2S j (k, k + m).
Finaly with (15) we get,

S i (k, k + m) ≤ KS j (k, k + m) with K = 10.

That proves (ii).

Remark 2.8. The property (ii) of lemma 2.7, can be extend immediatly for all finite set Ω. Indeed, we have for each connected component Ω s of Ω, S i (Ω s ) ≤ KS j (Ω s ). Then summing on s, we get S i (Ω) ≤ KS j (Ω) Before showing that the graph A ≀ Ag B is solution of our problem, let us notice the following property of the partition A g , that will be useful in the next.

Lemma 2.9. Let g satisfying assumptions of property 2.7 and A g = {A i } the associated partition. There exists constants c 1 , c 2 > 0 such that for all Ω ⊂ Z,

satisfying |∂ A ′ Ω| |Ω| ≤ 1 k , for all Ω δ ⊂ Ω such that |Ω δ | ≥ δ|Ω|, (δ > 0)
we have:

#{i; A i ∩ Ω δ = ∅} ≥ c 1 δ 2K g(c 2 F ol A (k)),
where K is the constant which appears in the item (ii) of lemma 2.7.

Proof.

(

) Let Ω ⊂ Z such that |∂ A ′ Ω| |Ω| ≤ 1 k . There exists at least one connected component Ω s0 of Ω such that |∂ A ′ Ω s 0 | |Ω s 0 | ≤ 1 k and so |Ω s0 | ≥ F ol A (k). (2) Take for c 1 et c 2 the constants verifying N Ag (k, k + m) ≥ c 1 g(c 2 m), for all k in Z and m in N. (3) There exists i 0 such that 0 < |A i0 ∩ Ω| ≤ |Ω| c1g(c2F olA(k)) . Indeed, if for all j such that |A j ∩ Ω| > 0 we had |A j ∩ Ω| > |Ω| c1g(c2F olA(k)) 1
then we would have had ,

|Ω| = j |A j ∩ Ω| > N Ag (Ω) |Ω| c 1 g(c 2 F ol A (k)) > N Ag (Ω s0 ) |Ω| c 1 g(c 2 F ol A (k)) > |Ω| (by the choice of c 1 et c 2 .)
Absurd.

(4) We deduce that for all i,

|A i ∩ Ω| ≤ K|Ω| c1g(c2F olA(k))
. Indeed, by remark 2.3.1, for all i we can write :

|A i ∩ Ω| = S i (Ω) ≤ KS i0 (Ω) = K|A i0 ∩ Ω| ≤ K|Ω| c 1 g(c 2 F ol A (k))
.

(5) Assume now that #{i;

A i ∩ Ω δ = ∅} ≤ c 1 δ 2K g(c 2 F ol A (k)
). Then we have successively,

δ|Ω| ≤ |Ω δ | = i; Ai∩Ω δ =∅ |A i ∩ Ω δ | ≤ #{i; A i ∩ Ω δ = ∅} × max i |A i ∩ Ω δ | ≤ #{i; A i ∩ Ω δ = ∅} × max i |A i ∩ Ω| ≤ c 1 δ 2K g(c 2 F ol A (k)) × K|Ω| c 1 g(c 2 F ol A (k)) = δ|Ω| 2 .
Absurd.

Take now g : x → x β . Since β < 1, assumptions of lemma 2.7 are satisfying. Let D F = A ≀ Ag B, in the following lines we are going to prove that this graph is solution of propostion 1.2.

proof of (i) of proposition 1.2. •Upper bound of Folner function

Using the sets U n defined by (11), we get upper bound of Folner function. .

F ol DF (n) |U n | = (2n + 1)2 N Ag (-n,n) ≈ e n β .

•Lower bound of Folner function

We get the lower bound by the same ideas as in the case α > 1/3, but we have to improve the definition of satisfactory points. Let M a set of part of V (A) and let ǫ > 0 and y > 0. Given U ⊂ V (A ≀ Ag B) and f a configuration of U , we say that the configuration f is (1ǫ, y) M satisfactory if there exists M ∈ M such that

M ′ ⊂ M and (1 -ǫ)|M | ≤ |M ′ |, where M ′ = {a ∈ V (A); dim φ(a) f ≥ y}.
Then the proof falls into 3 steps.

(1) Let U ⊂ V (D F ) such that

|∂D F U| |U| ≤ 1 k . (**) (2) For W ⊂ V (D F ), we call W c = {f ; ∃a ∈ V (A) (a, f ) ∈ W }.
By the same way as in the proof of propostion 1.2 in the case α > 1/3, we prove that there exists ǫ > 0 such that for all U verifying (**), there exists W ⊂ U such that all f of W c is (1ǫ, F ol B (k)/30) M satisfactory, with

M = {D ⊂ V (A); |∂ A D| |D| ≤ 1 k }.
This result is analogous to lemma 2.2 et 2.3 is proved in the next section 2.4.

(3) Take now f ∈ W c , there exists M ∈ M such that,        M ′ = {a ∈ V (A); dim φ(a) f ≥ F ol B (k)/30} ⊂ M and |M ′ | ≥ (1 -ǫ)|M |.
Lemma 2.9 apply with δ = 1ǫ, M = Ω and M ′ = Ω δ . We deduce that for all f in W c , we can change the value of the configuration f in at least c 1 1-ǫ 2K g(c 2 F ol A (k)) points in F ol B (k)/30 ways by staying in W c . Then we conclude by the following lemma: Lemma 2.10. Let Y > 0 and X > 0. Let A a non empty set of configurations, such that for all configurations of A, there exists at least Y points where we can change the value of the configuration in X way without leaving A. Then : |A| ≥ X Y . ie:

(∀f ∈ A ∃a 1 , a 2 , ..., a Y ∈ A such that g ∈ A) =⇒ |A| ≥ X Y ,
where g is defined from f by : g

(x) = f (x) if x = a i0 , X possibilities f or g(a i0 ) if x = a i0 .
Proof. We proceed by induction on Y . If Y = 1, it is exact. Suppose Y ≥ 1 and consider a point x 0 in the base such that there exists

X distinct configurations f 1 , ..., f X ∈ A such that ∀y = x 0 f 1 (y) = f 2 (y) = ... = f X (y). For all i = 1...X, let A i = {f ∈ A; f (x 0 ) = f i (x 0 )}, which are not empty. A = ˙ i=1...X A i and the A i satisfy induction hypothesis with constant Y -1. So, |A| = i=1...X |A i | ≥ X.X Y -1 = X Y .
Finally, lemma 2.10 gives,

|U | ≥ |W c | ≥ ( F ol B (k) 30 ) c ′ 1 g(c2F olA(k)) e g(k) , since first F ol B (n) = 2 and secondly F ol A (k) = 2k.
2.3.3. proof of (ii) of proposition 1.2. We follow idea of the case α ≥ 1/3.

(1) Let d 0 = (0, f 0 ) where f 0 is the configuration which is null every where. Let X n = (K n , g n ) be the random walk on D F defined above. X starts from d 0 and jumps uniformly on the set of points formed by the point where the walk is and its neighbor. On this generalized wreath product, this walk is still reversible for the uniform measure since the number of neighbor in D F is constant, equal to 4. Now write:

p DF 2n (d 0 , d 0 ) = z p DF n (d 0 , z)p DF n (z, d 0 ) ≥ z∈G p DF n (d 0 , z) 2 ≥ 1 |G| [ z∈G p DF n (d 0 , z)] 2 ≥ 1 |G| [P DF d0 (X n ∈ G)] 2 ,
where G is some finite set of V (D F ).

(2) Take G = G r = {(a, f ) ; |a| ≤ r and supp(f

) ⊂ φ([| -r, r|])}.
By the structure of edges on D F , we have :

P DF d0 (X n ∈ G r ) ≥ P DF d0 (∀i ∈ [|0, n|] |K i | ≤ r) ≥ P K 0 (∀i ∈ [|0, n|] |K i | ≤ r),
where P K 0 is the law of (K i ) i which is still a random walk with transitions probability which can be represented by :

n-1 n n+1 1/4 1/4 1/2
(3) Now we have to find a lower bound for

P K 0 (∀i ∈ [|0, n|] |K i | ≤ r). It is not sufficient to use P K 0 (∀i ∈ [|0, n|] |K i | ≤ r) ≥ e -c
(n/r 2 +r) as in the case α > 1/3, because β = 2α 1-α < 1 ( see step D of this proof). However we can prove that :

∃c > 0, ∀n ≥ 0 P K 0 (∀i ∈ [|0, n|] |K i | ≤ r) ≥ e -cn/r 2 .
One can find this result in the lemma 7.4.3 of [START_REF] Saloff-Coste | A survey on the relationships between volume growth, isoperimetry, and the behaviour of simple random walks on Caley graphs[END_REF]. It is known for a simple random walk on Z d and we can deduce it in this particular case with a coupling. Consider K ′ i which takes values in Z 2 . K ′ i follows the horizontal jumps of K i if K i moves and jumps uniformly on its 2 vertical neighbors if K i stays at its place. On the first hand we have {sup 0≤i≤n |K ′ i | ≤ r} ⊂ {sup 0≤i≤n |K i | ≤ r} and on other hand K ′ i is a simple random walk on Z 2 . (For x = (a, b) ∈ Z 2 , we note |x| := max(a, b).) Then the result for K i in Z follows from the result for K ′ i in Z 2 . (4) We can end up the proof. From |G r | = (2r + 1)2 N Ag (-r,r) e r β , we deduce there exists c > 0 such that :

p DF 2n (d 0 , d 0 ) ≥ e -c( n r 2 +r β ) .
But the function r → n r 2 + r β , is minimal for r like n 1 β+2 . So there exists c > 0 such that:

p DF 2n (0, 0) ≥ e -cn β β+2 = e -cn α .
2.4. Complement on satisfactory points. In this section we improve the notion of satisfactory point used in subsection 2.3 which is more abstract that the notion introduced in subsection 2.2. The reasons of this improvement will be explain in the next. We still consider a wreath product A ≀ B of two graphs A and B or a generalized wreath product A ≀ A B associated to some partition A. We take U ⊂ V (A ≀ B) and as before to each U we associate an hypergraph K U and its one dimensional skelelton Γ U with weight w, built as the same way that in section 2.2.

Let ǫ > 0 and a ≥ 0. Let M a set of parts of V (A). To light the way of this definition and to link it with the old definition of satisfactory points (section 2.2), one can think to take for M set of the form

{D ⊂ V (A); |∂AD| |D| ≤ 1 k }. • A configuration f of V (K U ) is said (1 -ǫ, a) M satisfactory if : there exists M ∈ M such that      M ′ ⊂ M and (1 -ǫ)|M | < |M ′ | (16)
where

M ′ = {m ∈ V (A); dim m f ≥ a}.
Once again, we denote by S U (1ǫ, a) M (or S(1ǫ, a) M ) the set of satisfactory configurations.

• Otherwise f is not satisfactory and we note N S(1ǫ, a) M ) the set of not satisfactory configurations.

• If Γ ′ is a subgraph of Γ U , we say that f is S(1 -ǫ, a) M in respect to Γ ′ if f
satisfies the same condition as in (16) but where dimension of f is counted only with edges in Γ ′ . More precisely : dim m,Γ ′ f = #{g; (f, g) ∈ E(Γ ′ ) and (x, g) ∈ U and ∀y = x f (y) = g(y)}.

• An edge of Γ U is said (1ǫ, a) M satisfactory if it joins two (1ǫ, a) M satisfactory configurations, otherwise it is said (1ǫ, a) M not satisfactory. As before we denote by S e (1ǫ; a) M [resp N S e (1ǫ, a) M ] the set of satifactory edges [resp not satisfactory ].

• A point u = (x, f ) ∈ U is said (1 -ǫ, a) M satisfactory [resp (1 -ǫ, a) M not sat- isfactory ] if f ∈ S(1 -ǫ, a) M [resp N S(1 -ǫ, a) M ].
We denote by S p (1ǫ, a) M and N S p (1ǫ, a) for the set of points which are (or are not ) satisfactory.

• We keep the same defintion for good points,

u = (x, f ) ∈ U is said a -good if dim x f ≥ a otherwise it is said a -bad.
The interest of this new definition of satisfactory points is the following. Consider a set U c of (λ, b)satisf actory configurations. With the "old" definition we know that we can change the value of f in at least b points in λ x ways (at point x) without leaving U c but we do not know exactly where are these b points whereas with the "new" definition, for a set U c of S(1ǫ, a) M configurations, we know that we can change the value of f in at least (1ǫ) min M∈M |M | points in a ways without leaving U c et moreover we know that these points are contained in some M ∈ M. This would be useful for our generalized wreath products since this property concentrate points where we can change value of f . By the properties of partition, it remains only to get lower bound of #φ(M ).

Let U ∈ V (A≀B) such that

|∂ A≀B U| |U| ≤ 1 1000k
, the two following lemmas are similar to lemmas 2.2 et 2.3.

Lemma 2.11. Let M = {D ⊂ V (A); |∂AD| |D| ≤ 1 k } then we have : (i) #{u∈U; u is F olB (k)-bad } |U| ≤ 1 1000 , (ii) there exists ǫ > 0 such that #{u∈U; (1-ǫ,F olB(k)/3)M-not satisfactory} |U| ≤ 1 500 .
Proof.

For (i), it is the same argument that in part (i) of lemma 2.2. For (ii) let,

N eud = {u ∈ U ; u ∈ N S p (1 -ǫ, F ol B (k) 3 ) M } = {u = (x, f ) ∈ U ; f ∈ N S(1 -ǫ, F ol B (k) 3 )},
and let:

N eud(f ) = {(x, f ); (x, f ) ∈ U }. Note that p(N eud(f )) = {x; (x, f ) ∈ U }.
For F a set of configurations, let

N eud(F ) = ∪ f ∈F N eud(f ).
Note the union is disjointed.

Take now f ∈ N S(1ǫ, F olB(k)

3

) M , and consider the set p(N eud(f )). Two cases appear. Either p(N eud(f )) gives a large part of boundary in "base" either not and this case by assumptions on f we will prove that p(N eud(f )) gives boundary in "configurations"

First case : f ∈ F 1 := {f ∈ N S(1 -ǫ, F olB (k) 3 ) M ; #∂A p(N eud(f )) #p(N eud(f )) > 1 k }. The application ˙ f ∈F1 ∂ A p(N eud(f )) -→ ∂ A≀B U is injective. (x, y) -→ (x, f ) ; (y, f )
So, we can write :

(17) |∂ A≀B U | ≥ f ∈F1 |∂ A p(N eud(f ))| ≥ 1 k f ∈F1 |p(N eud(f ))| ≥ 1 k |N eud(F 1 )|. Second case : f ∈ F 2 := {f ∈ N S(1 -ǫ, F olB (k) 3 ) M ; #∂A p(N eud(f )) #p(N eud(f )) ≤ 1 k }. Since f ∈ N S(1 -ǫ, F olB (k)
3

) M we have :

for all M ∈ M      ∃ m ′ ∈ M ′ -M, or |M ′ | ≤ (1 -ǫ)|M |, (18)
where M ′ stands for {m ∈ V (A); dim

m f ≥ F olB (k) 3 }.
Choose M = p(N eud(f )) since f ∈ F 2 we have M ∈ M and M ′ ⊂ M . So it is the second item of assertion (18) which is satisfied. ie :

|M ′ | ≤ (1 -ǫ)|M |. So, #{x ∈ p(N eud(f )); dim x f ≥ F ol B (k) 3 } < (1 -ǫ)|M | = (1 -ǫ)|N eud(f )|.
(We have used that |p(N eud(f

)| = |N eud(f )|.) So #{x ∈ p(N eud(f )); dim x f < F ol B (k) 3 } ≥ ǫ|N eud(f )| ie : |P f | ≥ ǫ|N eud(f )|, ( 19
) with P f = {x ∈ p(N eud(f ); dim x f < F olB (k) 3 }.
To each point of P f ( for f in F 2 ), we can associate in an injective way a point of the boundary (in configuration ) of U . Indeed, as before : for x ∈ P f and f ∈ N eud(F 2 ), we have :

| Px,f | ≤ F ol B (k) 3 < F ol B (k).
where Px,f = {g(x); (x, g) ∈ U and ∀y = x g(y) = f (y)}. Thus,

|∂ B Px,f | > 1 k | Px,f | ≥ 0,
and then

|∂ B Px,f | ≥ 1.
Finally,

|∂ A≀B U | ≥ x∈P f ,f ∈F2 |∂ B Px,f | ≥ f ∈F2 ǫ|N eud(f )| by (19), ≥ ǫ|N eud(F 2 )| ≥ 1 k |N eud(F 2 )| by choising ǫ < 1/k.
By adding (17) and this last inequality and using the fact that

|∂ A≀B U| |U| < 1 1000k , we get : |N eud| |U | < 1 500
.

Lemma 2.12. Let ǫ > 0 and x > 0. Consider Γ U the one dimensional skeleton with weight w, constructed from K U . Assume that E(Γ U ) = ∅ and ∀f ∈ K U dim

x f ≥ a and M does not contain the empty set. If we have : Proof. In the graph Γ U , we remove all points N S p U (1 -9+ǫ 10 , a 10 ) M and adjacents edges. After this first step, it may appear some new points N S P U1 (1 -9+ǫ 10 , a 10 ) M , where U 1 = U -N S p U (1 -9+ǫ 10 , a 10 ) M . We remove again all adjacent edges and points and we iterate this process. Let U i the set of vertices staying at step i.

U 0 = U, for i ≥ 1 U i+1 = U i -N S p
Ui (1 -9+ǫ 10 , a 10 ) M . it is sufficient to prove that this process ends up before the graph becomes empty. Let If we show that C 2 ≤ C 1 , the result is proved since:

C 0 ≤ C 1 + C 2 ≤ 2C 1 < e∈E(ΓU )
w(e).

That would mean that it stays at least one point not removed. ie: ∃k 0 ∈ N such that all points of the graph get at step k, are S p U k 0

(1 -9+ǫ 10 , a 10 ) M , so S p U (1 -9+ǫ 10 , a 10 ) M .

To see this, let us introduce an orientation on removed edges : if L and Q are points of the graph, we orient the edge from L to Q if L s removed before Q otherwise we choose an arbitrary orientation. We note L ↓ the set of edges leaving the point L and L ↑ for the set of edge ending in L at step 0.

Sublemma 2.13. Let k ∈ N and let L be a point of the graph Γ U (satisfying assumptions of lemma 2.12) removed after k + 1 steps. Assume that L is initially

S p U (1 -ǫ, a) M , then e∈L ↓ w(e) ≤ 1 2 e∈L ↑ w(e).
Proof. It would be useful to notice that for a multidimensional edge e, the sum of the weight (in the skeleton) of edges coming from e and adjacent to a point, is equal to 1. This is implied by our choice of the weight.

(1) Let now N 0 be the number of multidimensional edges at step 0. Since L is initially S p U (1ǫ, a) M , there exists M 0 ∈ M such that (1ǫ)|M 0 | multidimensional edges are attached to L. So,

N 0 ≥ (1 -ǫ)|M 0 |. ( 20
)
Besides notice that :

e∈E(ΓU ) e contains L w(e) = N 0 . Let : L 1 ↓ = {e ∈ L ↓ , e coming from a multidimensionnal edge of K U k , of dim ≥ a/10}, and L 2 ↓ = {e ∈ L ↓ , e coming from a multidimensionnal edge K U k , of dim < a/10}. We have L ↓ = L 1 ↓ ∪ L 2 ↓ , because edges of L ↓ correspond to edges leaving L at step k.
(2) Since L becomes N S p U k (1 -9+ǫ 10 , a 10 ) M , we have:

for all M in M      M ′′ ⊂ M or |M ′′ | ≤ (1 -9+ǫ 10 )|M | where M ′′ = {m ∈ V (A); dim m,U k L ≥ a 10 }.
Take M = M 0 , observe that M ′′ ⊂ M 0 so that implies

|M ′′ | ≤ (1 - 9+ǫ 10 )|M 0 |.
Finally L has less than (1 -9+ǫ 10 )|M 0 | multidimensional edges of dimension at least a/10. call them f 1 , ..., f q , with q < (1

-9+ǫ 10 )|M 0 |. e∈L1 ↓ w(e) = k=1..q e coming f rom f k w(e) ≤1 ≤ q. ( 21
)
(Initially this last sum was equal to 1, but after removing some edges, this sum is less than 1.) Besides, call g 1 , ..., g h the other multidimensional edges of dimension strictly less than a/10, attached to L at step k, with h ≤ N 0q. For all k = 1...h, (Indeed, first all point have initially dimension at least a so we deduce ∀e ∈ E(Γ Ui ) w(e) ≤ 1/a and secondly an edge of dimension less than a/10 gives less than a/10 edges attached to one point, in the skeleton. )

(3) Finally with ( 21) and ( 22), we get : The proof ends up by the same way as proposition 2.3, let: D 1 = {vertices removed at step 1}, and for i ≥ 2

e∈L ↓ w(e) = e∈L1 ↓ w(e) + e∈L2 ↓ w(e) ≤ q + (N 0 -q) 1 10 = 1 10 N 0 + 9 10 q = 19 100 N 0 . ( q < (1 -9+ǫ 10 )|M 0 | ≤ N 0 1-9+ǫ 10 1-ǫ ≤ N0
D i = {vertices S p U (1 -ǫ, a) removed at step i}, F i = {edges between D i and D i-1 }, F ′ i = {edges leaving D i-1 }.
Notice that F i ⊂ F ′ i and that edges of

F ′ i are removed. D1 D2 } F2 F3 } D3
By sublemma 2.13 applied in each point of D i in the graph get at step i -2. (Each point of D i is at this moment, at least S(1ǫ, a) M .) We get :

∀i ≥ 2 e∈F ′ i+1 w(e) ≤ 1 2 e∈Fi w(e).
so,

e∈F ′ i+1 w(e) ≤ ( 1 2 ) i-1 e∈F2
w(e).

(We have used that

F i ⊂ F ′ i .) Thus, e∈ ∪ i≥3 F ′ i w(e) ≤ ( i≥1 ( 1 2 ) i ) e∈F2 w(e) = e∈F2
w(e).

Now, an edge of F 2 is N S e U (1ǫ, a) because if this edge was S e U (1ǫ, a), this edge would have linked two points S p U (1ǫ, a) and in particular, points of D 1 would have been S p U (1ǫ, a), so S p U (1 -9+ǫ 10 , a/10) and so would not have removed. Thus : Besides, all removed edge S e U (1ǫ, a) is in some

F ′ i with i ≥ 3, so C 2 =
e removed at the of the process

e∈S e U (1-ǫ,a) w(e) ≤ e∈ ∪ i≥3 F ′ i w(e).
That ends the proof.

Now we are able to explain the fact that we used in section 2.3.2 in order to prove the lower bound of F ol DF . We recall that U ⊂ V (D F ) is such that

|∂ A≀B U| |U| ≤ 1 k .
Let K be the sub hypergraph of K U which contains only F ol B (k)/3-good points.

As in the proof of (i) in the case α > 1/3 of propostion 1.2, we prove by using lemma 2.11 that there exists θ < 1/2 such that,

e∈N S e U (1-ǫ,F olB (k)/3)M e∈E(Γ K )
w(e)

e∈E(Γ K )
w(e) < θ, for some ǫ > 0 and

M = {D ⊂ V (A); |∂AD| |D| ≤ 1 k }. Lemma 2.
12 gives us a sub graph where all edges are S e (1δ, F ol B (k)/30) M for δ = 1 -9+ǫ 10 . By definition of satisfactory points, this proves the fact that we have used.

3. Applications: study of some functionals 3.1. Kind of problems, case of the lattice Z d . Recall that for G a graph and X is a simple random walk on G, we note L x,n = #{k ∈ [0; n]; X k = x}. The question is to estimate functional of type

E ω 0 (e -λ z;Lz;n>0 F (Lz;n,z) ), ( 23
)
where F is a two variables non negative function. The method developped here is due to Erschler and can be applied on general graph G provided the isoperimetric profile on the graph G is known and the function F has some "good" properties. For the case of the simple random walk on Z d , in [START_REF] Ershler | Isoperimetry for wreath products for markov chains and multiplicity of self intersection of random walk[END_REF] it is proved that

∀α ∈ [0, 1] E ω 0 (e -λ z;Lz;n>0 L α z;n ) ≈ e -n η , (24)
∀α ≥ 1/2 E ω 0 ( z;Lz;n>0 L -α z;n ) ≈ e -n d d+2 ln(n) 2 d+2 , (25)
where η = d+α(2-d) 2+d(1-α) . This section is devoted to extend these estimates to an infinte cluster of the percolation model.

3.2.

In an infinite cluster of the percolation model. We still use the notation ω for the application E d → {0, 1} such that ω(e) = 0 if e is a removed edge and 1 otherwise. Let Q be the probability measure under which the variable (ω(e), e ∈ E d ) are Bernouilli(p) independent variables. If p is larger than some critical value p c , the Q probability that C is infinite, is strictly positive and so we can work on the event {#C = +∞}.

We denote by C g the graph such that

V (C g ) = C and E(C g ) = {(x, y) ∈ E d ; ω(x, y) = 1} and C g n the graph such that V (C g n ) = C and E(C g n ) = {(x, y) ∈ E d ; x, y ∈ C n and ω(x, y) = 1}
From now on and until the end, X will design the simple random walk on the graph C g . We are going to prove estimate (24) and (25) for the walk X.

Sketch plan.

Let (B x ) x∈C be a family of graphs and let 0 x an arbitrary point in each B x that we call the origin. For all x ∈ C, consider the random walk (Y x n ) n on B x starting from point 0 x , and jumping uniformly on the set of points formed by the point where the walk is and its neighbors. Let P Bx 0x be the law of (Y x n ) n . Transition kernels of Y x satisfy :

p Bx (a, b) = 1 ν x (a) + 1 (1 {a=b} + 1 {(a,b)∈E(Bx)} ),
where ν x (a) stands for the number of neighbors of a in graph B x .

Consider now the graph

W = W C = C g ≀ (B z ) z∈C . (26)
Let f 0 be the nulle configuration, such that , for x ∈ C, f 0 (x) = 0 x , and let o = (0, f 0 ). And we look at the random walk (Z n ) n on the graph W C starting from o, defined by the following: suppose that the walk is at point z = (x, f ), then in one unit of time the walk makes three independent steps. First, the value of f at point x jumps in graph B x in respect to the walk Y x starting from f (x). Secondly, we make the walker in C jump on his neighbors in respect to uniformly law on his neighbor, so the walker in C (projection on C of walk on W C ) arrives at point y ∈ C. And thirdly, the value of f at point y jumps in graph B y in respect to the walk Y y starting from f (y). Thus, calling p transitions kernel of Z, we have: for all ((a, f ); (b, g))

∈ (V (C g ≀ B z )) 2 : p[(a, f )(b, g)] = χ[(a, f ), (b, g)] ν(a) [ν a (f (a)) + 1] [ν b (f (b)) + 1] , (27)
where χ[(a, f ), (b, g)] is equal to 1 if the walk is able to jump from (a, f ) to (b, g) and 0 otherwise. More precisely,

χ[(a, f ), (b, g)] = ω(a, b) (χ 1 [(a, f ), (b, g)] + χ 2 [(a, f ), (b, g)] + χ 3 [(a, f ), (b, g)] + χ 4 [(a, f ), (b, g)]), with χ 1 [(a, f ), (b, g)] = 1 {∀x f (x)=g(x)} , χ 2 [(a, f ), (b, g)] = 1 { (f (a),g(a))∈E(Ba) ∀x =a f (x)=g(x) } , χ 3 [(a, f ), (b, g)] = 1 { (f (b),g(b))∈E(B b ) ∀x =b f (x)=g(x) } , χ 4 [(a, f ), (b, g)] = 1 {∀x∈{a,b} (f (x),g(x))∈E(Bx) ∀x =a,b f (x)=g(x) } .
Notice that m defined by,

m(a, f ) = ν(a), (28)
is a reversible measure for the walk Z. We note ã the following kernels:

ã(x, y) = m(x)p(x, y) (29)

Let Pω

o be the law of Z starting from o. The key for our problem is the following interpretation of the return probability of Z:

Proposition 3.1. Pω o (Z n = o) = E ω 0 ( x;Lx;n>0 P Bx 0x (Y x Lx;n = 0 x ) 1 {Xn=0} ).
Proof. :

Pω o (Z n = o) = Pω o (X n , f n ) = (0, f 0 ) = (k0,k1,...,kn)∈Z d k 0 =kn =0 Pω o (X 0 = k 0 , X 1 = k 1 , ..., X n = k n et f n = f 0 ) = (k0,k1,...,kn)∈Z d k 0 =kn =0 Pω o (X 0 = k 0 , X 1 = k 1 , ..., X n = k n ) × Pω o (f n = f 0 |X 0 = k 0 , ...X n = k n ) = (k0,k1,...,kn)∈Z d k 0 =kn =0 P ω 0 (X 0 = k 0 , X 1 = k 1 , ..., X n = k n ) × x;Lx;n>0 P Bx 0x (Y x Lx;n = 0 x ) = E ω 0 ( x;Lx;n>0 P Bx 0x (Y x Lx;n = 0 x ) 1 {Xn=0} ).
In order to estimate functional such that (23) and in view of propostion 3.1, we have to find graphs B x such that for all m ∈ N : x) . Moreover, since we know that an isoperimetric inequality with volume counted in respect to measure m and boundary counted in respect to kernels ã, gives an upper bound of the decay of the probability transitions of walk Z, in a first time we have to estimate the Folner function of W C and so (by similar results of section 1, see [START_REF] Ershler | Isoperimetry for wreath products for markov chains and multiplicity of self intersection of random walk[END_REF] [5] and [6]) we should know Folner function of each B x . The graph formed by the possible jumps of walk Z is not W C = C ≀ (B z ) z∈C , so we introduce the graph with same set of points of W C but different set of edges. We call it C ≀ ≀(B z ) z∈C or shortly W ′ C (or W ′ ), the graph such that :

P Bx 0x (Y x m = 0) ≈ e -λF (m,
V (W ′ C ) = V (W C ) and, (30) ((a, f ); (b, g)) ∈ E(W ′ C ) ⇐⇒ χ[(a, f ); (b, g)] = 1. Thus, in the graph W ′
C , the random walk Z is a nearest neighbor walk. Properties of Z are linked to geometry of W ′ C but as we will see later W C and W ′ C are roughly isometric, so we can study isoperimetric profile of W C .

Study of E ω

0 (e -λ L α z;n ). Upper bound Let α ∈]0, 1[ and β = 2α 1-α and let F (x) = e x β . Let D F be the graph given by proposition 1.2. We put for all x ∈ C, B x = D F .

First we want to obtain a lower bound of F ol C g ≀≀DF C g n ≀≀DF (k). We proceed in 3 steps: Hence, we have proved that (31) carry to F ol C g ≀≀DF C g n ≀≀DF , so we deduce: Proposition 3.2. For all γ > 0, there exists β > 0 such that for all c > 0, Q a.s on the set |C| = +∞ and for large enough n, we have :

F ol C g ≀≀DF C g n ≀≀DF (k) F (k) k if k < cn γ , (F (k) βk d if k ≥ cn γ . ( 34
)
Now we are able to get an upper bound of Pω o (Z 2n = o) and then an upper bound of our functional. Let

τ n = inf{s ≥ 0 ; Z s ∈ V (C g n ≀ ≀D F )} . We have, Pω o (Z 2n = o) = Pω o (Z 2n = o and τ n ≤ n) + Pω o (Z 2n = o and τ n > n).
The first term is zero since the walk can not go out the box V (C g n ≀ ≀D F ) before time n. The second term can be bounded with proposition 3.2. Let :

H(k) = F (k) k if k < cn γ , (F (k) βk d if k ≥ cn γ . ( 35
)
-H is increasing and we can define an inverse function by

H -1 (y) = inf{x; H(x) ≥ y}.
-Besides, with the help of (34),

F ol C g ≀≀DF C g n ≀≀DF
H.

-C and D F have bounded valency and from formula of m and ã (see ( 29) and ( 28)) we have : inf

V (W ′ ) m ≥ 1 2d > 0 et inf E(W ′ ) ã > 0.
Thus, (see theorem 14.3 in [START_REF] Woess | Random walks on infinite graphsand groups[END_REF] for example) there exists constants c 1 , c 2 and c 3 > 0 such that Pω o (Z 2n = o et τ n > n) u(n) where u is solution of the differential equation :

u ′ = - u c2(H -1 (c3/u)) 2 , u(0) = c 1 .
Replacing F (k) by e k β into H, we get the expression of H -1 :

H -1 (y) =          c(ln(y)) 1-α 1+α if 1 ≤ y < e cn γ(1+α) 1-α , cn γ if e cn γ(1+α) 1-α ≤ y < e cn γ(d+α(2-d)) 1-α , c(ln(y)) 1-α d+α(2-d) if e cn γ(d+α(2-d)) 1-α ≤ y. (36)
Resolving the differential equation in the different cases, we get :

u(t) =          ce -ct 1+α 3-α if t ≤ cn γ(3-α) 1-α , ce cn γ 1+α 1-α e -ct/n 2γ if cn γ(3-α) 1-α < t ≤ cn γ(d+2-dα) 1-α + n γ(3-α) 1-α , ce -(ct-c ′ n γ(d+2-dα) 1-α -cn γ(3-α) 1-α ) d+α(2-d) 2+d-dα if cn γ(d+2-dα) 1-α + n γ(3-α) 1-α ≤ t.
(Each c design a different constant.)

Now whe choose γ such that 0 < γ < min( 1-α d+2-dα , 1-α 3-α ), then we get :

P DF d0 (Y DF Lx;2n = d 0 ) 1 {X2n=0} ) e -n η . ( 37
)
By our choice of graph D F , there exists C 1 , C 2 > 0 such that for all n ≥ 1:

P DF d0 (Y DF n = d 0 ) ≥ C 1 e -(C2n) α , (38)
≥ e -λ0n α , (39) for some λ 0 > 0.

From (37) and (39), we get that there exists λ 0 > 0 such that Q a.s on the set C| = +∞ and for large enough n, E ω 0 (e -λ0

x;L x;2n >0 L α

x;2n

1 {X2n=0} ) e -n η . ( 40
)
To conclude, it remains only to prove that we can suppress the indicatrice function and that we can extend the inequality (40) to all λ > 0. We explain this in 3 steps.

1. First of all, notice that is is sufficient to prove (3) only for one value of λ. Indeed, let λ > 0, assume that for λ = λ 0 , we have:

E ω 0 (e - λ0
x;Lx;n>0 41) is true because we can replace λ 0 by λ using merely the decrease.

L α x;n ) e -n η . (41) -If λ ≥ λ 0 , (
-If λ < λ 0 , we write

E ω 0 [e -λ x;Lx;n>0 L α x;n ] = E ω 0 [(e - λ0
x;Lx;n>0

L α x;n ) λ λ 0 ] ≤ (E ω 0 [e - λ0
x;Lx;n>0

L α x;n ]) λ λ 0
(Jensen inequality applied to concave function x → x λ λ 0 .) e -n η . 2. To take out the indicatrice function, we use the following lemma: Lemma 3.3. For all m ≥ 0, we have :

P ω 0 ( x L α x;n = m) 2 ≤ 2d(2m + 1) d P ω 0 ( x L α x;2n ≤ 2m et X 2n = 0).
Proof.

[P ω 0 (

x L α x;n = m)] 2 = h∈Bm(C) P ω 0 ( x L α x;n = m; X n = h) 2 = h∈Bm(C) ν(h) × 1/ ν(h) × P ω 0 ( x L α x;n = m; X n = h) 2 ≤ ν(B m (C)) h∈Bm(C) (1/ν(h))P ω 0 ( x L α x;n = m; X n = h) 2
(Cauchy-Schwarz inequality)

≤ 2d(2m + 1) d h∈Bm(C) P ω 0 ( x L α x;n = m; X n = h) × P ω h ( x L α x;n = m; X n = 0)(1/ν(0)) (by reversibility ) ≤ 2d(2m + 1) d h∈Bm(C) P ω 0 ( x L α x;n = m; X n = h) × P ω 0 ( x L α x;[n;2n] = m; X n = h; X 2n = 0) (where L x;[n;2n] = #{i ∈ [n; 2n]; X i = x}) ≤ 2d(2m + 1) d P ω 0 ( x L α x;2n ≤ 2m; X 2n = 0). because { x L α x;n = m et x L α x;[n;2n] = m} ⊂ { x L α
x;2n ≤ 2m}, since for α ∈ [0, 1[, we have :

L α x;2n ≤ (L x;n + L x;[n;2n] ) α ≤ L α x;n + L α x;[n;2n] .
Then we write,

E ω 0 (e -λ0 x L α x;2n 1 {X2n=0} ) = m≥1 e -λ0m P ω 0 ( x L α x;2n = m; X 2n = 0) = (1 -e -λ0 ) m≥1 e -λ0m P ω 0 ( x L α x;2n ≤ m; X 2n = 0), since { x L α x;2n = m} = { x L α x;2n ≤ m} -{ x L α x;2n ≤ m -1}
. Thus, we have, (by lemma 3.3)

E ω 0 (e -λ0 x L α x;2n 1 {X2n=0} ) ≥ (1 -e -λ0 )
≥ m≥1 e -λ1m [P ω 0 ( x L α x;n = m)] 2 (for some λ 1 > 2λ 0 ) ≥ m≥1 e -λ1m -1 × m≥1 e -mλ1 P ω 0 ( x L α x;n = m)
(By Cauchy-Schwarz inequality)

≥ c 0 E ω 0 [e -λ1 x L α x;n ].
3. We can now conclude. By previous inequality and by (40), there exists λ 1 such that :

E ω 0 [e -λ1 x L α x;n ] e -n η .
Then by step 1, we can extend this inequality to all λ 1 .

Finaly we have proved :

Proposition 3.4. Q a.s on |C| = +∞ for large enough n and for all λ > 0 we have, for all α ∈ [0, 1[,

E ω 0 (e -λ x;Lx;n>0 L α x;n ) e -n η ,
where η = d+α(2-d) 2+d(1-α) .

Remark 3.5. 1) If α = 0, we retrieve the Laplace transform of the number of visited points by the simple random walk on an infinite cluster.

2)For α = 1, inequality is satisfied since

x;Lx;n>0 L x;n = n and η = 1 when α = 1.

Lower bound

The proof falls into 4 steps.

1. By concavity of the function x → x α for α ∈ [0, 1], we have :

x;Lx;n>0 L α x;n ≤ N n ( x;Lx;n>0 L x;n N n ) α = N 1-α n n α .
So,

E 0 (e -λ x;Lx;n>0 L α x;n ) ≥ E 0 (e -λn α N 1-α n ) ≥ P 0 ( sup 0≤i≤n D(0, X i ) ≤ m)e -λV (m) 1-α n α .
where V (m) = |B m (C)| stands for the volume of the ball of C centred at the origin with radius m. 2. By proposition 5.2 of [6], we have :

P 0 ( sup 0≤i≤n D(0, X i ) ≤ m) ≥ e -c(m+ n m 2 ) (42)
3. By lemma 5.3 of [6], there exists c > 0 such that Q a.s on |C| = +∞ and for large enough n, V (m) ≥ cm d . 4. So, we deduce, there exists C > 0 such that Q a.s on |C| = +∞ and for large enough n,

E 0 (e -λ x;Lx;n>0 L α x;n ) ≥ e -C(m+ n m 2 +λn α m d(1-α) )
Taking m = n 1-α 2+d(1-α) , we get :

E 0 (e -λ x;Lx;n>0 L α x;n 1

Study of E ω

0 ( L -α z;n ). We assume α > 1/2.

Upper bound

For this functional, one can take for all x ∈ C, B x = L 1 = (Z, E 1 ) ( if we take some L r , we get the same bound). We have :

F ol L 1 (k) = 2k.
We still use a random walk Y which jumps can be represented by: n-1 n n+1

1/3 1/3 1/3

Let P L 1 be the law of random walk Y .

As before, let W, W ′ , W n and W ′ n be the graphs defined respectively by (26) (30) (32) and (33) with D F = L 1 = (Z, E 1 ). With the help of proposition 1.4 in [6] and general properties of isoperimetry on wreath product, we deduce: for all γ > 0, there exists c, β > 0 such that Q a.s on |C| = +∞ we have :

F ol W Wn (k) k k if k < cn γ , k βk d if k ≥ cn γ . ( 43
)
With the same argument as in the upper bound of section 3.2.3, we carry (43) to F ol W ′ W ′ n by rough isometry between graphs W n and W ′ n . We get: for all γ > 0, there exists β > 0 such that for all c > 0, Q a.s on |C| = +∞ we have:

F ol W ′ W ′ n (k) k k if k < cn γ , k βk d if k ≥ cn γ . ( 44
)
In order to get an upper bound of Pω o (Z 2n = o), let again:

τ n = inf{s ≥ 0; Z s ∈ V (W ′ n )}. We still have Pω o (Z 2n = o) = Pω o (Z 2n = o and τ n > n).
We use the same way to get the upper bound from (44). Inequality (44) implies:

∀k ≥ 0 F ol W ′ W ′ n (k) J N (k) = 1 if k < cn γ , N βd ′ k d if k ≥ cn γ , (45)
where N ≤ cn γ . J N is increasing and we can compute J -1 N :

J -1 N = inf{x; J N (x) ≥ y} =    cn γ if 1 ≤ y < N cn dγ , c ln(y) ln(N ) 1/d if N cn dγ ≤ y. Remark 3.7. Let J (k) = k k if k < cn γ , k βk d if k ≥ cn γ . (46) Inequality (44) can be read F ol W ′ W ′ n (k) J (k).
J is increasing but the form of J does not enable us to compute an inverse and for this reason we use J N for the lower bound of F ol W ′ W ′ n (k) instead of J . C and L 1 have bounded valency so we still have inf

V (W ′ ) m ≥ 2 > 0 and inf E(W ′ ) ã > 0.
Thus with the same tools as in section 3.2.3 we get, there exists constants c 1 , c 2 and c 3 > 0 such that Pω o (Z 2n = o and τ n > n) u(n) where u is solution of the differential equation:

u ′ = - u c2(J -1 N (c3/u)) 2 , u(0) = 1/2.
Solving this equation, we obtain:

u(t) = e -ct/n 2γ if t ≤ t 0 := cn γ(d+2) ln(N ), e -( c(ln(N ) 2/d (t-t0)+ln(1/u(t0)) d+2 d ) d d+2 if t > t 0 .
Chosing γ < 1 d+2 and taking N = cn γ , we obtain in t = n: Q a.s on the event |C| = +∞ and for large enough n,

Pω o (Z 2n = o) e -n d d+2 ln(n) 2 d+2 .
So with proposition 3.1, we deduce :

Proposition 3.8. There exists a constant C > 0 such that Q a.s on |C| = +∞ and for large enough n,

E ω 0 ( x;Lx;2n>0 P L 1 0 (Y Lx;2n = 0) 1 {X2n=0} ) ≤ e -Cn d d+2 ln(n) 2 d+2 . ( 47
)
For the walk Y, we know that there exists c 0 > 0 such that P

L 1 0 (Y n = 0) ∼ c0 n 1/2 . In particular, ∃c 1 > 0 ∀n ≥ 1 P L 1 0 (Y n = 0) ≥ c 1 n α , (48)
with c 1 ≤ 1. So, for α > 1/2 we find A > 0 and c 2 > 0 such that

∀n ≥ 1 P L 1 0 (Y n = 0) ≥ 1 n α if n ≥ A, c2 n α if n < A, (49)
with c 2 ≤ 1. If we directly use the lower bound (49) in (47) at time L x;2n , it appears a supplementary factor c #{x; 0<Lx;2n<A} 2 on which we do not have control. So we put :

N n,2 = #{x; L x;n ≥ 2},
which is the number of visited points at least twice by the walk X. And for ε 1 , ε 2 > 0, consider the following events :

A 1 = {N 2n ≤ ε 1 n d d+2 ln(n) 2 d+2 }, A 2 = {N 2n ≥ ε 1 n d d+2 ln(n) 2 d+2 and N 2n,2 ≥ ε 2 n d d+2 ln(n) 2 d+2 }, A 3 = {N 2n ≥ ε 1 n d d+2 ln(n) 2 d+2 and N 2n,2 ≤ ε 2 n d d+2 ln(n) 2 d+2 }.
We have

E ω 0 ( x; Lx;2n>0 L -α x;2n 1 {X2n=0} ) = E ω 0 ( x; Lx;2n>0 L -α x;2n 1 {X2n=0} 1 A1 ) (50) + E ω 0 ( x; Lx;2n>0 L -α x;2n 1 {X2n=0} 1 A2 ) + E ω 0 ( x; Lx;2n>0 L -α x;2n 1 {X2n=0} 1 A3 ).
Let us examin these three 3 terms.

1. For the term corresponding to A 1 , we write :

E ω 0 ( x; Lx;2n>0 L -α x;2n 1 {X2n=0} 1 A1 ) = E ω 0 ( x; Lx;2n>0 c 1 L α x;2n × x; Lx;2n>0 1 c 1 × 1 {X2n=0} 1 A1 ) ≤ E ω 0 ( x;Lx;2n>0 P L 1 0 (Y Lx;2n = 0) × ( 1 c 1 ) N2n ×1 {X2n=0} 1 A1 ) (par 48) ≤ E ω 0 ( x;Lx;2n>0 P L 1 0 (Y Lx;2n = 0)1 {X2n=0} ) ×( 1 c 1 ) ε1 n d d+2 ln(n) 2 d+2 ≤ e -(C+ε1 ln(c1))n d d+2 ln(n) 2 d+2 .
(by proposition 3.8) Now, choosing ε 1 small enough ( recall that ln(c 1 ) ≤ 0), we deduce that there exists a constant C 1 > 0 such that Q a.s on |C| = +∞, we have,

E ω 0 ( x; Lx;2n>0 L -α x;2n 1 {X2n=0} 1 A1 ) ≤ e -C1n d d+2 ln(n) 2 d+2 . (51)
2. For the second term, we notice that on the event A 2 the product x; Lx;2n>0 L -α x;2n

is less than (1/2) ε2n d d+2 ln(n) 2 d+2 . Thus there exists a constant C 2 > 0 such that, E ω 0 ( x; Lx;2n>0 L -α x;2n 1 {X2n=0} 1 A2 ) ≤ e -C2n d d+2 ln(n) 2 d+2 . (52)
3. For the last term, we use the following lemma: Lemma 3.9. There exists ε ′ > 0 such that for all ε > 0, there exists a constant C 3 > 0 such that, for all n, N ≥ 0,

P ω 0 (N n ≥ εN et N n,2 ≤ ε ′ N ) ≤ e -C3N . (53)
Proof.

• Let τ 0 = 0 and for k ≥ 1 let,

τ k = min{s ≥ τ k-1 ; X s ∈ {X 0 , X 1 , ..., X s-1 } }.
The τ k represent instants when the walk X visits a new point. Consider now, the variables ǫ k defined by :

ǫ k = 1 if X τ k = X τ k +2 , 0 otherwise. ( 54
)
These variables have the following interpretation, ǫ k is equal to 1 only when the new visited point X τ k is immediatly re visited after a backward and foward. The ǫ k are not independent but their laws are all some Bernouilli with different parameters. Besides, these parameters have a same lower bound δ > 0, since the graph C g has bounded valency.

• Consider the following filtrations, G m = σ(X j ; 0 ≤ j ≤ m), F m = σ(X j ; 0 ≤ j ≤ τ m ). ǫ k are G 2+τ k measurable and so F k+2 measurable. For all λ > 0 and for all L > 0, we can write, Last inequality comes from the fact that the graph C g has bounded valency, so in each point x the probability to do a backward and foward is greater than δ 2 (with δ ≥ 1/2d).

• So, we deduce from (56) and (57) that, E ω 0 (e -λǫL |F L ) ≤ 1 + (e -λ -1)δ 2 . Iterating (55), we get, E ω 0 (e -λ L k=1 ǫ k ) ≤ (1 + (e -λ -1)δ 2 ) ⌊L/2⌋ , (58) where ⌊a⌋ stands for the whole number portion of a. Let: a λ =ln(1 + (e -λ -1)δ 2 ) > 0.

By Bien-aymé inequality, we deduce,

P ω 0 ( L k=1 ǫ k ≤ ε ′ L) ≤ e ε ′ λL-a λ ⌊L/2⌋ .
Using ⌊L/2⌋ for L ≥ 2, L ≤ 3, we get :

P ω 0 ( L k=1 ǫ k ≤ ε ′ L) ≤ e -⌊L/2⌋(a λ -3λε ′ ) .
Note that this last inequality is still valid for L = 1. Fix λ > 0, ( by example λ = 1) then we can choose ε ′ small enough such that a λ -3ε ′ > 0. We deduce the existence of constant b such that :

P ω 0 ( L k=1 ǫ k ≤ ε ′ L) ≤ e -bL . (59)
• Now, notice that

{N n ≥ εN et N n,2 ≤ ε ′ N } ⊂ { εN k=1 ǫ k ≤ ε ′ N }.
Indeed, first if N n ≥ εN that means that at least εN new points have been visited. Secondly if there are less than ε ′ N points visited more than twice then there are less than ε ′ N points which have been immediatly visited after their first visit. Finaly we have:

P ω 0 (N n ≥ εN and N n,2 ≤ ε ′ N ) ≤ e -εbN .
We can now get an upper bound of the term corresponding to A 3 The product is less than 1, so we can write:

E ω 0 (
x; Lx;2n>0 L -α x;2n 1 {X2n=0} 1 A3 ) ≤ P 0 (A 3 )

Let ε 1 small enough satisfying the first point (event A 1 ), lemma 3.9 with ε = ε 1 give us the existence of ε ′ such that (53). Then we take ε 2 = ε ′ and we deduce there exists a constant C 3 > 0 such that, To get the upper bound of the second point of Theorem 1.3, it remains to take out the indicatrice 1 {X2n=0} . We use the same way as in the section 3.2.3. We prove: Lemma 3.11. For all m ≥ 0, we have: Then by using (42), we deduce : Remark 3.14. In the proof of the lower bound, we have only used the assumption that α ≥ 0, so this bound is valid for all α ≥ 0.

P ω 0 (A 3 ) ≤ e -C3n

Definition 2. 1 .

 1 The wreath product of A and (B z ) z∈A is the graph noted by A ≀ B z such that:V (A ≀ B z ) = {(a, f ); a ∈ A and f : A → ∪ z B z with supp(f ) < ∞ and ∀z ∈ A, f (z) ∈ B z } and E(A ≀ B) = { (a, f )(b, g) ; (f = g and (a, b) ∈ E(A))or (a = b and ∀x = a f (x) = g(x) and f (a), g(a) ∈ E(B a ))}

1 .

 1 Construction of the graph and preliminary notions and lemmas. Let A ′ = (Z, E(Z)) where E(Z) = {(x, y); |x -y| = 1} and (B ′ z ) z∈Z be the Cayley graph of the groups ( Z l(z)Z , +) with { 1} as generators where l

C 1 =

 1 e∈N SU (η,b) w(e) , C 2 = e∈S e U (η,b);e removed at the end of the process w(e), et C 0 = e∈E(ΓU ));e removed at the end of the process w(e).

  to point x.. These pictures are represented at step 0 on the left side and at step k on the right side.

1 ↓= 2 ↓=

 12 {e ∈ L ↓ , e coming from a multidimensional edge of K U k , associated to a point x, of dim ≥ η x /10}, and L {e ∈ L ↓ , e coming from a multidimensional edge of K U k , associated to a point x, of dim < η x /10}.

  because edges of L ↓ , are edges leaving L at step k.

  , b) since if it was S e U (η, b), it would link two points S p U (η, b) and in particular points of D 1 would have been S p U (η, b), then S p U (η/10, b/10) and so would not have been removed. In consequence : e∈F2 w(e) ≤ e∈N S e (η,b) w(e) = C 1 . C. Besides, all removed edges S e U (η, b) are in some F ′ i with i ≥ 3, so C 2 = e removed at the end of the process e∈S e U (η,b)

  and a is neighbor of b in A. (ii) either a = b and ∀x = φ(a) f (x) = g(x) and f (φ(a)) is neighbor of g(φ(a)) in B.

  exists a not empty subgraph Γ ′ of Γ U such that all edges are S U (1 -9+ǫ 10 , a 10 ) M satisfactory in respect to Γ ′ .

C 1 =

 1 e∈N SU (1-ǫ,a)M w(e) , C 2 = e∈S e U (1-ǫ,a)M;e removed at the end of the process w(e), and C 0 = e∈E(ΓU ));e removed at the end of the process w(e).

  e∈F2 w(e) ≤ e∈N S e (a,b) w(e) = C 1 .

3.2. 1 .

 1 Percolation context. Consider the graph L d = (Z d , E d ) where E d are the couple of points of Z d at distance 1 for the N 1 norm. Now pick a number p ∈]0, 1[. Each edge is kept [resp removed ] with probability p [resp 1p] in an independant way. We get a graph ω and we call C the connected component that contains the origin and C n the connected component of C ∩ [-n, n] d that contains the origin.

  there exists c = c(p, d, α, λ) > 0 such thatu(2n) ≤ e -cn η , with η = d+α(2-d)2+d(1-α) . So, Q a.s on the set |C| = +∞, and for large enough n (which depends on the cluster ω), Pω o (Z 2n = o) e -n η . By proposition 3.1, we deduce that Q a.s on the event |C| = +∞ and for large enough n,

  ≤ 2m; X 2n = 0) (we add only the even m )≥ (1e -λ0 ) m≥1 1 2d(2m + 1) d e -2λ0m [P ω 0 ( x L α x;n = m)] 2

)

  {Xn=0} ) ≥ e -cn η , with η = d+α(2-d) d(1-α)+2 and for all α ∈ [0, 1]. Hence, we have proved : Proposition 3.6. For all α ∈ [0, 1], Q a.s on |C| = +∞ and for large enough n, e -cn η , with η = d+α(2-d) d(1-α)+2 . Thus, the first assertion of Theorem 1.3 comes from proposition 3.4 and proposition 3.6.

E ω 0

 0 (e -λ L k=1 ǫ k ) = E ω 0 (e -λ L-2 k=1 ǫ k E ω 0 (e -λ(ǫL-1+ǫL) |F L ) ) ≤ E ω 0 (e -λ L-2 k=1 ǫ k E ω 0 (e -λǫL |F L ) ). (55)• For the term E ω 0 (e -λǫL |F L ), we have:E ω 0 (e -λǫL |F L ) = e -λ P ω 0 (ǫ L = 1|F L ) + P ω 0 (ǫ L = 0|F L ) = 1 + (e -λ -1)P ω 0 (ǫ L = 1|F L ). (56)Now, we want a lower bound of P ω 0 (ǫ L = 1|F L ). We have successively:P ω 0 (ǫ L = 1|F L ) = P ω 0 (ǫ L = 1|X τL ) ( Markov property) = x; P ω 0 (Xτ L =x)>0 1 {Xτ L =x} P ω 0 (ǫ L = 1|X τL = x) ≥ δ 2 . (57)

  deduce from (51) (52) and (60), the following property.Proposition 3.10. Q a.s on |C| = +∞ and for large enough n, for all α > 1/2,

1 (

 1 x;n ) = m) 2 ≤ 2d(2m + 1) d P ω 0 ( x ln(L x;2n ) ≤ 2m et X 2n = 0).The proof is similar to lemma 3.3. We use in particular :ln(L x;2n ) ≤ ln(L x;n + L x;[n;2n] ) ≤ ln(L x;n ) + ln(L x;[n;2n] 1 {X2n=0} ) = E ω 0 (e -α x ln(Lx;2n) 1 {X2n=0} ) = m≥1 e -αm P ω 0 ( x ln(L x;2n ) = m; X 2n = 0) = (1e -α ) m≥1 e -αm P ω 0 ( x ln(L x;2n ) ≤ m; X 2n = 0). ≥ (1e -α ) m≥1 e -2αm P ω 0 ( x ln(L x;2n ) ≤ 2m; X 2n = 0) ≥ (1e -α ) m≥1 1 2d(2m + 1) d e -2αm [P ω 0 ( x ln(L x;n ) = m)] 2(by lemma 3.11)≥ m≥1 e -α1m [P ω 0 ( x ln(L x;n ) = m)] 2 (for some α 1 > 2α ) x;n ) = m)(by Cauchy-Schwarz inequality)≥ c E ω 0 [e -α1 x ln(Lx;n) ] = cE ω 0 ( x L -α1 x;n ).So, with this last inequality and with proposition 3.10, we obtain the expected upper bound for some value α 1 : this inequality at point α 1 , we extend this relation for all α > 1/2. Let α > 1/2. -If α ≥ α 1 , we can replace in (61) α 1 by α, by monotony in α.-If α < α 1 , we write Jensen inequality to concave function x → x α α 1 .) e -n η .So we have proved :Proposition 3.12. Q a.s on the set |C| = +∞ and for large enough n, for all α > 1/2, e -αNnln( n Nn ) .On the event { sup 0≤i≤n D(0, X i ) ≤ m}, it comes that :N n ≤ |B m (C)| ≤ c m d , Since function x → ln(x)x is decreasing on [e, +∞], if we choose m such thatn cm d ≥ e,(62)then we can write : E 0 ( x;Lx;n>0 L -α x;n ) ≥ e -αcm d ln( n cm d ) P 0 ( sup 0≤i≤n |X i | ≤ m).

  x;n ) ≥ e -αcm d ln( n cm d ) e -c(m+ n m 2 ) . Taking m = ( n ln(n) ) 1 d+2, inquality (62) is well satisfied for large enough n. Finaly, for large enough n we obtain, For all α > 1/2, Q a.s on the set |C| = +∞ and for large enough n

  , this means that it remains point(s) not removed. ie: ∃k 0 ∈ N such that all vertices of the graph we get at step k 0 , are S p In order to see this, let us introduce an orientation on edges removed: if L and Q are points of the graph, we orient the edge from L to Q if L is removed before Q, and we choose an arbitrary orientation if they are removed together. We denote by L

		U k 0	(η/10, b/10), donc S p U (η/10, b/10).
	↓	the set of edges leaving the point L and L ↑	the set of edges ending at point L,
	both at step 0.
	Sublemma 2.4. Let k ∈ N and let L stands for a point of the graph Γ U (satisfying
	assumptions of lemma 2.3), removed after k + 1 steps. Suppose that L is initially S p U (η, b), then e∈L ↓ w(e) ≤ 1 ↑ 2 e∈L w(e).

A. By using general results on wreath product, see [START_REF] Ershler | Isoperimetry for wreath products for markov chains and multiplicity of self intersection of random walk[END_REF], [START_REF] Ershler | On isoperimetric profiles of finitely generated groups[END_REF] and [6], we have :

B. By proposition 1.4 of [6], we get: for all γ > 0, there exists β > 0 such that for all c > 0, Q a.s for large enough n, we have :

C. We want to carry (31 ) on F ol C g ≀≀DF C g n ≀≀DF . Let δ a imaginary point and consider the following graphs:

and

defined by :

∪ {δ} and set of edges are given by

Let respectively d and d ′ be the distances on W and W ′ , given by edges of these graphs. W n are W ′ n are rough isometric with constants independant of n. With the notations of definition 3.7 in [START_REF] Woess | Random walks on infinite graphsand groups[END_REF], we have A = 3 and B = 0. Indeed, consider id

Thus the respective Dirichlet forms E and E ′ for simple random walks on W n and W ′ n satisfy: there exists c 1 , c 2 > 0 such that for all f :

So the second assertion of Theorem 1.3 follows from propositions 3.12 and 3.13.

Acknowledgment

The author would like to thank Pierre Mathieu and Anna Erschler for usefull remarks.