Cyril Roberto

Ellen Saada

Guilhem Semerjian D'

Arturo Barbara

Bohdan, Clément, Clément, Côme Benjamin

Cyril

Enzo David

Fabio

Hiroshi, Houzhi, Junchao Guillaume

Laure

Luca

Marc Mi-Song Lucas

Rémy, S. (qui voulait Mina Sothea

Ziad Merci

Keywords: kinetically constrained models, bootstrap percolation, stochastic models in random environments, glassy dynamics, interacting particle systems, hitting times, relaxation time, metastability iii modèles aux contraintes cinétiques, percolation bootstrap, modèles stochastiques en environnement aléatoire, dynamique vitreuse, systèmes de particules en interaction, temps d

Cette thèse représente la conclusion de mes trois ans de doctorat ; trois ans que je considère comme une très belle période de ma vie, en grande partie grâce à certaines personnes que j'aimerais mentionner. Je tiens tout d'abord à remercier ma directrice de thèse, Cristina Toninelli, qui m'a soigneusement dirigé, sachant quand il fallait être présente et quand il fallait me laisser plus de liberté. Merci pour nos discussions, la relecture de toute mes notes, les conseils, et ton aide sur tout ce dont j'avais besoin.

I would also want to thank Fabio Martinelli for the time in Rome and in Paris,

Glass is a material widely present in our daily life, and yet a complete microscopic understanding of its state of matter and its formation is still out of reach for condensed matter physicists [START_REF] Berthier | Dynamical heterogeneities in glasses, colloids, and granular media[END_REF][START_REF] Biroli | Perspective: The glass transition[END_REF]. At the heart of this puzzle lies the fact that glasses display properties of both solids and liquids despite their rigidity, the arrangement of their atoms and molecules is disordered, like that of a liquid. This seems to be a contradiction: if the arrangement of the molecules is amorphous, why would they stay in a xed position and keep the glass rigid?

The liquid-glass transition occurs when a liquid is cooled below its melting temperature very rapidly, preventing the nucleation of the ordered crystal structure. Roughly speaking, the liquidcrystal transition is avoided since molecules do not have enough time to organize themselves and form the ordered crystal structure. In this way the liquid enters a metastable supercooled phase in which the molecules move slower and slower as the temperature is decreased until they get trapped in the structureless glass state. Even though this state is not thermodynamically stable, relaxation times are out of reach in any reasonable experiment and the system gets stuck in the amorphous solid glass state. Experiments show that the slowing down of dynamics in the vicinity of the liquid-glass transition is extremely sharp relaxation times can increase by 14 orders of magnitude upon a small decrease in temperature. This dramatic growth of time scales is related to the fact that when the temperature is lowered the density is augmented: molecules tend to obstruct one another and the motion becomes very cooperative, giving rise to large blocked structures. There is indeed a clear coexistence of fast and slow regions, a phenomenon that is called dynamical heterogeneities.

Kinetically constrained models

One attempt to explain the phenomenology described above relies on the idea that the glass transition is a purely dynamical phenomenon, and the static interactions play a minor role (see [START_REF] Sivert | Dielectric relaxation of polar liquids[END_REF][START_REF] Anderson | Lectures on amorphous systems[END_REF][START_REF] Garrahan | Geometrical explanation and scaling of dynamical heterogeneities in glass forming systems[END_REF]). This approach leads to the study of kinetically constrained models (KCMs), which is a family of interacting particle systems. These models are Markov processes constructed in such a way, that they have a very simple non-interacting equilibrium, and local kinetic constraints that freeze sites with a dense neighborhood. These two properties imitate the dynamical aspect of the glassy behavior when static interactions do not play an important role, a coarse grained version of the glass will look like a non-interacting system from the thermodynamic point of view, but small regions will not be able to equilibrate when their 1. INTRODUCTION local environment is dense. The validity of this framework, that the dynamical eect captures the central mechanism behind the liquid-glass transition, is still under debate; but still, both numerical and theoretical studies conrm that KCMs show indeed a behavior typical of glassy phenomenology, including super-Arrhenius slow down [START_REF] Fredrickson | Kinetic Ising model of the glass transition[END_REF][START_REF] Sollich | Glassy dynamics in the asymmetrically constrained kinetic ising chain[END_REF], non-trivial spatio-temporal uctuations corresponding to dynamical heterogeneities [START_REF] Garrahan | Geometrical explanation and scaling of dynamical heterogeneities in glass forming systems[END_REF], aging phenomena [START_REF] Sollich | Glassy dynamics in the asymmetrically constrained kinetic ising chain[END_REF][START_REF] Faggionato | Aging through hierarchical coalescence in the east model[END_REF] and ergodicity breaking transition [START_REF] Toninelli | A new class of cellular automata with a discontinuous glass transition[END_REF]. KCMs live on a (possible innite) graph G, where each vertex has a state taken from a set S. That is, the state space of the Markov process is Ω = S G . We will call the vertices of G sites, and an element of Ω will be called conguration. The equilibrium is non-interacting, i.e., an independent product measure µ = x∈G µ x , where µ x , for each site x, is a measure on S. In the models that we will study all these measures are equal. µ x is a measure on the space of states, thus it operates on functions from S to R. It will be useful to apply µ x to functions on the entire conguration space Ω, by xing the conguration at the sites G \ {x} and integrating over the state at x. This way we obtain another function on Ω that does not depend on the conguration at x. It could also be thought of as the expected value conditioned on the conguration outside x.

Before dening the KCM, we rst consider the unconstrained model on each site there is a Poisson clock, ringing at rate 1. Whenever the clock rings, the site forgets its state, and chooses a new one at random, according to the equilibrium measure. This description of the process is called the graphical construction (see [START_REF] Thomas | Interacting particle systems[END_REF]). Equivalently, we can describe this dynamics using the generator of the Markov semi-group. The generator is an operator dened on local functions, i.e., functions from Ω to R that depend only on the states of nitely many sites. For the unconstrained dynamics,

L unconstrained f = x∈G (µ x f -f ) .
Let us now add the constraints for every site x, we dene its constraint c x . It equals either 0 or 1, and depends on the conguration outside x, i.e., the states of the vertices in G \ {x}.

Then the generator of the associated KCM is dened by

Lf = x∈G c x (µ x f -f ) . (1.2.1)
In the graphical construction, we will take the same Poisson clocks with rate 1, but unlike the unconstrained case, we only update the state of a vertex when the constraint is satised, i.e., when c x = 1. It is important to stress that once the constraint is satised, the new state that we give to the site is chosen randomly according to the measure µ x , and it does not depend on the conguration of the system. This assures that the model is indeed reversible with respect to the (not necessarily unique) invariant measure µ.

There are many KCMs with dierent possible G, S, µ and c x . A common choice for S is {0, 1} and µ x = Ber (1 -q) for some parameter q ∈ [0, 1]. These are called 0-1 spin models, and sites are said to be empty or occupied if their state is 0 or 1 respectively. In the 0-1 spin models that we discuss, the constraint is a decreasing function of the conguration, that is, more empty sites could only help satisfying the constraint.

In order to have a more concrete example in mind, we will introduce now the Fredrickson-Andersen 2 spin facilitated KCM on Z 2 (FA2f on Z 2 ), see [START_REF] Fredrickson | Kinetic Ising model of the glass transition[END_REF]. It is a 0-1 spin model on the graph G = Z 2 , with the constraint

c x (η) =    1
y∼x (1 -η y ) ≥ 2 0 otherwise, i.e., the constraint is satised at x if at least 2 of its neighbors are empty. This is an example of a homogeneous KCM, meaning that the constraint is translation invariant. The dynamics described above, in which sites are resampled at a certain rate, is called Glauber dynamics. For systems in which the total number of occupied sites is conserved we introduce Kinetically Constrained Liquid Gas (KCLG) models. They evolve according to the Kawasaki dynamics, in which sites exchange their state rather than resampling it. In this case the constraint will be dened for edges of the graph rather than vertices. We will study such a model in chapter 5.

Ergodicity and the bootstrap percolation

From now on we will focus on 0-1 spin KCMs, and assume that the constraint is decreasing in the conguration. The rst question we ask about a KCM is whether or not it is ergodic, i.e., if it must equilibrate eventually (in the L 2 (µ) sense). One possible obstacle that could make the system non-ergodic is the existence of a large cluster of occupied sites, each of which has many neighbors inside the cluster, such that none could ever be emptied. In FA2f on Z 2 , for example, two innite consecutive rows of occupied sites will form such a cluster each site only has one neighbor outside the cluster, so it could never have the two empty neighbors needed in order for the constraint to be satised. In order to identify these blocked clusters, we introduce the bootstrap percolation associated with the KCM.

The bootstrap percolation is a deterministic dynamics on Ω in discrete time, where at each time step t empty sites stay empty, and an occupied site x becomes empty if the constraint is satised, namely η x (t) =    1 η x (t -1) = 1 and c x (η (t -1)) = 0 0 otherwise. (1.3.1) In other words, whenever the constraint is satised we empty the site, and never ll it again. This way, if we wait for long enough, only the blocked clusters will remain occupied. The initial conguration for the bootstrap percolation is random according to the measure µ (which is the 1. INTRODUCTION equilibrium of the KCM), so it will give us information on the KCM starting from equilibrium. Going back to the example given in the previous paragraph, the blocked cluster described for FA2f in Z 2 has µ-probability 0 to appear in the initial conguration.

The bootstrap percolation is monotone, since sites that become empty could never be lled.

Therefore, one can dene a limiting conguration at time ∞, saying if a site is emptiable, or forever occupied. Moreover, there exists a critical probability above which all sites are emptiable with probability 1, and below which some sites could remain occupied forever: q c = inf {q : µ(all sites are emptiable) = 1} .

Proposition 1.3.1 (Proposition 2.5 of [START_REF] Cancrini | Kinetically constrained spin models[END_REF]). The KCM is ergodic if and only if all sites are emptiable for the bootstrap percolation with probability 1. In particular, it is ergodic for q > q c and not ergodic for q < q c . For the FA2f on Z 2 model introduced above, it is shown in [START_REF] Aernout | Proof of Straley's argument for bootstrap percolation[END_REF] that q c = 0, so all sites are emptiable with probability 1 whenever q > 0. For q = 0, however, all sites are occupied in the initial state, so the constraint is never satised, and all sites remain occupied forever.

In order to understand this transition, we can try to study the bootstrap percolation in nite regions. Definition 1.3.2. Consider a set V of sites and a conguration η ∈ Ω. The span of V for η is the set of sites that are emptiable for the conguration which equals η on V and 1 outside V . If V is contained in its span for η we say that it is internally spanned for η.

The scaling of the probability that the box [L] 2 ⊂ Z 2 is internally spanned has been studied in [2, [START_REF] Holroyd | Sharp metastability threshold for two-dimensional bootstrap percolation[END_REF], nding that for small q it becomes very close to 1 when L passes the critical scale e π 2 18 1 q . Remark 1.3.3. The notation adopted here it the one usually used in the study of KCMs, which is not necessarily the more common in the bootstrap percolation community. For example, empty and occupied sites are often referred to as infected and healthy by people studying the bootstrap percolation; and their label (0 or 1) is the opposite of the one dened for KCM. Slightly less confusing dierences are that the parameter q is usually called p, and the naming of the constraints is not the same, e.g., FA2f introduced above is called the 2-neighbor bootstrap percolation.

Time scales

An important aspect of both the bootstrap percolation and KCMs is the divergence of time scale around criticality. For the bootstrap percolation, the most natural time is the time at which a site becomes empty. In the KCM sites are emptied and lled many times, so the relevant scale is when a site becomes empty for the rst time (see, e.g., [START_REF] Cancrini | Kinetically constrained spin models[END_REF]). Since the bootstrap percolation empties all possible sites, we can bound from below (with high probability) the rst time a site is empty for the KCM by its emptying time for the bootstrap percolation. The other direction, however, is not always true.

If we are interested in understanding the time that it takes for the system to forget its initial state, a good candidate will be the time scale at which correlation is lost if we take some function f : Ω → R and evaluate it at time 0 and at time t starting from equilibrium, will these two values be (more or less) independent? The time scale on which this correlation decays may depend on f , and taking the worst possible (local) f gives the relaxation time. In homogeneous KCMs this scale often describes also the decay of typical observables (see [START_REF] Marêché | Exact asymptotics for Duarte and supercritical rooted kinetically constrained models[END_REF]), but we will see here that in systems that are not homogeneous this will no longer be the case.

Universality results for general homogeneous models in two dimensions have been studied recently for the bootstrap percolation in a series of works that provide a good understanding of their behavior [6, [START_REF] Bollobás | Universality of two-dimensional critical cellular automata[END_REF][START_REF] Bollobás | Monotone cellular automata in a random environment[END_REF][START_REF] Hartarsky | U-bootstrap percolation: critical probability, exponential decay and applications[END_REF]. Inspired by the tools developed for the bootstrap percolation, universality results on the KCMs could also be obtained for systems with general translation invariant constraints [START_REF] Martinelli | Towards a universality picture for the relaxation to equilibrium of kinetically constrained models[END_REF][START_REF] Martinelli | Universality results for kinetically constrained spin models in two dimensions[END_REF].

Random environments

In the example that we have seen, of FA2f on Z 2 , the graph G and the constraints c x have a very simple form. This describes a rather non-realistic physical system, but still, the common belief is that a big part of the behavior of a system is determined by a few important features. This means that as long as we include these features, a simplied model could still explain observed phenomena. This idea of universality, in the case of KCMs, is supported by the results of [START_REF] Martinelli | Towards a universality picture for the relaxation to equilibrium of kinetically constrained models[END_REF][START_REF] Martinelli | Universality results for kinetically constrained spin models in two dimensions[END_REF]. They show that as long as the constraints are local and translation invariant, there are just a handful of possible ways in which time scales diverge near criticality.

However, one of the important features that is required for these universality results to hold is the homogeneity of the system; and though many systems are indeed homogeneous, when materials have pollution or defects that appear during their preparation non-homogeneity could play an important role. Such systems are often modeled by a dynamics on a frozen random environment, which, in the case of KCM and bootstrap percolation, will mean that the graph G, the constraints c x , or the local equilibrium measures µ x are random.

The bootstrap percolation has been studied in many dierent random environment, e.g., the polluted lattice [START_REF] Gravner | Bootstrap percolation in a polluted environment[END_REF][START_REF] Gravner | Polluted bootstrap percolation with threshold two in all dimensions[END_REF], Galton-Watson trees [START_REF] Bollobás | Bootstrap percolation on Galton-Watson trees[END_REF], random regular graphs [START_REF] Balogh | Bootstrap percolation on the random regular graph[END_REF][START_REF] Janson | On percolation in random graphs with given vertex degrees[END_REF] and the Erd®s-Rényi graph [START_REF] Janson | Bootstrap percolation on the random graph G n[END_REF]. KCMs in random environments have not been studied mathematically (to my knowledge), but they have been treated in the physics literature, see [START_REF] Schulz | Glass transition in a modied Fredrickson model[END_REF][START_REF] Willart | Evidence of a dynamical length scale in the f-spin frustrated kinetic Ising model[END_REF].

KCMs in random environments contain three types of randomness the disorder (also called quenched variables), the initial state, and the evolution of the Markov process. Throughout this thesis we will denote by ν the measure of the disorder (namely the randomness of the environment); and use the letter ω when we want to refer to a specic realization of the quenched variables. The initial state will always be sampled from the equilibrium measure µ and we will use the letter η to represent a conguration of the system. Finally, the randomness 1. INTRODUCTION of the Markov process will be denoted by P η and E η when starting from a given conguration η, or P µ and E µ when starting from equilibrium.

Overview of the results

This monograph covers two main problems the behavior of time scales for KCMs and bootstrap percolation in random environments (chapters 2,3 and 4), and the relaxation time of the Kob-Andersen model (chapter 5).

We will start with chapter 2, introducing the tools that will be required in the study of KCMs in random environments. KCMs are not attractive adding empty sites could allow other sites to update and become occupied. This excludes techniques such as monotone coupling and censoring, which are used in the study of attractive Glauber dynamics like the Ising model or the contact process. This is the reason that in the homogeneous case most of the information we have on the time scales of KCMs comes from the relaxation time, which is given by a variational principle, and will be introduced in the rst part of chapter 2. However, we will see in chapters 3 and 4 that in non-homogeneous models the relaxation time fails to describe the actual behavior of the system. The reason is that the variational formula dening it focuses on the worst observable, and when the system is not homogeneous it will be determined by the slowest possible regions. The goal of the rest of chapter 2 will be to develop new variational tools that will not share this problem.

In chapter 3 we will apply these tools to several models on Z d in which the constraints are random. We will compare dierent time scales of the KCM and the associated bootstrap percolation, and see that the random environment induces many interesting phenomena. For example, it is possible for the relaxation time to be innite, whereas the distribution of the emptying time of a site decays exponentially fast. In another model we will see that the divergence of the emptying time of a site is polynomial with a random power that may depend on the environment. Chapter 4 will discuss KCMs and bootstrap percolation on a random graph, the Galton-Watson tree. Already for the bootstrap percolation we will see an intriguing behavior, that for dierent types of Galton-Watson trees the proportion of empty sites could decrease in many strange ways, staying almost xed for long time intervals (that diverge when approaching q c ), and jumping down rapidly between them.

Chapter 5 presents an analysis of the relaxation time of the Kob-Andersen model. This model is homogeneous, but unlike the models discussed before it is of Kawasaki type particles are not created and destroyed, but jump from one site to the other. We prove a diusive scaling in a box of side L the relaxation time is proportional to L 2 , whereas previous studies only showed a scaling of L 2 (log L) 4 [20].

List of conventions and notation

To make the reading of this thesis easier, I list here the notation that have been introduced above and will be used in the following.

• G the graph on which the model lives. Sometimes we use G also for the vertices of the graph.

• (S, µ 0 ) the space of values that a site could have and its equilibrium probability. In most cases S = {0, 1} and µ 0 = Ber(1 -q). • (Ω, µ) the state space of the Markov process and its equilibrium probability. Ω = S G and µ = x∈G µ x .

• η a generic conguration (element of Ω). η x (t) is the occupation value of the site x at time t, and η x is the conguration obtained from η by ipping the site x.

Warning: we will sometimes need to refer to a sequence of congurations. In these cases we will denote the sequence by η 1 , η 2 , . . . , and the occupation of a site x by, e.g., (η 1 ) x .

• c x the constraint at the site x.

• L the generator of the Markov process (see equation (1.2.1)).

• P, E the measure of the Markov process. We use P η and E η when starting from a given conguration η, or P µ and E µ when starting from equilibrium.

• ν the measure of the disorder.

• ω generic realization of the disorder. The law of ω is ν.

• µ V f expectation of f with respect to the occupation values in V ⊆ G. • ∇ x f (η) = f (η x ) -f (η). CHAPTER 2

Variational tools

This chapter will introduce the variational tools that will be used afterwards in the analysis of KCMs. In the rst section we dene the spectral gap and see some basic properties related to it. More details could be found, for example, in [START_REF] Levin | Markov chains and mixing times[END_REF]. The second section describes the tools presented in [START_REF] Shapira | Kinetically constrained models with random constraints[END_REF] in order to study hitting times of reversible Markov processes, and in particular KCMs. Finally, the third section concerns with the time spent in a certain event before hitting another event.

Spectral gap and relaxation time

The Markov processes that we study will be reversible, i.e., their equilibrium dynamics is the same as the time reversed dynamics. To be more precise, consider a general Markov process on a state space Ω with generator

Lf = η,η ∈Ω L (η , η) (f (η ) -f (η)) ,
i.e., when at state η, the process jumps to η at rate L (η , η). For nite Ω, choosing the state η according to the measure µ, we dene the ow of probability from η to η as

R (η , η) = L (η , η) µ (η) . (2.1.1)
The measure µ is called an equilibrium measure, and the process is said to be reversible if for all η, η ∈

Ω R (η , η) = R (η, η ) . (2.1.2)
KCMs (see equation (1.2.1)) have this property. In fact, the ow could only be non-zero when η = η x for some site x, and in this case

R (η x , η) = c x (η) q(1 -q) (µ(η) + µ(η x )) , (2.1.3)
which shows that R is indeed symmetric. Equation (2.1.2) is a dierent way of saying that L is a self-adjoint operator in the space L 2 (Ω, µ), and dening reversibility this way makes sense also for innite Ω. Self-adjointness allows us to study the process via the spectrum or L. In particular, we will be interested in the second biggest eigenvalue of L, which is called (up to sign) the spectral gap.

Before discussing the spectral gap we start by dening the Dirichlet form. Let f be in the domain of L, then the Dirichlet form applied to f is dened as

Df = -µ (f Lf ) . (2.1.4)
For the models we will consider (dened in equation (1.2.1)), the following identities will also be useful:

Df = µ x∈G c x Var x f = µ x∈G c x q(1 -q) (∇ x f ) 2 = 1 2 η∈Ω x∈G R (η x , η) (∇ x f ) 2 . (2.1.5)
We are now ready to dene the spectral gap and the relaxation time

gap (L) = sup f :Varf =0 Df Varf , (2.1.6
)

τ rel = 1 gap (L)
.

(2.1.7)

The spectral gap will give us the time decay of correlation when starting from equilibrium:

for every local f, g and every t ≥ 0

|E µ [f (η (t)) g (η (0))] -µ (f ) µ (g)| ≤ Cov(f, g) e -t/τ rel .
In particular, if the process is not ergodic some correlations are never lost, and the spectral gap must be 0. The contrary is not true, i.e., ergodic processes may have 0 gap, as long as the only eigenfunctions of L with eigenvalue 0 are the constant functions (see, e.g., [START_REF] Thomas | Interacting particle systems[END_REF]).

Hitting times

The spectral gap that was introduced in the previous section gives a times scale which describes the relaxation of all observables uniformly. That is, it will be as long as the time that the slowest possible observable takes to relax. In disordered systems, as we will see in more details in chapters 3 and 4, this slowest observable is often much slower than typical times that we are interested in. In these cases, the spectral gap fails to provide a correct description of actual physical time scales of the system, and we must study specic times that could be observed. One of these is the time it takes for the origin to become empty, and more generally hitting times of dierent events.

We will start by considering a reversible Markov process on a state space Ω with generator L and equilibrium measure µ. Definition 2.2.1. Consider an event A ⊆ Ω. The hitting time at A is dened as

τ A = inf {t : η(t) ∈ A} .
The hitting time is dened for both the KCM and the bootstrap percolation. For the time it takes to empty the origin we will use the notation

τ 0 = τ {η 0 =0} . (2.2.1)
In the case of KCMs, the hitting time is a random variable that depends on both the initial conguration η ∈ Ω and the randomness of the Markov process. With some abuse of notation, we will use τ A (η) and τ 0 (η) for the expected value of the hitting time starting at η, i.e.,

τ A (η) = E η [τ A ] . (2.2.2)
The function τ A , for some event A ⊆ Ω, satises the following Poisson problem (see, e.g., [18, equation (7.2.45)]):

Lτ A = -1 on A c , (2.2.3) τ A = 0 on A.
By multiplying both sides of the equation by τ A and integrating with respect to µ, we obtain Corollary 2.2.2. µ (τ A ) = D (τ A ).

Rewriting this corollary as µ (τ

A ) = µ(τ A ) 2 Dτ A
, it resembles a variational principle introduced in

[5] that will be useful in the following. In order to formulate it we will need to introduce some notation.

Definition 2.2.3. For an event A ⊆ Ω, V A is the set of all functions in the domain of L that vanish on the event A. Note that, in particular, τ A ∈ V A . Definition 2.2.4. For an event A ⊆ Ω,

τ A = sup 0 =f ∈V A µ (f 2 ) Df .
The following proposition is given in the rst equation of the proof of Theorem 2 in [START_REF] Asselah | Quasi-stationary measures for conservative dynamics in the innite lattice[END_REF]:

Proposition 2.2.5. P µ [τ A > t] ≤ e -t/τ A .
Remark 2.2.6. In particular, Proposition 2.2.5 implies that µ (τ A ) ≤ τA . This, however, could be derived much more simply from Corollary 2.2.2

µ (τ A ) 2 ≤ µ τ 2 A ≤ τ A Dτ A = τ A µ (τ A ) .
Note that whenever τ A is not constant on A c this inequality is strict. Thus on one hand Proposition 2.2.5 gives an exponential decay of P µ [τ A > t], which is stronger than the information on the expected value we can obtain from the Poisson problem in equation (2.2.3). On the other hand, τ A could be longer than the actual expectation of τ A .

In order to bound the hitting time from below we will formulate a variational principle that

characterizes τ A . Definition 2.2.7. For f ∈ V A , let T f = 2µ(f ) -Df. Proposition 2.2.8. τ A maximizes T in V A . Moreover, µ(τ A ) = sup f ∈V A T f .
Proof. Consider f ∈ V A , and let δ = f -τ A . Using the self-adjointness of L, equation (2.2.3), and the fact that δ ∈ V A we obtain

T f = T (τ A + δ) = 2µ(τ A ) + 2µ(δ) -Dτ A -Dδ + 2µ(δLτ A ) = T τ A -Dδ.
By the positivity of the Dirichlet form, T is indeed maximized by τ A . Finally, by Corollary

2.2.2, sup f ∈V A T f = T τ A = 2µ(τ A ) -Dτ A = µ(τ A ).
As an immediate consequence we can deduce the monotonicity of the expected hitting time: Corollary 2.2.9. Let D and D be the Dirichlet forms of two reversible Markov processes dened on the same space Ω, and sharing the same equilibrium measure µ. We denote the expectations with respect to these processes starting at equilibrium by E µ and E µ . Assume that the domain of D is contained in the domain of D , and that for every f ∈ DomD Df ≥ D f. Then, for an event A ⊆ Ω,

E µ τ A ≤ E µ τ A .
We will now restrict ourselves to 0-1 kinetically constrained spin models, i.e., S = {0, 1}. Fix a subgraph H of G, and denote the complement of H in G by H c . We will compare the dynamics of this KCM to the dynamics restricted to H, with boundary conditions that are the most constrained ones. Definition 2.2.10. The restricted dynamics on H is the KCM dened by the constraints

c H x (η) = c x (η H ),
where, for η ∈ {0, 1} H , η H is the conguration given by

η H (x) =    η x x ∈ H, 1 x ∈ H c .
We will denote the corresponding generator by L H and its Dirichlet form by D H . Claim 2.2.11. For any f in the domain of

L Df ≥ µ H c D H f. Proof. c H x ≤ c x and Var x f is positive, therefore Df = µ x c x Var x f ≥ µ x∈H c H x Var x f .
The next claim will allow us to relate the spectral gap of the restricted dynamics to the expected hitting time and the persistence function using the variational principles discussed above. For the case H = G the result has been noted in [START_REF] Martinelli | Universality results for kinetically constrained spin models in two dimensions[END_REF], but not fully proven.

Claim 2.2.12. Let γ H be the spectral gap of L H , and x an event A that depends only on the occupation of the vertices of H. Then for all f ∈ V A

(1) Df ≥ µ(A)γ H (µf ) 2 , (2) Df ≥ µ(A) 1+µ(A) γ H µ (f 2 ) Proof. First, note that µ H (A) ≤ µ H (f = 0) ≤ µ H (|f -µ H f | ≥ µ H f ).
Therefore, by Chebyshev inequality and the fact that µ(A) = µ H (A),

µ(A) ≤ Var H f (µ H f ) 2 . (2.2.4) Then, Claim 2.2.11 implies Df ≥ µ H c D H f ≥ γ H µ H c Var H f ≥ µ (A) γ H µ H c (µ H f ) 2 ≥ µ (A) γ H (µf ) 2
by Jensen inequality. For the second part, we use inequality 2.2.4

Var

H f ≥ µ(A) µ H (f 2 ) -Var H f , which implies Var H f ≥ µ(A) 1 + µ(A) µ H (f 2 ).
The result then follows by applying Claim 2.2.11.

The time spent in E

In this section we consider a reversible Markov process on a state space Ω with generator L and equilibrium measure µ. Fix an event E ∈ Ω and t > 0. We will dene the time spent in E by time t as

T E t = t 0 1 E (η (s)) ds. (2.3.1)
Similarly to the case of the hitting time, this is a random variable that depends on the initial conguration and on the evolution of the Markov process, and we will dene again (in analogy with equation (2.2.2)) the averaged version

T E t (η) = E η T E t . ( 2
T E A = T E τ A . Also for T E A we dene T E A (η) = E η T E A .
(

LT E A (η) = -1 E (η) η / ∈ A, T E A (η) = 0 η ∈ A. (2.3.4)
Multiplying both sides by T E A and integrating with respect to µ gives

Corollary 2.3.2. µ T E A 1 E = D T E A .
To nish this section we present the analog of Proposition 2.2.8:

Proposition 2.3.3. Let T E f = 2µ (f 1 E ) -D (f ), and recall Denition 2.2.3. Then T E A maximizes T E in V A . Moreover, µ T E A 1 E = sup f ∈V A T E f . Proof. Consider f ∈ V A , and let δ = f -T E A .
Using the self-adjointness of L, equation (2.3.4), and the fact that δ ∈ V A we obtain

T E f = T E T E A + δ = 2µ T E A 1 E + 2µ (δ1 E ) -DT E A -Dδ + 2µ δ LT E A = T E τ A -Dδ.
By the positivity of the Dirichlet form, T E is indeed maximized by τ A . Finally, by Corollary

2.3.2, sup f ∈V A T E f = T T E A = 2µ T E A 1 E -DT E A = µ T E A 1 E .

Introduction of the models

The rst model we analyze is the mixed threshold bootstrap percolation and KCM. The graph G is Z d , and the disorder ω in an element of {easy, dicult} Z d

. Its measure will depend on a parameter π ∈ (0, 1), giving probability π for a site to be dicult and 1 -π to be easy. For an easy site x we dene the constraint Note that a more general model would be to allow ω x to take values in {1, . . . , d} and require ω x empty neighbors, but the result will not change and the notation will become a bit more complicated.

Section 3.5 will concern with a mixture of the North-East model and the FA1f model on the graph G = Z 2 . The disorder ω and its measure ν will be the same as for the mixed threshold models. For an easy site x the constraint is given by

c x (η) =    1
x is easy and has at least one empty neighbor 0 otherwise, In sections 3.6 and 3.7 the graph will be again Z 2 , and the disorder ω will give one of two values to each site, which we will call absent or present. Its measure will depend on a parameter π ∈ (0, 1), giving probability π for a site to be absent and 1 -π to be present. for the FA2f model (section 3.7).

Bootstrap percolation on Z 2 with threshold 1 or 2

Consider the bootstrap percolation on Z 2 dened by the constraints in equations (3.1.1) and (3.1.2). We will show that the hitting time τ 0 scales like q -1/2 when q is small; and see how the coecient scales with π when π is also small (but still much bigger than q). (1) ν-almost surely there exists t 0 = t 0 (ω) such that µ τ 0 ≥ t 0 + e γ/π π 3 √ q a ≤ e -λa 2 .

(3.2.1)

γ and λ are explicit constants. (2) ν-almost surely there exists a 0 = a 0 (ω) such that

µ τ 0 ≤ e γ /π 2 √ q a ≤ C 1 q + C 2 a 2 (3.2.2)
for all a ∈ a 0 √ q, 1 . γ and C 2 are explicit constants, and C 1 may depend on π (but not on ω, η, or q). Remark 3.2.2. This theorem gives a way to interpolate between the FA1f and FA2f bootstrap percolation when π = 1 it is the FA1f model, and τ 0 is indeed of the scale q -1/2 . As π decreases the coecient in front of q -1/2 increases, bringing us closer to the time scale of the FA2f. If we believe that π could go all the way down to order q (even though the theorem only allows to obtain the scaling for q → 0 after xing π), we reach the time scale e γ/q , as in the FA2f model.

Remark 3.2.3. The proof of Theorem 3.2.1 is essentially that of [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF], with the appropriate adaptations. Also in their proof the two exponents γ and γ are dierent, but in [START_REF] Holroyd | Sharp metastability threshold for two-dimensional bootstrap percolation[END_REF] a sharper bound gives two equal exponents. It is thus natural to conjecture that also in our case γ = γ , and perhaps using some of the methods in [START_REF] Holroyd | Sharp metastability threshold for two-dimensional bootstrap percolation[END_REF] could show that. We start by a simple estimation of probability that a square is good.

Claim 3.2.5. The probability that a square of size L is good is at least 1 -2Le -πL .

Proof.

ν [easy site in each line] = 1 -(1 -π) L L ≥ 1 -Le -πL .
The same bound holds for ν [easy site in each column], and then we conclude by the union bound.

Definition 3.2.6. The square [L] 2 is excellent if for every 2 ≤ i ≤ L at least one of the sites in {i} × [i -1] is easy, and at least one of the sites in [i -1] × {i} is easy. For other squares of side L being excellent is dened by translation.

We will use p L to denote the probability that a square of side L is excellent. Claim 3.2.7. p L ≥ e -2γ/π , uniformly in L.

Proof. The probability that the condition holds at step i is 1 -(1 -π) i-1 2 . We then bound the product L i=2 1 -(1 -π) i-1 by its value at L = ∞. This could be evaluated by Though not essential for the proof, one may note that γ could be calculated explicitly: Proof. This could be done by induction on the size of the empty square assume that [l] 2 is entirely emptied for some l ≤ L. By the denition of an excellent square, there is an easy site x ∈ {l + 1} × [l]. Its neighbor to the left is empty (since it is in [l] 2 ), so at the next time step this site will also be empty. Once x is empty, the two sites x ± e 2 could be emptied, and then the sites x ± 2e 2 and so on, as long as they stay in {l + 1} × [l]. Thus, at time l all sites in {l + 1} × [l] will be empty, and by the same reasoning the sites of [l] × {l + 1} will also be empty. Since (l + 1, l + 1) has two empty neighbors it will be emptied at step l + 1, and thus [l + 1] 2 will be emptied. Claim 3.2.9. Assume that [L] 2 is good, and that it has a neighboring square that is entirely empty by time T . Then [L] 2 will be entirely empty by time T + L 2 .

∞ i=2 log 1 -(1 -π) i-1 ≥ ∞ 0 dt log 1 -(1 -π) t = - 1 log (1 -π) ∞ 0 ds log 1 -e -s .
- ∞ 0 ds log 1 -e -s = ∞ 0 ds ∞ k=1 1 k e -ks = ∞ k=1 1 k ∞ 0 ds e -ks = ∞ k=1 1 k 2 = ζ(2).
Proof. We can empty [L] 2 line by line (or column by column, depending on whether its empty neighbor is in the horizontal direction or the vertical one). For each line, we start by emptying the easy site that it contains, and then continue to propagate. Definition 3.2.10. Until the end of the proof of the upper bound, L will be the minimal length for which the probability to be good exceeds the critical probability for Bernoulli site percolation by at least 0.01. By Claim 3.2.5 this L exists, and is of order log 1 /π π when π is small. Definition 3.2.11. C will denote the innite cluster of good boxes of the form Li + [L] 2 for i ∈ Z 2 . C 0 will denote the cluster of the origin surrounded by a path in C, or just the origin if it is in C. ∂C 0 will be the outer boundary of C 0 (namely the boxes out of C that have a neighbor in C 0 ). Note that C 0 is nite and that ∂C 0 is connected. Claim 3.2.12. Assume that at time t one of the boxes on ∂C 0 is entirely empty. Then by time t + t 1 the origin will be empty, where

t 1 = (|∂C 0 | + |C 0 |) L 2 .
Proof. By Claim 3.2.9, the boundary ∂C 0 will be emptied by time t 1 + L 2 |∂C 0 |. Then, at each time step at least one site of C 0 must be emptied, since no nite region could stay occupied forever. Claim 3.2.13. Assume that a box Li + [L] 2 in C is empty at time t. Also, assume that the graph distance in C between this box and ∂C 0 is l. Then by time t + lL 2 + t 1 the origin will be empty.

Proof. This is again a direct application of claims 3.2.9 and 3.2.12.

Finally, we will use the following result from percolation theory: Claim 3.2.14. ν-almost surely there exists l 1 = l 1 (ω), such that for l ≥ l 1 the number of boxes in C that are at graph distance in C at most l from ∂C 0 is greater than θl 2 . θ is a universal constant (depending only on the choice 0.01 made in Denition 3.2.10).

Proof. By ergodicity the cluster C has an almost sure positive density, so in particular

lim inf l→∞ C ∩ [-l, l] 2 [-l, l] 2 > 0.
By [START_REF] Antal | On the chemical distance for supercritical Bernoulli percolation[END_REF], there exists a positive constant ρ such that boxes of graph distance l from the origin must be in the box -1 ρ l, 1 ρ l 2 for l large enough. Combining these two facts proves the claim.

This claim together with a large deviation estimate yields Corollary 3.2.15. ν-almost surely there exists l 2 = l 2 (ω), such that for For l ≥ l 2 , the number of excellent boxes in C that are at graph distance in C at most l from ∂C 0 is greater than θ l 2 , where θ = 0.99 θp L .

We can now put all the ingredients together and obtain the upper bound.

Let l = e γ/π √ q 1

L 2 π 3 a + l 2 . By Corollary 3.2.15, there are at least θ l 2 ≥ e 2γ/π q 1 L 2 π 3 a 2 excellent boxes in C at graph distance in C at most l from ∂C 0 . If one of them contains an empty site at its bottom left corner, the origin will be emptied by time (l + 1) L 2 + t 1 , so in this case τ 0 < e γ/π π 3 √ q a + t 0 , taking t 0 = t 1 + (l 2 + 1) L 2 . We are left to bound the probability that none of the θ e 2γ/π q 1 L 2 a 2 excellent boxes has an empty corner:

(1 -q) θ e 2γ/π q 1 L 2 π 3 a 2 ≤ e -0.99 θp L e 2γ/π a 2 ≤ e -0.99θ a 2 .

Lower bound (proof of equation

(3.2.2)). Definition 3.2.16. A rectangle R (that is, a subset of Z 2 of the form x + [L 1 ] × [L 2 ]
) is pre-internally spanned if there is a vertex x ∈ R such that starting from entirely lled R, except for one empty site at x, R is internally spanned.

We now x k = B π , for some constant B that will be determined later on. Claim 3.2.17. Fix the rectangle [a] × [b], for a ∈ [k, 2k + 2] and b ≤ a. The probability that it is pre-internally spanned is at most e -γ 1 /π . Proof. In order to prevent the rectangle from being pre-internally spanned it suces to have two consequent columns with no easy vertices. This happens with probability

1 -(1 -π) 2b a ≤ 1 -(1 -π) 2a a ≤ 1 -(1 -π) 2k k ≤ e -γ 1 /π .
To obtain the second inequality we need to look at the function a

→ 1 -(1 -π) 2a a . It
decreases to a minimum at some point ∝ 1 π , and then increases. We can x B such that this minimum is at 10B q , and the inequality follows.

We will now bound the number of pre-internally spanned rectangles.

Definition 3.2.18. Fix l ∈ N. n l = n l (ω) will be the number of pre-internally spanned rectangle inside [-l, l] 2 whose longest side is of length between k and 2k + 2. Claim 3.2.19. There exists l 0 = l 0 (ω) such that for all l ≥ l 0 n l ≤ 40k 2 e -γ 1 /π l 2 .

Proof. First, we can bound the number of rectangle of longest side in [k, 2k + 2] inside [-l, l] 2 whose longest side is of length between k and 2k + 2. Each of them could have one of (2l + 1) 2 points to be its right corner, at most 2k + 2 options for its height and at most 2k + 2 for its width. That is, the total number of possibilities is at most 20k 2 l 2 . By FKG, we can take 20k 2 l 2 independent rectangles, thus ν n l > 20k 2 e -γ 1 /π l 2 is dominated by the probability that a binomial of parameters 20k 2 l 2 and e -γ 1 /π is greater than 40k 2 l 2 e -γ 1 /π . By large deviation estimate this happens with probability at most e -c l 2

for some c that depends on γ 1 , π, k but not on l. We then conclude by the Borel-Cantelli lemma. This is the information that we need about the quenched environment ω. We will now consider the state η as well. Lemma 3.2.20. Fix l, m ≤ l. If [-l, l] 2 in internally spanned, then it contains an internally spanned rectangle whose longest side is of length between m and 2m + 2.

Proof. We will dene a sequence {C n } N n=0 of collections of (possibly overlapping) rectangles in [-l, l] 2 , such that the following conditions hold (1) For all n and all rectangles R ∈ C n , R is internally spanned or a single easy site.

(2) For all n, the union ∪ R∈Cn R contains all empty sites and all easy sites.

(3) For all n and for all R, R ∈ C n , R R . (4) Let l n be the maximal side length of a rectangle in C n . Then l n+1 ≤ 2l n + 2.

(5

) C N = [0, L -1] 2 .
The construction is the same as in [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF] start with all empty and easy sites (we assume that [-l, l] 2 is internally spanned, so some must exist). Then we make the following observation: Observation 3.2.21. Assume that C n satises conditions 1,2 and 3 above, and that it contains more than one rectangle. Then there are two rectangles in C n with distance at most 2.

Proof. Assume the contrary, so in particular [-l, l] 2 \ ∪ R∈Cn R is nonempty. Take the rst x ∈ [-l, l] 2 \ ∪ R∈Cn R that is emptied by the bootstrap percolation. This x is dicult, and has has one neighbor in ∪ R∈Cn R, which is a contradiction.

Using this observation, we could, starting at C n , take two rectangles R 1 , R 2 ∈ C n at distance at most 2. Let R be the minimal rectangle containing both of them. Then add R to C n and remove all rectangles of C n contained in R (among them R 1 and R 2 , but possible others as well). This will give us a new collection C n+1 satisfying conditions 1,2 and 3. Since at each step the number of rectangles decreases, and as long as |C n | ≥ 2 we can go on, until we reach some step N at which |C N | = 1.

Property 4 is easily veried from the construction, so we are left to check property 5. Since |C N | = 1, we can write C n = {R} for some rectangle R. We know that if there are sites outside R they must be dicult, but then they could never be emptied, contradicting the fact that [l] 2 is internally spanned.

Finally, by property 4, we can take the last n for which

l n ≤ m. Then m ≤ l n+1 ≤ 2l n + 2 ≤ 2m + 2.
The connection between τ 0 and internally spanned rectangles is given in the following claim: Claim 3.2.22. Recall the denition of τ 0 (Denition 2.2.1). There must be (for the initial conguration) an internally spanned rectangle containing the origin whose longest side is of length greater or equal τ 0 .

Proof. Consider the span of [-τ 0 , τ 0 ] 2 . It is compound of disjoint rectangles, one of which containing the origin. We know that the origin is emptiable using only the sites of [-τ 0 , τ 0 ] 2 , but not the sites of [τ 0 -1, τ 0 -1] 2 . That is, the rectangle containing the origin has a site on the boundary. In particular, its longest edge is of length at least τ 0 .

We can now put everything together and prove equation (3.2.2).

First, we bound the probability that τ 0 < k

µ (τ 0 < k) ≤ µ ([-k, k] contains an empty site) ≤ 4k 2 q = 4B 2 π 2 q.
If τ 0 ≥ k, by Claim 3.2.5 and Lemma 3.2.20 there must be an internally spanned rectangle of longest side between k and 2k + 2 in [-τ 0 , τ 0 ] 2 . There are two ways for such a rectangle to be internally spanned either it is pre-internally spanned and contains an empty site, or it is not, and in this case it must contain at least two empty sites. Let l = π 2 e γ 1 /2π 2 √ q a. Then, assuming l ≥ l 0 ,

µ (τ 0 ≤ l) ≤ 4B 2 π 2 q + n l (2k + 2) 2 q + l 2 (2k + 2) 4 q 2 ≤ 4B 2 π 2 q + 50k 4 π 4 a 2 + 5 k 4 π 4 e γ 1 /π a 2 q = 4B 2 π 2 + 5 B 4 e γ 1 /π a 2 q + 50B 4 a 2 . Setting γ = γ 1 /2, a 0 = 2l 0 π -2 e -γ/π , C 1 = 4B 2 π 2 + 5 B 4 e γ 1 /
π and C 2 = 50B 4 nishes the proof.

Fredrickson-Andersen model on Z 2 with threshold 1 or 2

We will now study the KCM on Z 2 dened by the constraints in equations (3.1.1) and (3.1.2). We will see that the hitting time τ 0 scales polynomially with q, like in the bootstrap percolation. However, unlike the bootstrap percolation, this exponent will not be that of the FA1f constraint, but a random exponent changing from one realization of ω to the other.

2).

(1) There exists a constant c > 0 such that, ν-a.s., the relaxation time of the process is greater than e c/q . (2) ν-a.s. there exist α and α (with α ≤ α) such that

P µ τ 0 ≥ q -α q→0 --→ 0, (3.3.1) P µ τ 0 ≤ q -α q→0 --→ 0. (3.3.2)
Moreover, E µ [τ 0 ] ≥ q -α for q small enough. α and α depend on ω, and assuming π < e -1 they could be chosen such that

ν α > 11 log 1 /π π a < e -a , ν α < a π < a ,
for any a > 3 and any a such that cπ ≤ a ≤ C for two constants c, C. In particular, they cannot be deterministic there exists α 0 such that ν (α < α 0 ) > 0 but ν (α < α 0 ) <

1.

This theorem suggests the following conjecture: Conjecture 3.3.2. ν-almost surely the limit lim q→0 log τ 0 log 1 /q exists. Its value α is a random variable whose law depends on π. Moreover, the law of πα converges (in some sense) to a non-trivial law as π tends to 0.

Remark 3.3.3. Like in the case of the bootstrap percolation, we can see how the time scales t with the deterministic models when taking π to 1 or to 0. For π = 1 we obtain the FA1f, in which τ 0 is polynomial, of order q -2 1 . In the other limit, for small π, the scale obtained for τ 0 is (up to logarithmic corrections) q 1/π . If we believe that π could be taken of order q (though, strictly speaking, the theorem does not allow us to do that), we obtain (up to logarithmic corrections) the scaling e 1/q , just like in FA2f [START_REF] Martinelli | Towards a universality picture for the relaxation to equilibrium of kinetically constrained models[END_REF].

Spectral gap (proof of part 1 of Theorem 3.3.1). The spectral gap of this

model is dominated by that of the FA2f model. Fix any γ strictly greater than the gap of FA2f. Then there is a local non-constant function f such that

D FA2f f Varf ≤ γ,
where D FA2f is the Dirichlet form of the FA2f model.

Since f is local, it is supported in some square of size L × L, for L big enough. ν-almost surely it is possible to nd a far away square in Z 2 of size L × L that contains only dicult sites. By translation invariance of the FA2f model we can assume that this is the square in which f is supported. In this case, Df = D FA2f f , and this shows that indeed the gap of the model with random threshold is smaller than that of FA2f, which by [START_REF] Cancrini | Kinetically constrained spin models[END_REF] is bounded by e -c /q .

Upper bound (proof of equation (3.3.1))

. For the proof of the upper bound we will use Corollary 2.2.2 in order to bound τ 0 by a path argument. As in the proof of the upper bound for the bootstrap percolation, we will consider the good squares (see Denition 3.2.4) and their innite cluster. In fact, by Claim 3.2.5, by choosing L big enough we may assume that the box [L] 2 is in this cluster:

L = inf d : [d] 2 is in an innite good cluster . (3.3.3)
Let us x this L until the end of this proof.

1 It is shown in [START_REF] Cancrini | Kinetically constrained spin models[END_REF] that the spectral gap of FA1f in Z 2 scales as q -2 up to logarithmic corrections. Using their methods together with those presented in the proof of Theorem 3.3.1 one nds the same scaling also for τ 0 . Claim 3.3.4. Assume that π < e -1 . Then ν L > 2 log 1 /π π a < e -a for all a > 3.

Proof. Fix d > 2 log 1 /π π a. Then, by Claim 3.2.5, the probability that a box of size d is good is greater than 1 -20e -2a . Then (see, e.g., [START_REF] Duminil-Copin | A new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model[END_REF][START_REF] Grimmett | Percolation[END_REF]), the probability that [d] 2 does not belong to the innite cluster is at most 320e -2a , and the result follows.

We will also choose an innite self avoiding path of good boxes starting at the origin and denote it by i 0 , i 1 , i 2 , . . . . Note that this path depends on ω but not on η.

On this cluster empty sites will be able to propagate, and the next denition will describe the seed needed in order to start this propagation.

Definition 3.3.5. A box in Z 2 is essentially empty if it is good and contains an entire line or an entire column of empty sites. This will depend on both ω and η.

In order to guarantee the presence of an essentially empty box we will x l = q -L-1 ,

(3.3.4)
and dene the bad event Definition 3.3.6. B = {none of the boxes i 0 , . . . , i l is essentially empty}. For xed ω the path i 0 , i 1 , i 2 , . . . is xed, and B is an event in Ω.

A simple bound shows that

µ (B) ≤ 1 -q L l ≤ e -1 /q . (3.3.5)
We can use this inequality in order to bound the hitting time at B:

Claim 3.3.7. There exists C > 0 such that P µ (τ B ≤ t) ≤ Ce -1 /q t.
Proof. We use the graphical construction of the Markov process. In order to hit B, we must hit it at a certain clock ring taking place in one of the sites of ∪ l n=1 Li + [L] 2 . Therefore,

P (τ B ≤ t) ≤ P more than 2 (2L + 1) 2 lt rings by time t + 2 (2L + 1) 2 l t µ (B) ≤ e -(2L+1) 2 q -L-1 t + 2 (2L + 1) 2 q -L-1 t e -1 /q ≤ Ce -1 /q t.
In order to bound τ 0 we will study the hitting time of

A = B ∪ {η (0) = 0} . (3.3.6) Lemma 3.3.8. Fix η ∈ Ω.
Then there exists a path η 0 , . . . , η N of congurations and a sequence of sites x 0 , . . . x N -1 such that [START_REF] Aizenman | Sharpness of the phase transition in percolation models[END_REF] (4)

η 0 = η, (2) η N ∈ A, (3) η i+1 = η x i i , 0
c x i (η i ) = 1, (5) N ≤ 4L 2 l, (6)
For all i ≤ N , η i diers from η at at most 3L points, contained in at most two neighboring boxes.

Proof. If η ∈ A, we take the path η with N = 0. Otherwise η ∈ B c , so there is an essentially empty box in i 0 , . . . , i l , which then contains an empty column (or row). We can then create an empty column (row) next to it and propagate that column (row) as in gure 3.3.1.

When the path rotates we can rotate this propagating column (row) as show in gure 3.3.2.

We can use this path together with Corollary 2.2.2 in order to bound τ A . Lemma 3.3.9. There exists C L > 0 (that may depends on L but not on q) such that µ

(τ A ) ≤ C L L 10L q -5L-2 .
Proof. Since τ vanishes on A, taking the path dened in Lemma 3.3.8,

τ A (η) = N -1 i=0 (τ A (η i ) -τ A (η i+1 )) .
In the following we use the notation

∇ x τ A (η) = τ A (η) -τ A (η x ) .
Then, by Cauchy Schwartz inequality,

µ (τ A ) 2 ≤ µ τ 2 A = η µ (η) N -1 i=0 ∇ x i τ A (η i ) 2 ≤ η µ (η) N i c x i (η i ) (∇ x i τ A (η i )) 2 = η µ (η) N i z η c z (η ) (∇ z τ A (η )) 2 1 z=x i 1 η =η i .
By property number 6 of the path, we know that µ (η

) ≤ q -3L µ (η ), yielding µ (τ A ) 2 ≤ q -3L N η µ (η ) z c z (η ) (∇ z τ A (η )) 2 i 1 z=x i η 1 η =η i .
Still using property 6, η diers form η at at most 3L point, all of them in the box containing z or in one of the two neighboring boxes. This gives the bound η

1 η =η (i) ≤ (3L 2 ) 3L . Finally, bounding 1 z=x i by 1, µ (τ A ) 2 ≤ q -3L 3L 2 3L N 2 η µ (η ) z c z (η ) (∇ z τ A (η )) 2 ≤ 16 3L 2 3L L 4 q -5L-2 Dτ A .
This concludes the proof of the lemma by Corollary 2.2.2.

Using this lemma and the bound on τ B in Claim 3.3.7, we can nish the estimation of the upper bound. By Markov inequality and the fact that µ (τ

A ) = E µ (τ A ) (recall equation (2.2.2)) P µ τ A ≥ C L q -5L-3 ≤ q.
On the other hand, by Claim 3.3.7,

P µ τ A < C L q -5L-5 ≤ P µ τ 0 < C L q -5L-3 + P µ τ B < C L q -5L-3 ≤ P µ τ 0 < C L q -5L-3 + C L e -1 /q . Therefore P µ τ 0 ≥ C L q -5L-3 ≤ q + C L e -1 /q ,
and taking α = 5L + 3 will suce.

Lower bound (proof of equation (3.3.2))

. In order to prove equation (3.3.2) we will show that before hitting {η 0 = 0} we must pass through a very unlikely state, in which many sites are empty. Proof. We may assume without loss of generality that R contains d distinct pairs of neighboring lines with only dicult vertices. That is, there exist i 1 < i 2 < • • • < i d such that i n+1 > i n + 1 and the sites of R ∩ (Z × {i n , i n + 1}) are dicult for all n ≤ d. We will show that R ∩ (Z × {i n , i n + 1}) contains an empty site for all n ≤ d, and this will prove the claim.

Definition 3.3.10. Consider a rectangle R = [x 1 , y 1 ] × [x 2 , y 2 ]. We say that R is d-dicult if it contains at least d distinct
Fix n ≤ d, and assume that the sites of R ∩ (Z × {i n , i n + 1}) are all occupied. Since R is internally spanned, one of these sites must be emptied at some time. However, at this time it could only have one empty neighbor in R three of its neighbors are in (Z × {i n , i n + 1}) and the sites in R ∩ (Z × {i n , i n + 1}) are occupied by minimality. This is a contradiction, since this site must be dicult.

In order to guarantee the existence of d-dicult rectangles, we dene the event D L,d : Definition 3.3.12. Let L, d ∈ N. The event D L,d is the intersection of the following events:

(1) # 0 ≤ i ≤ L 2 : all vertices in {2i, 2i + 1} × [-L, L] are dicult ≥ d, (2) # 0 ≤ i ≤ L 2 : all vertices in {-2i, -2i -1} × [-L, L] are dicult ≥ d, (3)
# 0 ≤ i ≤ L 2 : all vertices in [-L, L] × {2i, 2i + 1} are dicult ≥ d, (4) # 0 ≤ i ≤ L 2 : all vertices in [-L, L] × {-2i, 2i -1} are dicult ≥ d.
Note that this event depends only on the disorder ω.

a ≤ C, ν ∃d ≥ a π and L ≥ 10a π such that D L,d ≥ 1 -a. Proof. Let 0 < b < 2π, x L = b 4π -1 2 and d = L 4 e -b . We will estimate the probability of D L,d . For xed i, the probability that {2i, 2i + 1} × [-L, L] contain only dicult sites equals (1 -π) 2L+1 ≥ e -2(2L+1)π ≥ e -b .
Therefore, the rst event in the denition of D L,d (3.3.12) is described by a binomial random variable with parameters L

2 , e -b that must be greater than d. This probability is bounded from below by 1 -e -1 4 e -b L . Then, by the union bound,

ν (D L,d ) ≥ 1 -2Le -1 4 e -b L .
We may choose b (uniformly in π) such that a = πd, and if it is small enough then 2Le

-1 4 e -b L ≤ a. Claim 3.3.15. Fix L, d and x ∈ Z 2 . Let G x ⊆ Ω be the event that the origin is in the span of [-L, L] 2 for η, but it is not in the span of [-L, L] 2 for η x (recall Denition 1.3.2). Let G = ∪ x∈Z 2 G x . Assume further that D L,d occurs. Then µ (G) ≤ 2L 2 + 1 d q d .
Proof. First, note that x must be on the boundary of [-L, L] 2 , and that it is contained in the same internally spanned rectangle as the origin for the conguration η. Then by Claim 3.3.11 and Observation 3.3.13 the conguration η contains at least d empty sites.

We can now conclude the proof for the lower bound. Fix d, L and assume that D L,d occurs. The argument of Claim 3.3.7 tells us that τ G (for the event G dened in Claim 3.3.15) is greater than q -d+1 with probability that tends to 1 as q → 0 (while keeping ω, and therefore L, xed). If we start with a conguration for which the origin is not in the span of [-L, L] 2 , it could only be emptied after τ G at the rst instant in which the span of [-L, L] 2 includes the origin, G x must occur for the site that has just been ipped. Since the probability to start with an entirely occupied [-L, L] 2 tends to 1 as q → 0, equation (3.3.2) is satised for α = d -1.

In order to bound also the expected value of τ 0 we will use Proposition 2.2.8. Let us consider the function

f = 1 0 is not in the span of [-L,L] 2 .
We can bound its Dirichlet form using Claim 3.3.15:

Df = µ x c x Var x f ≤ µ x c x q1 Gx ≤ q 4 (2L + 1) 2L 2 + 1 d q d = C L q d+1 .
The expected value is bounded by the probability that all sites are occupied µf ≥ (1 -q) (2L+1) 2 .

Now consider for some λ ∈ R the rescaled function f = λf . Recall Denition 2.2.7.

T f = 2µf -Df ≥ 2λ (1 -q) (2L+1) 2 -λ 2 C L q d+1 .
The optimal choice of λ is (1-q) (2L+1) 2

C L q d+1 , which yields T f ≥ (1 -q) 2(2L+1) 2 C L q -d-1 .
In addition, f ∈ V {η 0 =0} , so by Proposition 2.2.8

µ (τ 0 ) ≥ (1 -q) 2(2L+1) 2 C L q -d-1 .

Fredrickson-Andersen model on Z d with threshold 1 or d

The results of the previous section could be extended to Z d . In [START_REF] Shapira | Kinetically constrained models with random constraints[END_REF] it is explained how the proof in section 3.3 could be generalized, but here we will use a dierent strategy. We will see that τ 0 scales as a power law (like in the FA1f case [START_REF] Cancrini | Kinetically constrained spin models[END_REF]), with a power that may change from one realization to the other. We will not analyze the scaling of this power when π is small as we did for the two dimensional case, but we can expect an iteretated exponent scaling that would t the FAdf model when π is of order q (see Remark 3.

2).

(1) There exists a constant c > 0 such that, ν-a.s., the relaxation time of the process is greater than exp (d-1) c q , where exp (•) is the iterated exponential. (2) Recall Denition 2.2.4 and let τ = τ {η 0 =0} . ν-a.s. there exist α and α (with α ≤ α) such that for q small enough

τ ≤ q -α (3.4.1)
and

E µ [τ 0 ] ≥ q -α . (3.4.2)
Remark 3.4.2. As already mentioned in the denition of the model, a more general disorder would allow any threshold between 1 and d, and not just d. It will make notations more complicated, but by monotonicity the theorem will also hold for that case. will use Claim 2.2.12 together with the following proposition proven in [START_REF] Martinelli | Universality results for kinetically constrained spin models in two dimensions[END_REF].

Proposition 3.4.3. Consider a KCM on Z with spin values in S and equilibrium measure µ, which is a product of copies of the measure µ 0 on S. Let G be an event on S, and consider the generator dened on local functions as

L G f = i∈Z 1 G i-1 ∪G i+1 (µ i f -f ) .
Then the gap of L G is greater than C µ 0 (G) 3 for a constant C > 0.

We start by extending Denition 3.2.4 to dimension d:

Definition 3.4.4. A square (that is, a subset of Z 2 of the form x + [L] d ) is good if each of its d -1 dimensional
sections could be emptied with an initial conguration in which one of its two neighboring faces is empty and all other vertices are occupied. Note that being good depends only on the disorder ω and not on the state η.

From bootstrap percolation results (e.g., [START_REF] Balogh | The sharp threshold for bootstrap percolation in all dimensions[END_REF]) we know that Claim 3.4.5. The probability that a square of size [L] d is good tends to 1 as L tends to ∞. This implies that ν-a.s. we can choose L (depending on ω) such that the origin belong to an innite cluster of good squares. We x this L, and a biinnite nearest neighbor self avoiding path . .

. , b -1 , b 0 , b 1 , • • • ∈ Z d , such that B b i is good for all i ∈ Z.
In the following we will consider the dynamics restricted to the graph ∪ i∈Z B b i (see Denition 2.2.10), and denote B b i by B i .

First, we dene the coarse grained dynamics. Let E i be the event, that for each of the d directions, at least one section of the box B i is empty. Then we dene

c CG i = 1 E i+1 ∪E i-1 , L CG f = i c CG i (µ B i f -f ) , D CG f = µ i c CG i Var B i f .
Observation 3.4.6. If we take S = {0, 1} B 0 with the measure µ B 0 , and G = E 0 , then L G given in Proposition 3.4.3 describes the same dynamics as L CG . In particular,

gap L CG ≥ µ (E 0 ) 3 ≥ C q 3dL d-1 .
The next step is to bound D using D CG . First, we write

c CG i ≤ 1 E i+1 + 1 E i-1 .
Consider the term 1 E i+1 . Without loss of generality assume b i+1 = b i + e 1 . Let S k = Lb i + {k} × [L] d-1 be the kthe section of B i in the direction e 1 . By the denition of E i+1 ,

1 E i+1 ≤ 2L n=L+1 1 Sn is empty . (3.4.3)
In order to bound the term 1 Sn is empty Var B i f we will use the a dynamics in Lb

i +[n -1]×[L] d-
c S k = 1 {S k+1 is empty}∪{S k-1 is empty} , L Sn f = n-1 k=1 c S k (µ S k f -f ) , D Sn f = µ ∪ n-1 k=1 S k n-1 k=1 c S k Var S k f .
i +[n -1]×[L] d-1 .
In particular, due to the empty boundary,

gap L Sn ≥ C µ (S 0 is empty) 3 = C q 3L d-1 .
Before continuing, we mention the following general property of the spectral gap. Claim 3.4.8. Take any Markov process on a nite state space Ω, reversible with respect to a measure µ. Assume that it is ergodic, and that for all transitions (η, η ) with non-zero rate R (η, η ) ≥ r, for some xed r > 0 (recall equations 2.1.1 and 2.1.3). Then the spectral gap is

at least r 2|Ω| 2 . Proof. Let f : Ω → R such that µ (f ) = 0 and µ (f 2 ) = 1. There exists η + ∈ Ω such that |f (η + )| ≥ 1.
Assume without loss of generality f (η + ) > 0. µ (f ) = 0, so there must be η -∈ Ω such that f (η ) < 0. By ergodicity, there is a path η + = η 0 , . . . , η N = η -with non-zero rate transitions, and length N ≤ |Ω|. f (η N ) -f (η 0 ) > 1, so there must be two congurations

η i , η i+1 such that f (η i+1 ) -f (η i ) > 1 |Ω| . Therefore Df = 1 2 η,η R (η, η ) (f (η) -f (η )) 2 ≥ 1 2 r (f (η i ) -f (η i+1 )) 2 ≥ r 2 |Ω| 2 .
We will use Claim 3.4.8 on the dynamics restricted to S k , with the Dirichlet form given by

D S k f = µ S k x∈S k c x Var x f .
We will denote by D k the Dirichlet form of the same dynamics, but with empty boundary at S k+1 and occupied elsewhere. Note that this is the exact same dynamics as the one we obtain by taking F k-1 empty and occupied elsewhere, and that this dynamics is ergodic since all boxes are good.

With these denitions, taking r = q L d-1 in Claim 3.4.8, the gap of the D k -dynamics is at least 2

L d-1 -1 q L d-1 . Therefore, c S k Var S k f ≤ 2 -L d-1 +1 q -L d-1 c S k D S k f.
We now use Observation 3.4.7, equation (3.4.3) and the above equation to obtain

µ 1 E i+1 Var B i f ≤ 2L n=L+1 µ (1 Sn is empty Var B i f ) ≤ 2L n=L+1 µ 1 Sn is empty Var ∪ n-1 k=1 S k f ≤ C -1 q -3L d-1 2L n=L+1 µ 1 Sn is empty D Sn f = C -1 q -3L d-1 2L n=L+1 µ 1 Sn is empty n-1 k=1 c S k Var S k f 3.5. MIXED NORTH-EAST AND FREDRICKSON-ANDERSEN 1 SPIN FACILITATED MODELS ON Z 2 31 ≤ C -1 q -3L d-1 2 -L d-1 +1 q -L d-1 2L n=L+1 µ 1 Sn is empty n-1 k=1 c S k D S k f = C -1 q -3L d-1 2 -L d-1 +1 q -L d-1 q 2L d-1 2L n=L+1 n-1 k=1 µ (D S k f ) = C -1 2 -L d-1 +1 q -2L d-1 2L n=L+1 n-1 k=1 µ x∈S k c x Var x f ≤ C -1 2 -L d-1 +1 q -2L d-1 L µ   x∈B i ∪B i+1 c x Var x f   .
By symmetry this bound also holds for µ

1 E i-1 Var B i f . Finally, using Theorem 3.4.6 Varf ≤ C -1 q -3dL d-1 µ i c CG i Var B i f ≤ C -1 q -3dL d-1 µ i 1 E i+1 Var B i f + C -1 q -3dL d-1 µ i 1 E i-1 Var B i f ≤ 2C -1 q -3dL d-1 i 2 -L d-1 +1 q -2L d-1 L x∈B i ∪B i+1 c x Var x f ≤ C -1 L 2 -L d-1 +3 q -(3d+2)L d-1 x∈∪ i∈Z B i c x Var x f.
That is, the spectral gap of the restricted dynamics is greater than CL -1 2 L d-1 +3 q (3d+2)L d-1

.

Choosing α > (3d + 2) L d-1 nishes the proof by Claim 2.2.12.

Lower bound (proof of equation (3.4.2))

. The lower bound of this model can by analyzed in a similar way to the case of Z 2 . However, if we are not interested in the way α scales with π, we can simply observe that the time at which the origin is empty is certainly longer than the that of the unconstrained dynamics. Therefore, any α < 1 will suce.

Mixed North-East and Fredrickson-Andersen 1 spin facilitated models on Z 2

Unlike the models that have been studied in the previous sections, this KCM is not necessarily ergodic. For a xed environment ω there exists a critical value q c above which all sites are emptiable for the bootstrap percolation, and below which some sites remain occupied forever.

Denote by p SP the critical probability for the Bernoulli site percolation on Z 2 and by p OP the critical probability for the oriented Bernoulli percolation on Z 2 . Then

q c ≤ 1 - 1 -p SP 1 -π ,
since if we have an innite cluster of sites that are either easy or empty all sites are emptiable.

In particular, if π > p SP the critical probability is 0. On the other hand, if there is an innite up-right path of dicult sites that are all occupied, this path could never be emptied. This will imply that q c ≥ 1 -p OP 1-π .

We will see for this model that it is possible to have an innite relaxation time, and still the tail of the distribution of τ 0 decays exponentially, with a rate that scales polynomially with q.

Theorem 3.5.1. Consider the kinetically constrained model described above, with π > p SP and q < p OP .

(1) ν-almost surely the spectral gap is 0, i.e., the relaxation time is innite.

(2) There exist two positive constants c, C depending on π and a ν-random variable τ such that (a) P µ (τ 0 ≥ t) ≤ e -t /τ for all t > 0, (b) ν (τ ≥ t) ≤ C t c log q for t large enough. The exponential tail of τ 0 is a consequence of Proposition 2.2.5, so we are left with proving that ν (τ ≥ t) ≤ t c log q for some constant c. We will do that by choosing a subgraph on which we can estimate the gap, and then apply Claim 2.2.12.

Since π is greater than the critical probability for the Bernoulli site percolation, there will be an innite cluster of easy sites C. We denote by C 0 the cluster of the origin surrounded by a path in C. ∂C 0 will be the outer boundary of C 0 , i.e., the sites in C that have a neighbor in C 0 . Then, we x a self avoiding innite path of easy sites v 0 , v 1 , . . . starting with the sites of ∂C 0 . That is, v 0 , . . . , v |∂C 0 | is a path that encircles C 0 , and then v |∂C 0 |+1 , . . . continues to innity. We will denote V = {v i } i∈N . Let H = V ∪ C 0 , and consider the restricted dynamics L H introduced in Denition 2.2.10. We split the dynamics in two for some local function f on H

L H f = L C 0 f + L V f, L V = i∈N c H v i (µ v i f -f ) , L C 0 = x∈C 0 c H x (µ x f -f ) .
Note that the boundary conditions of the C 0 dynamics depend on the state of the vertices in V and vice versa. We will denote by L C 0 0 the C 0 dynamics with empty boundary conditions 3.5. MIXED NORTH-EAST AND FREDRICKSON-ANDERSEN 1 SPIN FACILITATED MODELS ON Z 2 33

and by L V 1 the V dynamics with occupied boundary conditions. All generators come with their Dirichlet forms carrying the same superscript and subscript.

We will bound the gap of L H using the gaps of L V 1 , L C 0 0 and the following block dynamics:

L b f = (µ V (f ) -f ) + 1 ∂C 0 is empty (µ C f -f ) . Denote the spectral gaps of L V 1 , L C 0 0 ,L b , L H by γ V 1 ,γ C 0 0 ,γ b ,γ H .
γ b = 1 -1 -q |∂C 0 | , i.e., Varf ≤ 1 1- √ 1-q |∂C 0 | D b f for any local function f .
Let us now use this gap in order to relate γ H to γ V and γ C 0 :

Claim 3.5.3. γ H ≥ γ b min γ V 1 , γ C 0 0 . Proof. Fix a non-constant local function f . Varf ≤ 1 γ b D b f = 1 γ b [µ (Var V f ) + µ (1 ∂C 0 is empty Var C f )] ≤ 1 γ b 1 γ V 1 µ D V 1 f + 1 γ C 0 0 µ 1 ∂C 0 is empty D C 0 f ≤ 1 γ b max 1 γ V 1 , 1 γ C 0 0 D H f.
We are left with estimating γ V 1 and γ C 0 0 . Claim 3.5.4. There exists C > 0 such that γ

V 1 ≥ Cq 3 .
Proof. The Dirichlet form D V 1 is dominated by the Dirichlet form of FA1f on Z + , and that dynamics has spectral gap which is proportional to q 3 (see [START_REF] Cancrini | Kinetically constrained spin models[END_REF]).

For γ C 0 0 we will use the bisection method, comparing the gap on a box to that of a smaller box. For L ∈ N, let L NE L be the generator of the north-east dynamics in the box [L] 2 with empty boundary (for the north east model this is equivalent to putting empty boundary only above and to the right). Denote its gap by γ NE

[L] 2 . By monotonicity we can restrict the discussion to this dynamics, i.e.,

γ C 0 0 ≥ γ NE diam C 0 .
(3.5.1)

We will now bound γ NE (see also Theorem 6.16 of [START_REF] Cancrini | Kinetically constrained spin models[END_REF]).

Claim 3.5.5. γ NE [L] 2 ≥ e 3 log q L . Proof. We will prove the result for L k = 2 k by induction on k. Then monotonicity will complete the argument for all L. Consider the box [L k ] 2 , and divide it in two rectangles

R -= [L k-1 ] × [L k ] and R + = [L k-1 + 1, L k ] × [L k ].
We will run the following block dynamics

L bNE f = µ R + f -f + 1 ∂ -R + is empty µ R -f -f , where ∂ -R + is the inner left boundary of R + . Again, by Proposition 4.4 of [19], gap L bNE = 1 -1 -µ 1 ∂ -R + is empty = 1 -1 -q L k . Therefore for every local function f Varf ≤ 1 1 -1 -q L k D bNE f = 1 1 -1 -q L k µ Var R + f + 1 ∂ -R + is empty Var R -f ≤ 1 1 -1 -q L k µ 1 γ NE R + D NE R + f + 1 γ NE R - D NE R -f ,
where γ NE R , D NE R are the spectral gap and Dirichlet form of the north-east dynamics in R with empty boundary conditions for any xed rectangle R. We see that

γ NE [L k ] 2 ≥ 1 -1 -q L k γ NE [L k-1 ]×[L k ] .
If we repeat the same argument dividing

[L k-1 ] × [L k ] into the rectangles [L k-1 ] × [L k-1 ] and [L k-1 ] × [L k-1 + 1, L k ], we obtain γ NE L k-1 ×L k ≥ 1 -1 -q L k-1 γ NE [L k-1 ] 2 .
Hence,

log γ NE [L k ] 2 ≥ log γ NE [L k-1 ] 2 + 2 k log q -log 4, yielding log γ NE [L k ] 2 ≥ log q k n=1 2 n -k log 4
which nishes the proof.

We can now put everything together. Let L be the diameter of C 0 . By the second part of Claim 2.2.12 τ ≤ 1 + q q

1 γ r ≤ 1 + q q 1 1 -1 -q |C| min γ V 1 , γ C 0 0 (3.5.2)
≤ q -4L-1 .

Finally, we will use the sharpness of the phase transition for the site percolation on the dual graph (see [START_REF] Aizenman | Sharpness of the phase transition in percolation models[END_REF][START_REF] Duminil-Copin | A new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model[END_REF]):

Claim 3.5.6. There exists a positive constant c 2 that depends on π such that ν (L ≥ D) ≤ e -c 2 D for any D ∈ N.

Using this claim and equation (3.5.2)

ν (τ ≥ t) ≤ ν q -4L-1 ≥ t = ν L ≥ log t 4 log 1 q - 1 4
≤ C t c /log q .
3.6. Fredrickson-Andersen 1 spin facilitated model on the polluted Z 2

In this section we will analyze the KCM dened in equation (3.1.5). Rather than considering the time τ 0 , we will ask at which time scale correlation is lost. In the worst case, as explained in section 2.1, this is the relaxation time. We will see, however, that in a typical case this time is shorter.

We will study here the loss of correlation in the occupation of the origin. Clearly, if the origin is surrounded by absent sites it will not change, so we will only consider the case in which π is small enough, and that the origin is in the innite cluster of present sites. The following theorem shows that the relaxation time scales as q -3 , but already at times proportional to q -5/2 the correlation becomes small. Theorem 3.6.1. Consider the FA1f model on the innite cluster of present sites, and assume it contains the origin.

(1) There exists c > 0 such that the relaxation time is bigger than cq -3 .

(2) Fix a > 0. There exists ν-a.s. q 0 such that for all q ≤ q 0

E µ [η 0 (0)η 0 (t)] -µ (η 0 ) 2 ≤ q (1 -q) 2e -Ca ,
where t = aq -5 /2 (log 1 /q) 3/2 . Remark 3.6.2. For the case π = 0, i.e., the FA1f model on Z 2 , the relaxation time scales like q -2 (up to log corrections). We expect this to be the scale at which correlation is lost whenever the origin belong to the innite present cluster, but a proof will require more precise knowledge on the structure of this cluster. Still, the theorem above gives us a time scale which is faster than the spectral gap.

3.6.1. The spectral gap (proof of part 1 of Theorem 3.6.1). The gap of the model on polluted Z 2 is at most the gap on Z the percolation cluster contains paths of arbitrary length containing only vertices of degree 2, so any test function on Z could be shifted to such a path giving the same value of Df

Varf

. By [START_REF] Cancrini | Kinetically constrained spin models[END_REF] the spectral gap of the FA1f model on Z is at most cq 3 . 3.6.2. Loss of correlation (proof of part 2 of Theorem 3.6.1). The proof will be based on the methods of [START_REF] Martinelli | Towards a universality picture for the relaxation to equilibrium of kinetically constrained models[END_REF], by introducing a long-range constraint on the graph.

During this prove γ and C will denote generic positive constants that may change from one line to the other. They are allowed to depend on π but not on q.

Let H be an arbitrary directed graph with no oriented cycles. The orientation of the edges denes a partial order, where for two vertices x, y we say that x ≤ y if there is a path leading from x to y. Definition 3.6.3. B x (R) is the ball of radius R around a vertex x with respect to the graph distance (ignoring orientation). The forward ball is dened as

- → B x (R) = B x (R) ∩ {y : y ≥ x} . Definition 3.6.4. Let V ∈ N and a vertex x of G. The critical length at x with respect to V is l V x = min l : - → B x (l) ≥ V .
Definition 3.6.5. Fix two scaling functions l c : N → R, L : N → R (L l c ) and a vertex x 0 . We say that H has an l c forward growth in the domain B x 0 (L) if for all V ∈ N big enough and for all x ∈ B x 0 (L(V )) l V x ≤ l c (V ). In other words, l c forward growth means that all vertices in B x 0 (L(V )) have at least V sites in their forward ball of radius l c .

We now focus on the innite cluster G of present sites, and assume that π is small. Fix

l c = (α + β) √ V , (3.6.1)
L = Ce γV , for α, β big enough and C, γ small enough that will be determined later.

Proposition 3.6.6. Assume that there exists an innite up-right path starting at 0. Then there exists an orientation of G, for which G has an l c forward growth in the domain B 0 (L).

We will postpone the proof of this proposition to the end of the section, and continue using the orientation that it provides. Proposition 3.6.7. Let L 0 L be the generator of the FA1f dynamics on B 0 (L) with free boundary conditions, for V = 2 log 1 /q q . Then the gap of L 0 L is at least Cq 5/2 (log 1 /q) -3/2 .

The strategy of the proof will pass through a long range dynamics on B 0 (L):

c (l) x =        1 - → B x (l) contains an emtpy site 1 x 1 = L 0 otherwise.
Denote by L (l) the generator of the associated KCM on B 0 (L) and by D (l) its Dirichlet form.

Claim 3.6.8. There exists ν-a.s. q 0 > 0 such that for all q < q 0 the spectral gap of L (l) is greater than 1 4

, choosing V = 2 log 1 /q q and l = l c (V ).

Proof. By choosing q 0 small enough, l V x ≤ l for all x ∈ B 0 (l). That is, B x (l) contains at least V sites, which means that

µ c (l) x ≥ 1 -(1 -q) V .
Then we use Theorem 2 of [START_REF] Martinelli | Towards a universality picture for the relaxation to equilibrium of kinetically constrained models[END_REF]. This theorem says that in a KCM such as the one we consider, with oriented constraints, the spectral gap is greater than 1 4 if the constraint is likely enough compared to its range. In our case this condition translates to

sup z∈B 0 (L) x:z∈ -→ B x(lc) µ 1 -c (l) x ≤ 1 4 .
Since for every given z the number of vertices x such that z ∈ -→ B x (l c ) is bounded by l 2 c , the proof is nished once noting that l 2 c (1 -q) V ≤ (α + β) 2 V e -qV = (α + β) 2 q log 1 /q, which will be smaller than 1 4

for q 0 small enough.

In order to move from the long range dynamics to the short range dynamics we use a path argument.

Lemma 3.6.9. Fix l, and let x ∈ B 0 (L) and η such that c (l)

x (η) = 1. Then there exists a path η 0 , . . . , η N of congurations and a sequence of sites x 0 , . . . x N -1 such that [START_REF] Aizenman | Sharpness of the phase transition in percolation models[END_REF]

η 0 = η, η N = η x . (2) η i+1 = η x i i . (3) c x i (η i ) = 1. (4) N < 2l.
(5) max i # {empty sites of η i besides x i } ≤ # {empty sites of η 0 } + 1. (6) Each ip occurs at most once, i.e., if x i = x j and η i = η j , then i = j. (7) Let ξ x (η) be the rst empty site in -→ B x (l) for the conguration η according to the order induced by the edge orientation (and an arbitrary order in case of ambiguity). Then for all i either ξ x (η) = ξ x i (η i ) or ξ x (η) = ξ x i (η y i ) for a vertex y such that there is an edge from x i to y.

(8) For any x, x ∈ G and any conguration η there exist at most six possible congurations η such that (η , x ) is compatible with (η, x) . Compatibility means that η = η i and x = x i for some i < N , where η i and x i are the ith conguration and ith ip in the path dened for η and x.

Proof. We use a path similar to the one dened in [START_REF] Cancrini | Kinetically constrained spin models[END_REF]Theorem 6.4]. c (l)

x (η) = 1, so we can nd an oriented path z 0 , . . . , z t such that z 0 = x, z t = ξ x (η) and t ≤ l. Assume rst η x = 1. Then we start by ipping z t-1 , then z t-2 , then ip back z t-1 , ip z t-3 , ip back z t-4 and so on, until we ip z 0 . Then we ip z 1 again in order to ll it, and nish.

If, on the other hand, η x = 0, we start by ipping z 1 , then z 0 , then z 2 , then z 1 and so on, until ipping z t-1 , then z t-2 , and then z t-1 again.

Verifying conditions 1-7 is immediate. For condition 8 we note that if we know who ξ x (η) is and the initial occupation of x, we can reconstruct the initial conguration by setting all sites between x and ξ x to occupied. Property 6 guarantees that at most three values of ξ x (η) are possible, and the initial state of x could be either 0 or 1.

Proof of Proposition 3.6.7. Fix V = 2 log 1 /q q and l = l c (V ) and L as in equation (3.6.1). Recall equations 2.1.3 and 2.1.5. Using the path dened in Lemma 3.6.9 and denoting p = 1 -q

Varf ≤ 4 x c (l) x µ (Var x f ) = 4pq η µ (η) x c (l) x c x i (η i ) N i=1 ∇ x i f (η i ) 2 ≤ 8pql η x µ (η)
x η

1 (η ,x ) compatible with (η,x) c x (η ) (∇ x f (η )) 2 = 8l x η R η x , η (∇ x f (η )) 2 η x pqµ (η) R (η x , η ) 1 (η ,x ) compatible with (η,x) . c x (η ) = 1, so R is given by R η x , η = pq z∈B 0 (L)\{x } µ z (η z ) . Since µ (η) = z∈B 0 (L) µ z (η z ), the ratio pqµ (η) R (η x , η ) = µ (η x ) z =x :ηz =η z µ (η z ) µ (η z ) ≤ q -1 .
Hence, noting that x ∈ B l (x ),

Varf ≤ 50l 3 q -1 x η R η x , η (∇ x f (η )) 2 = 100q -1 l 3 Df.
This proves Proposition 3.6.7 by inserting l = (α + β) 2 log 1 /q q (recall the variational denition of the spectral gap in equation (2.1.6)).

We can now prove Theorem 3.6.1 using a nite speed of propagation argument, coupling the process generated by L with that generated by L 0 L . The coupling will be via the graphical construction we take the same initial conditions and same clock rings with the same coin tosses, so the only dierence is in the constraint on the boundary of B 0 (L). η denotes the process that evolves according to L, and η 0 the process evolving according to L 0 L .

Recall that t = aq -5 /2 (log 1 /q) 3/2 . Definition 3.6.10. Let B be the event, that there exist a sequence of times 0 ≤ t 1 ≤ • • • ≤ t k ≤ t and of sites x 1 , . . . , x k ∈ B 0 (L) such that x 1 is on the boundary of B 0 (L), x k = 0, and the clock of site x i rang at time t i for all i ≤ k.

Observation 3.6.11. In the coupling dened above, whenever B c occurs η 0 (t) = η 0 0 (t).

We can now estimate the correlation:

E µ [η 0 (0) η 0 (t)] = E µ [η 0 (0) η 0 (t) 1 B ] + E µ [η 0 (0) η 0 (t) 1 B c ] = E µ [η 0 (0) η 0 (t) 1 B ] + E µ η 0 0 (0) η 0 0 (t) 1 B c = E µ [η 0 (0) η 0 (t) 1 B ] -E µ η 0 0 (0) η 0 0 (t) 1 B + E µ η 0 0 (0) η 0 0 (t) , thus E µ [η 0 (0) η 0 (t)] -E µ η 0 0 (0) η 0 0 (t) ≤ 2P (B)
. Using the spectral gap of L 0 L we know that E µ η 0 0 (0) η 0 0 (t) -(1 -q) 2 ≤ q (1 -q) e -Cq 5/2 (log 1 /q) -3/2 t = q (1 -q) e -Ca .

The probability of B could be bounded by the possible number of paths x 1 , . . . , x k , times the probability that a Poisson random variable of parameter t will exceed k:

P (B) ≤ ∞ k=L 4 k m≥k t m e -t m! ≤ e -t ∞ k=L m≥k (4t) m m! .
By equation (3.6.1) and the choice V = 2 log 1 /q q , for q small enough L ≥ 20t, so (4t) m m!

/ (4t) m+1 (m+1)! = m+1 4t ≥ 5. That is, ∞ k=L m≥k (4t) m m! ≤ ∞ k=L n≥0 (4t) k k! 1 5 n ≤ 2 ∞ k=L (4t) k k! ≤ ∞ k=0 (4t) L L! 2 5 k ≤ 4 (4t) L L! ≤ 1.
In order to nish the proof of Theorem 3.6.1, consider x 0 in the innite present cluster, but not necessarily in the innite oriented cluster. Since G has an l c forward growth in the domain B x 0 (L -x 0 1 ), the above estimations hold also for the correlation of E µ [η x 0 (0) η x 0 (t)].

We are left with the proof of Proposition 3.6.6. Definition 3.6.12. G is the up-right percolating cluster of G, i.e., the sub-graph induced by the vertices connected to innity by an up-right path. Note that orienting all edges up or to the right gives a directed graph with no oriented cycles. Proof. Fix V , x ∈ G . We ask what is the probability that l V x > l c (V ). In other words, we look for the probability that

- → B x (l c ) < 1 α 2 l 2 c
. By [23] ν

1 l 2 c - → B x (l c ) < 1 α 2 < Ce -γl 2 c . Therefore ν ∃x ∈ B 0 (L) such that l V x > l c (V ) < 4L 2 Ce -γl 2 c = Ce -γV .
The result follows by the Borel-Cantelli lemma.

In order to extend this result to the entire G, we will use the uniqueness of the innite cluster of the oriented percolation, that will imply the following observation.

Observation 3.6.14. G \ G is a union of disjoint nite connected clusters.

Call the set of these cluster C. For L ∈ N, let where C is a positive constant.

C L = {G ∈ C | G ∩ B 0 (L) = ∅} .
Proof. Fix V . By [START_REF] Aizenman | Sharpness of the phase transition in percolation models[END_REF][START_REF] Duminil-Copin | A new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model[END_REF], for every x 1 ∈ Z 2 , the probability that its cluster in G \ G is contained in x 1 + [-D/2, D/2] is exponentially close to 1. In order for a graph H ∈ C to have a diameter larger than D it must contain such a vertex. Thus ν max

H∈C L(V ) diamH > D(V ) < C (L + D) 2 e -γD ,
and the result follows by the Borel-Cantelli lemma.

Proof of Proposition 3.6.6. In G take the usual up-right orientation. Then, for each H ∈ C, we take any arbitrary orientation such that all vertices point to G via an oriented path (this could always be done for nite H). We use Claim 3.6.15 and Claim 3.6.13 with α, β given in equation (3.6.1). Fix x ∈ B 0 (L). By Claim 3.6.15, the forward ball

- → B x (l c ) contains - → B x (α √ V )
for some x ∈ G . This ball alone contains more than V vertices by Claim 3.6.13, which concludes the proof.

Fredrickson-Andersen 2 spin facilitated model on polluted Z 2

Consider now the model dened in equation (3.1.6). The bootstrap percolation was studied in [START_REF] Gravner | Bootstrap percolation in a polluted environment[END_REF], where it is shown that when q and π tend to 0, if π q 2 is small enough the probability that the origin could be emptied tends to 1, but if π q 2 is big this probability tends to 0. In this section we will study τ 0 of the KCM. We will assume π < q 2+ε for some ε > 0, which will mean that the origin is likely to be emptiable. Even in this case the KCM is not ergodic for any xed ω there exists with probability 1 a square around the origin whose four corners are absent. The µ-probability that this square is entirely occupied is nonzero (though very small for typical ω), and when it is entirely occupied it could never change. This is very dierent from the previous models that we have analyzed, and we will have to take into account that τ 0 could be innite. Theorem 3.7.1. Fix ε > 0. Then for q small enough, with probability tending to 1 (with respect to the measure ν) the environment ω is such that P µ τ 0 > e q -1-ε < 4q ε/12 . Remark 3.7.2. The corresponding lower bound is left out for brevity, but since the bootstrap percolation is monotone, the time it would take to empty the origin is of order at least that of the non-polluted lattice, namely e c/q , which will then also bound the emptying time for the KCM. Thus (up to ε) the correct scaling is indeed e c/q . 3.7.1. Proof of Theorem 3.7.1. The idea of the proof is to nd a good event that happens with very high probability. Then use the results of section 2.3 in order to show that not too much time was spent in this good event before τ 0 . This, however, is only possible if τ 0 is small, since the fraction of time spent in the good event equals its probability, which is very high.

We start by xing two scales:

L = q -1-ε/3 , (3.7.1) l = q -L-1 ;
and dening a good square (which is not the same as Denition 3.2.4, though they play a similar role). Definition 3.7.3. A square (that is, a subset of Z 2 of the form x+[L] 2 ) is good if it contains at least one empty site in each line and in each column, and if none of its sites is absent. Claim 3.7.4. For q small enough ν ⊗ µ [L] 2 is good ≥ 1 -2q ε/3 . Proof. The probability that one of the sites of [L] 2 is absent is at most L 2 π, which is bounded by q -2-2ε/3 q 2+ε = q ε/3 . The probability that one of the line or columns of [L] 2 is entirely occupied is at most 2L (1 -q) L , which is asymptotically equivalent to 2q -1-ε/3 e -q -ε/3 . This bound tends to 0 much faster than q ε/3 , and the union bound given the proof of the claim.

Together with results from percolation theory (e.g. [22, 32, Theorem 1.33]) this implies the following corollary. Corollary 3.7.5. The ν ⊗ µ-probability that the origin belongs to an innite cluster of good boxes is at least 1 -16q ε/3 . Definition 3.7.6. Consider a path of good boxes. We say that the path is super-good if one of its boxes contains an empty line. Claim 3.7.7. Fix a self avoiding path of boxes whose length is l.

Then ν ⊗ µ (path is super-good | path is good) ≥ 1 -e -1/q .
Proof. Since the events {the path is good} and {one of the boxes contains an empty line} are both increasing we can use the FKG inequality, and bound this probability by the probability that a length l path of boxes (not necessarily good) does not contain an empty line. This conclude the proof, since 1 -q L l ≤ e -q L q -L-1 . Claim 3.7.8. For q small enough ν ⊗ µ (0 belongs to a super-good path of length l) ≥ 1 -25q ε/3 . Proof. By Corollary 3.7.5 the origin belongs to an innite cluster of good boxes with probability greater than 1 -16q ε/3 . In particular, it is contained in a self-avoiding path of length l. Then we use Claim 3.7.7 and the union bound to conclude. Definition 3.7.9. p SG (ω) is the µ-probability that the origin is contained in a super-good path of length l. Definition 3.7.10. We say that ω is low pollution if p SG (ω) > 1 -5q ε/6 . Claim 3.7.11. ν (low pollution) ≥ 1 -5q ε/6 . Proof. By Claim 3.7.8, ν (p SG ) ≥ 1 -25q ε/3 . Since p SG ≤ 1, Markov inequality will give the result.

From now on we think of a xed ω. Let E = {0 belongs to a super-good path of length l} , A = {η 0 = 0} .

We will use a path argument in order to bound µ T E A 1 E (recall Denition 2.3.1).

Lemma 3.7.12. Fix η ∈ E. Then there exists a path η 0 , . . . , η N of congurations and a sequence of sites x 0 , . . . x N -1 such that [START_REF] Aizenman | Sharpness of the phase transition in percolation models[END_REF]

η 0 = η, (2) η N ∈ A, (3) η i+1 = η x i i , (4) c x i (η i ) = 1, (5) N ≤ 4L 2 l, (6)
For all i ≤ N , η i diers from η at at most 3L points, contained in at most two neighboring boxes.

Proof. This path is constructed in the exact same manner as Lemma 3.3.8 (see also gures 3.3.1 and 3.3.2). The empty line that exists somewhere along the path could be propagated, until reaching the origin. The only dierence between this path and that of Lemma 3.3.8 is that the sites that used to be easy in the proof of Lemma 3.3.8 are now empty (which could only help).

Claim 3.7.13.

E µ T E A 1 E (η(0)) ≤ q -13L Proof. Recall equation (2.3.2). Thus E µ T E A 1 E (η(0)) = µ E η T E A 1 E (η) = µ T E A 1 E ,
and the the statement of the claim is equivalent to µ T E A 1 E ≤ q -10L . We use the path constructed above. Note rst that T E A (η N ) = 0, so for η ∈ E

T E A (η) = N -1 i=0 c x i (η i ) ∇ x i T E A (η i ) .
Then for q small enough µ

T E A 1 E 2 ≤ µ T E A 1 E 2 = η∈E µ (η) N -1 i=0 c x i (η i ) ∇ x i T E A (η i ) 2 ≤ η∈E µ (η) N N -1 i=0 c x i (η i ) ∇ x i T E A (η i ) 2 = η∈E N -1 i=0 η x 1 η =η i 1 x=x i µ (η) µ (η ) µ (η ) N c x (η ) ∇ x T E A (η ) 2 ≤ 4L 2 l q -3L η x η∈E N -1 i=0 1 η =η i 1 x=x i µ (η ) c x (η ) ∇ x T E A (η ) 2 ≤ 4L 2 l q -3L L 2 l 3L 2 3L 4L 2 l η µ (η ) x c x (η ) ∇ x T E A (η ) 2 ≤ q -13L D T E A = q -13L µ T E A 1 E ,
where the last equality is due to Corollary 2.3.2.

We are ready to prove Theorem 3.7.1. Assume ω is low pollution, an event with probability tending to 1 according to Claim 3.7.11. Let t = 1 -2q ε/12 q -14L . By Claim 3.7.13 and Markov's inequality

P µ T E A 1 E (η (0)) ≥ t ≤ 2q. Being low pollution means P µ (η (0) ∈ E) ≥ 1 -5q ε/6 , thus P µ T E A ≥ t = P µ T E A 1 E (η (0)) ≥ t + P µ T E A 1 E c (η (0)) ≥ t ≤ 1 2 q + P µ (η (0) ∈ E c ) ≤ 6q ε/6 .
On the other hand, for any s > 0,

E µ T E s = sµ (E) ≥ 1 -5q ε/
P µ T E s ≤ 1 -2q ε/12 s ≤ 3q ε/12 . Combining these inequalities for s = q -14L yields P µ (τ A ≥ s) ≤ P µ T E τ A ≥ T E s ≤ P µ T E τ A ≥ t + P µ T E s ≤ t ≤ 6q ε/6 + 3q ε/12 . CHAPTER 4
Models on the Galton-Watson tree While in chapter 3 the constraints were random, in this chapter we will consider a random graph G, which will be a Galton-Watson tree. Section 4.2 is based on [START_REF] Shapira | Metastable behavior of bootstrap percolation on Galton-Watson trees[END_REF] and discusses the bootstrap percolation, and Section 4.3 presents some preliminary results on the KCM.

Model, notation, and preliminary results

In this chapter we will discuss the bootstrap percolation and the FA model on a random graph G, chosen according to the Galton-Watson (GW) measure start at the root (denoted 0), and at each step give each of the leaves a random number of children, independently according to a distribution ξ. We x a threshold r and assume that ξ k (the probability to have k children) equals 0 for k < r.

Once G is chosen, we x the following constraint In [START_REF] Bollobás | Bootstrap percolation on Galton-Watson trees[END_REF] it is shown that, depending on ξ, the model could have a continuous or a discontinuous phase transition, and an explicit expression for the critical probability q c is found. Here we will study the time scales of the model, rst for the bootstrap percolation and then for the KCM.

Metastability of the bootstrap percolation

When studying the bootstrap percolation it will be convenient to use the notation φ G t for the probability that root is occupied at time t (so in particular φ G 0 = 1 -q). This probability random, since G is random, and we will denote its expectation by φ ξ t .

One particular case, that has been studied in [START_REF] Balogh | Bootstrap percolation on innite trees and non-amenable groups[END_REF][START_REF] Biskup | Metastable behavior for bootstrap percolation on regular trees[END_REF][START_REF] Luiz | Bootstrap percolation on homogeneous trees has 2 phase transitions[END_REF][START_REF] Chalupa | Bootstrap percolation on a Bethe lattice[END_REF], is the case of a rooted (d + 1)-regular tree, or equivalently ξ k = 1 k=d . Here, one can nd φ d t recursively using the relation

φ d t+1 = h d φ d t ;
(4.2.1)

h d (x) = (1 -q) P [Bin (d, 1 -x) ≤ r -1] . (4.2.2)

MODELS ON THE GALTON-WATSON TREE

For the GW tree, such a recursion still holds for the expected value φ ξ t :

φ ξ t+1 = h ξ φ ξ t ;

(4.2.3)

h ξ (x) = ∞ k=r ξ k h k (x). (4.2.4)
The relation in equation (4.2.3) allows us to nd the expected value of φ G t , but for a specic realization of G φ G t may dier from that value. For example, xing t, there is a nonzero probability that a nite neighborhood of the root will have many vertices of high degree, which will result in a smaller φ G t . However, we will see that φ ξ t describes almost surely another observable the density, i.e., the limiting fraction of occupied vertices.

First, denote by B(R) the ball of radius R around the root. We can then dene the R-density

at time t as ρ R (t) = |{occpied vertices in B(R) at time t}| |B(R)| .
It is natural to expect ρ R (t) to be close to φ ξ t , and this is indeed the case, as shown in the following proposition: Proposition 4.2.1. Fix t. Then lim R→∞ ρ R (t) = φ ξ t almost surely (in both the graph and the initial state measures).

We would like to understand the critical behavior of the bootstrap percolation, so following [START_REF] Balogh | Bootstrap percolation on innite trees and non-amenable groups[END_REF][START_REF] Bollobás | Bootstrap percolation on Galton-Watson trees[END_REF], we dene the critical probability

q c = inf [0,1] q : φ ξ ∞ = 0 . (4.2.5)
In order to analyze this criticality, dene

g k (x) = h k (x) (1 -q) x , (4.2.6) g ξ (x) = h ξ (x) (1 -q) x . (4.2.7)
In [START_REF] Bollobás | Bootstrap percolation on Galton-Watson trees[END_REF], the following fact is shown: Fact 4.2.2. Fix ξ. Then:

(1) For a given q, φ ξ ∞ is the maximal solution in [0, 1] of the equation g ξ (x) = 1 1-q , and 0 if no such solution exists.

(2) q c = 1 -

1 max [0,1] g ξ (x) .
We will consider here the behavior near criticality, at q slightly smaller than q c . Definition 4.2.3. For 0 < x < 1 and some positive δ, the δ-entrance time of x is τ -

x,δ (q) = min{t : φ ξ t < x + δ}, x,δ (q) = min{t : φ ξ t < x -δ}.

Definition 4.2.4. Fix δ > 0. We say that the critical point is δ-(ν 1 , . . . , ν n )-metastable at x 1 > • • • > x n > 0 if, for q q c , the following hold:

(1) τ - x 1 ,δ = O (1).

(2)

log τ + x i ,δ -τ - x i ,δ log(q-qc) q qc ---→ -1 + 1 2ν i for i = 1, . . . , n. (3) τ - x i+1 ,δ -τ + x i ,δ = O (
1) for i = 1, . . . , n and x n+1 = 0.

We say that the critical point is (ν

1 , . . . , ν n )-metastable at x 1 > • • • > x n if it is δ-(ν 1 , . . . , ν n )- metastable at x 1 > • • • > x n for small enough δ. See gure 4.2.1.
The following theorem gives a full classication of the metastability properties: Theorem 4.2.5. Fix ξ. Then the metastable behavior is determined by one of the following cases: Case 1. g ξ attains its maximum at 1. In this case the critical probability is 1. Case 2. g ξ has a unique maximum at 0. In this case the phase transition is continuous. At the critical point

log(φ ξ t ) log t t→∞ ---→ - 1 ν , (4.2.8)
where ν is determined by the asymptotic expansion g ξ (x) = 1 qc -Cx ν + o (x ν ). Case 3. The maximum of g ξ is attained at the points x 1 , . . . , x n for 1

> x 1 > • • • > x n > 0,
and possibly also at 0. In this case the phase transition is discontinuous. For i = 1, . . . , n we may write around x i

g ξ (x) = 1 1 -q c -C i (x -x i ) 2ν i + o (x -x i ) 2ν i (4.2.9)
for some C i > 0. Then the critical point is (ν 1 , . . . , ν n )-metastable at

x 1 > • • • > x n .
Remark 4.2.6. In the rst case, where the critical probability is 1, it is not clear whether or not an asymptotic expansion exists, since g ξ is not guaranteed to be analytic. When it does exist, one can recover a result similar to Case 3.

We can now state our main result, proving that all the dierent metastable behaviors described above can be attained. Actually, the proof of Theorem 4.2.7 is constructive: we provide for any choice of the widths of the multiple plateaus, an ospring distribution which realizes the corresponding metastable behavior. Theorem 4.2.7.

(1) Let ν ∈ N. Then there exists ξ such that the phase transition is continuous, and satises equation (4.2.8) at criticality. (2) Let (ν 1 , . . . , ν n ) ∈ N n . Then there exist ξ and

x 1 > • • • > x n such that the critical point is (ν 1 , . . . , ν n )-metastable at x 1 > • • • > x n .
This behavior is much richer than the dynamics on the regular tree in that case, if the transition is continuous it satises equation (4.2.8) with ν = 1, and when it is discontinuous it could only be 1-metastable at some point x 1 .

4.2.1. Proof of Proposition 4.2.1. The idea of the proof is to notice that the main contribution to the density comes from the sites close to the boundary, and then use their independence. Thus, we x a width w, and consider

ρ R,w (t) = |{occupied vertices in B (R) \ B (R -w) at time t}| |B (R) \ B (R -w)| .
First, we claim that ρ R (t) is approximated by ρ R,w (t) for large w. More accurately, we have |B (R -w)| ≤ 2 -w |B(R)|, which also implies that the number of occupied vertices in B (R) \ B (R -w) is the same as the number of occupied vertices in B (R), up to a correction

of order 2 -w |B(R)|. Thus ρ R (t) = ρ R,w (t) + O 2 -w . ( 4

.2.10)

We would now like to bound the distance between ρ R,w (t) and 1 -φ ξ t . Let ε > 0, and, by equation (4.2.10), take w big enough such that |ρ R (t) -ρ R,w (t)| < ε 2 uniformly in R. Note that ρ R,w (t) is a weighted average of the w random variables ρ R,1 (t) , ρ R-1,1 (t) , . . . , ρ R-w+1,1 (t), and consider one of these variables, ρ r,1 (t). This variable is the average of the random variables 1 v is empty for all vertices v of distance r from the root, and since these are independent Bernoulli random variables with mean φ ξ t , and since there are at least 2 R-w+1 such variables, we can use a large deviation estimate, yielding

P ρ r,1 (t) -φ ξ t > ε 2 ≤ e -c 2 R-w+1
for a positive c that only depends on ε and on φ ξ t . Since for φ ξ t to be far from ρ R,w (t) it must be far from at least one of the variables ρ R,1 (t) , ρ R-1,1 (t) , . . . , ρ R-w+1,1 (t), we have

P ρ R,w (t) -φ ξ t > ε 2 ≤ we -c 2 R-w+1 . (4.2.11)
Hence, ρ R (t) is ε-close to φ ξ t with probability larger than 1 -we -c 2 R-w+1

, which concludes the proof by the Borel-Cantelli lemma.

g k (x) = P [Bin (k, 1 -x) ≤ r -1] x = r-1 i=0 k i (1 -x) i x k-i-1 ;
therefore all monomials are of degree between k-r and k-1. The coecient of x k-r is k r-1 = 0, and the coecient of x k-1 is r-1 i=0 k i (-1) i , which is also nonzero since 0 < r -1 < k. This concludes the proof. Claim 4.2.9. g r (x) , . . . , g m (x) , x m-r+1 , . . . , x m-1 is a basis of the linear space of polynomials of degree smaller or equal to m -1.

Proof. Denote v 1 (x) = g r (x) , . . . , v m-r+1 (x) = g m (x) , v m-r+2 (x) = x m-r+1 , v m (x) =
x m-1 . By Claim 4.2.8, all v's are of degree smaller or equal to m -1. Moreover, the matrix whose (i, j) entry is the coecient of x j in the polynomial v i is upper triangular, with nonzero diagonal. This shows that {v i } m i=1 is indeed a basis.

We will also use Claim 3.9 of [START_REF] Bollobás | Bootstrap percolation on Galton-Watson trees[END_REF]:

Claim 4.2.10. For ξ k = r-1 k(k-1) , g ξ (x) = 1.
We are now ready to prove Theorem 4.2.5.

First, we note that g k (1) = 1 for all k, so in particular the series ∞ k=r ξ k g k (x) converges at x = 1. By Claim 4.2.8, the monomials of degree up to n of the partial sum N k=r ξ k g k (x) are xed once N > n + r. From these two facts we conclude that g ξ (x) is analytic in (-1, 1) and continuous at 1. Thus, cases 1, 2 and 3 exhaust all possibilities.

The result will then follow from general arguments of dynamical systems near a bifurcation point. Since the exact calculations are a bit tedious, we only give here a short sketch of the argument, referring to the appendix for the complete proof.

For case 2, the expression

φ t+1 = φ t -C (1 -q c ) φ ν+1 t + o(φ ν+1 t )
could be estimated by comparing to the dierential equation

dφ dt = -C (1 -q c ) φ ν+1 t .
This equation could be solved explicitly, yielding the asymptotics of equation (4.2.8).

For case 3, the approximate dierential equation will be

dφ dt = - x i 1 -q c (q -q c ) -C i (1 -q c ) x i (φ -x i ) 2ν i .
The solution of this equation has a plateau around x i , whose length diverges as (q-q c ) -1+

Q(x) = b 0 + • • • + b r-2 x r-2 such that (1) g ξ (x) = Const -x ν Q(x). (2) Q(x) > 0 for all x ∈ [0, 1].
This ξ, according to Theorem 4.2.5 and the fact that b 0 > 0, will indeed satisfy equation (4.2.8).

Rather than ξ, it will be easier to nd a sequence {χ k } ∞ k=r with a nite sum together with a polynomial P

(x) = a 0 + • • • + a r-2 x r-2 , such that (1) g χ (x) = k χ k g k (x) = 1 -x ν P (x).
(2) χ k ≥ 0.

(3) P (x) > 0 for all x ∈ [0, 1].

Taking ξ = 1 χ k χ k will then conclude the proof. Let

χ k =    r-1 k(k-1) r ≤ k ≤ ν + r -1 0 k ≥ ν + r. (4.2.12)
Using Claim 4.2.10 we may write

g χ (x) = 1 - ∞ k=ν+r r -1 k (k -1) g k (x)
.

By Claim 4.2.8 g χ is a polynomial of degree ν + r -2, therefore ∞ k=ν+r r-1 k(k-1) g k (x
) equals a polynomial of degree ν + r -2. Using again Claim 4.2.8, we can dene the polynomial

P (x) = ∞ k=ν+r r -1 k (k -1) g k (x)
x ν .

It is left to show that P (x) > 0 for all x ∈ [0, 1]. By equations 4.2.6 and 4.2.2, P (x) is nonnegative and could only vanish at x = 0. But by Claim 4.2.8, P (0) = r-1 (ν+r)(ν+r-1)

g ν+r (x)
x ν x=0 = 0. This concludes the rst part. Remark 4.2.11. Note that, by Claim 4.2.9, we can dene the projection Pr from the space of polynomials of degree at most r + ν -2 to its subspace spanned by x ν , . . . , x ν+r-2 with kernel spanned by g r (x), . . . , g ν+r-1 (x). Dene also M 0 to be the map from the space of polynomials of degree at most r -2 to the space of polynomials of degree at most r + ν -2 given by the multiplication by x ν . Then the rst of the conditions above can be written as PrM 0 P = Pr 1.

Since Pr • M 0 is bijective, this equation has a unique solution; and what we have shown in the proof is that this solution satises the necessary positivity conditions.

We will now prove the second part of the theorem. In analogy with the rst one, we will

nd ξ, Q(x) = b 0 + • • • + b r-2 x r-2 and x 1 > • • • > x n such that (1) g ξ (x) = Const -(x -x 1 ) 2ν 1 . . . (x -x n ) 2νn Q (x). (2) Q(x) > 0 for all x ∈ [0, 1].
Similarly to the previous part, we will look for {χ k } ν+r-1 k=r and P (x

) = a 0 + • • • + a r-2 x r-2 satisfying: (1) g χ (x) = k χ k g k (x) = 1 -(x -x 1 ) 2ν 1 . . . (x -x n ) 2νn P (x). (2) χ k > 0. (3) P (x) > 0 for all x ∈ [0, 1].
Note that choosing ν = 2ν 1 + • • • + 2ν n , χ k (dened in equation (4.2.12)) is strictly positive for r ≤ k ≤ ν + r -1. Since P was required to be strictly positive, we may hope that also after adding a small perturbation (x 1 , . . . , x n ) around 0 there still exists a positive solution P . More precisely, let us denote by M x 1 ,...,xn the multiplication by (x -x 1 ) 2ν 1 . . . (x -x n ) 2νn , acting on the polynomials of degree at most r -2. In particular, for x 1 , . . . , x n = 0 this is M 0 dened in 4.2.11. Then, we want to show that the solution of PrM x 1 ,...,xn P = Pr 1 satises the positivity conditions 2 and 3. By continuity of the determinant, when (x 1 , . . . , x n ) is in a small neighborhood of 0 the operator PrM x 1 ,...,xn is invertible. Moreover, in an even smaller neighborhood of 0 the polynomial (PrM x 1 ,...,xn ) -1 Pr1 will satisfy the positivity condition 3 matrix inversion is continuous, and the set of polynomials satisfying this condition is open and contains (PrM 0 ) -1 Pr1 by the rst part of the proof. Finally, since coordinate projections of 1 -(x -x 1 ) 2ν 1 . . . (x -x n ) 2νn (PrM x 1 ,...,xn ) -1 Pr1 with respect to the basis dened in Claim 4.2.9 are continuous in (x 1 , . . . , x n ), and since for (x 1 , . . . , x n ) = 0 condition 2 is satised, by taking (x 1 , . . . , x n ) in a further smaller neighborhood of 0 we are guaranteed to nd a polynomial P satisfying the required conditions. 1-q for three parameters q, intersecting g ξ at φ ξ ∞ . One sees here the discontinuity when 1 1-q equals the value of g ξ at the local maximum.

g ξ (x) is maximal at g ξ (0) = 6 5 , then it has a local minimum, followed by a local maximum (see gure 4.2.2).

In this case, recalling Fact 4.2.2, φ ξ t will have a discontinuity at this local maximum, that is, a second phase transition occurs. We may then expect that one can nd ξ giving rise to as many (decreasing) local maxima of g ξ as we wish:

Conjecture 4.2.12. Let ν

(1) 1 , . . . , ν (1)
n 1 , ν (2)
1 , . . . , ν

n 2 , . . . , ν (2)
nm . Then there exists g ξ , {q i } m i=1 and x (i) j 1≤i≤m, 1≤j≤n i such that q i is a critical point which is ν

(i) 1 , . . . , ν (i)
n i -metastable at

x (i) 1 , . . . , x (i)
n i .
Another possible phase transition, studied in [START_REF] Luiz | Bootstrap percolation on homogeneous trees has 2 phase transitions[END_REF] for the case of regular trees, is when innite empty clusters start to appear, but the density is still bigger than 0. Following the proof of Proposition 3.9 in [START_REF] Luiz | Bootstrap percolation on homogeneous trees has 2 phase transitions[END_REF], one sees that it applies also for the bootstrap percolation on GW trees, showing that the critical probability q (∞) c below which innite clusters no longer appear is strictly smaller than q c dened in equation (4.2.5), unless ξ k = 1 r .

Finally, a few open problems remain. First, though we have seen that the metastability above describes the almost sure density of specic realizations G of the tree, we do not have a quenched description of φ G t . Its value depends highly on the local structure, so it doesn't seem to be close to φ ξ t that we have analyzed, but we can still ask what is its metastability picture.

One easy observation is that by monotonicity φ G τ --φ G τ + is always positive (for τ -≤ τ + , as in Denition 4.2.3). Therefore, when φ ξ τ --φ ξ τ + is very small, Markov's inequality says that φ G τ --φ G τ + is small with high probability. That is, during a time interval in which φ ξ is at there will be a high probability for φ G to be at. This suggests that φ G , though it could be far from φ ξ , should have the same metastability structure. In order to prove this, however, one must also show that between plateaus the value of φ G changes by Ω(1), which is beyond my current reach.

Other than this specic model, more questions could be studied on the time behavior of the bootstrap percolation on random graphs, such as G n,p or the conguration model, for which the critical point is understood but, to my knowledge, not its metastability properties.

Fredrickson-Andersen model on a Galton-Watson tree one example

We will now discuss the spectral gap of the FA model on Galton-Watson trees (equation (4.1.1)). This model is still not well understood, so this section will be more a description of the thought process than the presentation of a complete result.

We focus on one specic example:

r = 2, ξ k =    1 2 k = 3 or 4 0 otherwise.
We start by a few observations that will direct us to the questions we can ask about this model. Proof. This is a consequence of the monotonicity of the Dirichlet form. Consider a test function f on our Galton-Watson tree G. We can take G to be a subtree of the 4-ary tree, and the Dirichlet form D 4 f will be greater than Df . For the other inequality, we can think of the trinary tree as a subtree of G, so D 3 f ≤ Df for any f dened on it. Observation 4.3.2. Let q c be the critical probability, starting from which the KCM is ergodic. q

(3) c and q (4) c will correspond to the dynamics on the 3and 4-ary trees. Then q (4) c < q c < q (3) c .

Proof. All three probabilities could be calculated explicitly using Fact 4.2.2. The values obtained are

q (3) c = 1 9 , q (4) c = 13 256 , q c = 31 √ 31 -154 89 + 31 √ 31 .
When q < q c the dynamics is not ergodic, so we will only be interested here in q > q c . When q > q (3) c the spectral gap is positive, since according to [START_REF] Martinelli | Kinetically constrained spin models on trees[END_REF] the spectral gap of L 3 is positive; and their bounds hold. Proposition 4.3.3. Fix q c < q < q (3) c . Then the spectral gap of L is 0.

Next, we would like to nd, for x on the boundary of T d ,

µ (c x Var x f ) ≤ q (1 -q) µ (f (ω x ) = f (ω)) .
Lemma 4.3.7. Consider the bootstrap percolation on T 3 , and x x on its boundary. Then the probability that r 3 is in the span of T 3 for η x but not for η is at most 0.3 l when l large enough. We call this probability π.

Proof. Let x = v 0 , . . . , v l = r 3 be the path from x to the root. Assume that the root is in the span of T 3 for η x but not for η. This means that for every 0 ≤ i ≤ l, the vertex v i is occupied, and exactly one of its two siblings is in the span of T 3 . Thus

π = l-1 i=0 (1 -q) 2φ (3) i 1 -φ (3) i ,
and the result follows since, for l big enough, φ

(3) i is close to 5 6 .
All that is left is to estimate the Dirichlet form:

Df = x µ (c x Var x f ) = x∈∂T 3 µ (c x Var x f ) ≤ x∈∂T d q (1 -q) 0.3 l = 0.09 3 l 0.3 l ≤ 0.9 l Varf.
The result follows since L -0.09 > L log 3 0.9 = 0.9 log .

By [42], if sup x∈G µ 1 -c (l) x < 1 l+1 then for any f Varf ≤ 8D (l) L f = 8 x µ c (l)
x Var x f .

(l) x ≤ 1 l+1 is at most e -L .
Proof. First, note that for a xed vertex, the expected value of µ 1 -c (l) x (with respect to the quenched variables) is φ ξ l . By the recursion formula equation (4.2.3), we can nd that, for l big enough, it is bounded by 2e -2 l-70

. Therefore, by Markov's inequality,

ν µ 1 -c (l) x > 1 l + 1 ≤ (l + 1) 2e -2 l-71 .
Then by the union bound

ν sup x∈G µ 1 -c (l) x > 1 l + 1 ≤ 4 L (l + 1) 2e -2 l-71 .
We will now use a path argument in order to bound the spectral gap.

Definition 4.3.9. Let G (l)

x be the tree of depth l rooted at x, and assume that c (l)

x = 1. We construct T 2 the emptying tree of x as follows:

(1) Put x in T 2 .

(2) Look for a leaf y of T 2 that has at least two children in the span of G (l)

x . If there is such y, add to T 2 rst two children of y that are in the span of G (l) x (according to some xed arbitrary order).

(3) Repeat step 2 until all leaves of T 2 have at most one child in the span of G (l) x .

Note that this construction is possible since c (l)

x = 1, and thus at each step T 2 is in the span of G (l)

x .

Observation 4.3.10. Fix x, let T 2 be its emptying tree for the conguration η, and take a leaf y of T 2 . Then the emptying tree of x for η y is also T 2 . x be the tree of depth l rooted at x, assume that c (l)

x = 1, and let T 2 be its emptying tree. Assume that all sites of T 2 other than its leaves are occupied. Then there is a path of congurations η 0 , . . . , η N and sites x 0 , . . . , x N -1 ∈ T 2 such that [START_REF] Aizenman | Sharpness of the phase transition in percolation models[END_REF]

η 0 = η and η N = η x . (2) η i+1 = η x i i , (3) c x i (η i ) = 1, (4) N ≤ 4 l+1 , ( 5
) η i diers from η at at most 2l sites.

Proof. Assume that such a path exists for each of the children of x (in T 2 ), but for l -1 rather than l. Then we empty both of them, then empty x, and then ip again both children.

The path could thus be constructed by induction. Definition 4.3.12. Let G (l)

x be the tree of depth l rooted at x, assume that c (l)

x = 1, and let T 2 be its emptying tree. The canonical path η 0 , . . . , η N is dened by

η i = η ∧ η i ,
where η 0 , . . . , η N is the path constructed in Claim 4.3.11 for the initial state in which all are occupied except for the leaves of T 2 that are empty.

We are now ready to apply the path argument. Fix a local function f and a vertex x ∈ G. µ c (l) x Var

x f = q (1 -q) η µ (η) c (l) x (∇ x f ) 2 = q (1 -q) η µ (η) N i=1 c x i (η i ) ∇ x i f (η i ) ≤ 4 l+1 η µ (η) N i=1 (c x i (η i ) ∇ x i f (η i )) 2 = 4 l+1 η µ (η ) x η 1 η =η i 1 x =x i N i=1 µ (η) µ (η ) (c x (η ) ∇ x f (η )) 2 .
The ratio µ(η) µ(η ) could be bounded by q 1-q 2l . Then, if we know η and x, we can construct T 2 .

Therefore, if we also know i, η could be one of 2 2l congurations. Finally, we can bound 1 x =x i by 1, and obtain µ c (l) x Var x f ≤ 4 l+1 10 2l 2 2l 4 l+1

x ∈Gx η

µ (η ) (c x (η ) ∇ x f (η )) 2 .
All that is left is to combine this result with equation (4.3.1):

Varf ≤ 8D (l) L f = 8 x µ c (l) x Var x f ≤ 128 6400 l 4 l x ∈G η µ (η ) (c x (η ) ∇ x f (η )) 2 = C L log 2 25600 Df. CHAPTER 5
The Kob-Andersen model on Z d

This chapter presents a joint work with Fabio Martinelli and Cristina Toninelli, that also appears in [START_REF] Martinelli | Diusive scaling of the Kob-Andersen model in Z d[END_REF]. It concerns with the Kob-Andersen model, which is a kinetically constrained lattice gas model. Particles are allowed to jump to a nearby empty site, as long as the constraint is satised, and it is in a sense the Kawasaki version of the Fredrickson-Andersen model. In [START_REF] Cancrini | Kinetically constrained lattice gases[END_REF] the relaxation time of the Kob-Andersen model has been studied in dimension 2 and parameter k = 2 (to be dened later on). By a simple comparison with the simple exclusion process this relaxation time, when considering the model in a box of side L and free boundary, is at least CL 2 . However, [START_REF] Cancrini | Kinetically constrained lattice gases[END_REF] only show an upper bound of L 2 (log L) 4 . In this work we have proven a diusive (i.e., CL 2 ) scaling in all dimensions. Moreover, we are able to bound the constant C, showing that its divergence at small q is at most that of the relaxation time in the corresponding

Fredrickson-Andersen model.

The Kob-Andersen model and the main result

Given an integer L, and a parameter q ∈ (0, 1),

we let Λ = [L] d ∂Λ = {x ∈ Λ : ∃y / ∈ Λ with x -y 1 = 1}.
and consider the probability space (Ω Λ , µ Λ ) where

Ω Λ = η ∈ {0, 1} Z d : η x = 0 for all x / ∈ Λ and µ Λ is the product Bernoulli(1-q) measure. Given η ∈ Ω Λ and V ⊂ Λ, we shall say that V is empty (for η) if η x = 0 ∀x ∈ V. Fix an integer k ∈ [2, d]
and, for any given a pair of nearest neighbor sites x, y in Λ, write c xy (•) for the indicator of the event that both x and y have at least k -1 empty neighbors among their nearest neighbors in Λ without counting x, y

c xy (η) = 1 if z: x-z 1 =1,z =y (1 -η z ) ≥ k -1 and z: y-z 1 =1,z =x (1 -η z ) ≥ k -1, 0 otherwise. (5.1.1)
and set

η xy z :=      η z if z / ∈ {x, y} η x if z = y η y if z = x. η x z := η z if z = x 1 -η x if z = x.
The Kob-Andersen model in Λ with parameter k, for short the KA-kf model, with constrained exchanges in Λ and unconstrained sources at the boundary ∂Λ is the continuous time Markov process dened through the generator which acts on local functions f :

Ω Λ → R as Lf (η) = x,y∈Λ x-y 1 =1 c xy (η)[f (η xy ) -f (η)] + x∈∂Λ [(1 -η x )(1 -q) + η x q][f (η x ) -f (η)]. (5.1.2)
In words, every pair of nearest neighbors sites x, y such that c xy (η) = 1, with rate one and independently across the lattice, exchange their states η x , η y . In the sequel we will sometimes refer to such a move as a legal exchange. Furthermore every boundary site, with rate one and independently from anything else, updates its state by sampling it from the Bernoulli(1-q) measure. Notice that these latter moves are unconstrained and that for k = 1 the KA-1f chain coincides with the symmetric simple exclusion in Λ with sources at ∂Λ. It is easy to check that the KA-kf chain is reversible w.r.t µ Λ and irreducible thanks to the boundary sources. Let T rel (q, L) be its relaxation time i.e. the inverse of the spectral gap in the spectrum of its generator L Λ . Theorem 5.1.1. For any q ∈ (0, 1) there exists a constant C(q) such that

L 2 ≤ T rel (q, L) ≤ C(q)L 2 .
Moreover, as q → 0 the constant C(q) can be taken equal to

C(q) =    exp (k-1) c/q 1/(d-k+1) if 3 ≤ k ≤ d, exp(c log(q) 2 /q) if k = 2 ≤ d, (5.1.3)
where exp (r) denotes the r-times iterated exponential and c is a numerical constant.

Remark 5.1.2. The lower bound in the theorem follows from a simple comparison of the KA-kf chain with the symmetric simple exclusion in Λ and it was already established in [START_REF] Cancrini | Kinetically constrained lattice gases[END_REF].

An interesting open problem already for k = 2 is to prove a diusive lower bound of the form C (q)L 2 with C (q) diverging to +∞ as q → 0.

Proof of the main theorem

The standard variational characterization of the spectral gap of L implies immediately that the upper bound on T rel (q, L) of Theorem 5.1.1 is equivalent to the Poincaré inequality

Var(f ) ≤ C(q)L 2 D(f ) ∀ f : Ω Λ → R, (5.2.1)
where C(q) is as (5.1.3), Var(f ) denotes the variance of f w.r.t. the reversible measure µ and D(f ) is the Dirichlet form associated to the generator (5.1.2)

D(f ) = x,y∈Λ x-y 1 =1 µ c xy (∇ xy f ) 2 + x∈∂Λ µ Var x (f ) , (5.2.2) where ∇ xy f (η) := f (η xy ) -f (η) Var x (f ) is the local variance w.r.t. η x .
We will prove (5.2.1) in several steps. The rst step consists in proving a coarse-grained constrained Poincaré inequality with long range constraints (see Proposition 5.2.11) under the assumption that the probability π l (k, d) of a certain good event (see Denition 5.2.2) is suciently large. Here l is the mesoscopic scale characterizing the coarse-grained construction and 2 ≤ k ≤ d is the parameter of the KA-model. The necessary tools for this part are developed in Sections 5.2.1 and 5.2.2.

The second step (see Section 5.2.4) consists developing canonical ows techniques for the KA model in order to bound from above the r.h.s. of the coarse-grained Poincaré inequality by C(l, q)(L/l) 2 D(f ), with C(l, q) ≤ e O(l d-1 (| log(q)|+log(l))) (see Proposition 5.2.45 and Corollary

5.2.46).

The nal step (see Section 5.2.6) proves that it is possible to choose l = l(q, k, d) in such a way that π l (d, k) is large enough and C(l, q) ≤ C(q) as q → 0, where C(q) is as in (5.1.3).

Coarse graining.

Let l be such that N := L/l ∈ N. W.l.o.g. we also assume that 1 2

√ N ∈ N. Later on (see Section 5.2.6) we will choose l as a function of q and suitably diverging as q → 0. We will then consider the coarse grained lattice of boxes with side l. We will denote this lattice by Z d l . As a graph it is equal Z d , but its elements represent coarse grained boxes rather than sites. Let also Λ l = [N ] d ⊂ Z d l , where we use the notation [N ] for the set {1, . . . , N }. Vertices of the coarse-grained lattice Z d l will always be denoted using letters i, j, . . . while vertices of the original lattice Z d will be denoted x, y, . . . . The boundary ∂Λ l ⊂ Λ l of Λ l will consists of the vertices of Λ l with at least one nearest neighbor (in Z d l ) not in Λ l . We partition the lattice Z d into mesoscopic boxes of side l indexed by vertices in

Z d l . If B := [l] d then B i will denote the box B + li, i ∈ Z d l .
In particular Λ = ∪ i∈Λ l B i . Sometimes we shall simply write the box i meaning the box B i . For x ∈ Z d we denote by B(x) the mesoscopic box containing x. Definition 5.2.1 (Frameable congurations). Given the d-dimensional cube C n = [n] d and an integer j ≤ d we dene the j th -frame of C n as the union of all (j -1)-dimensional faces containing the vertex (1, . . . , 1) of C n . Next we introduce the set of (d, j)-frameable congurations of {0, 1} Cn as those congurations which are connected by legal KA-jf exchanges inside C n to a conguration for which the j th -frame of C n is empty.

We are nally ready for our denition of a box being good for a given conguration. Definition 5.2.2 (Good boxes). Given η ∈ E Λ , we say that the box B is (d, k)-good for η if all (d -1)-dimensional slices of B parallel to the axes are (d -1, k -1)-frameable for all congurations η ∈ E Λ that dier from η in at most one site. The probability that the d-dimensional box B is (d, k)-good will be denoted by π l (d, k). Notation warning Whenever the value of d, k is clear from the context we shall simply write that a box is good if it is (d, k)-good. We shall also say that a

vertex i ∈ Z d l is (d, k)-good if the box B i is (d, k)-good.
5.2.2. Tools from oriented percolation. In this section we collect and prove certain technical results from oriented percolation which will be crucial to prove the aforementioned coarse-grained constrained Poincaré inequality. We shall work on the coarse-grained lattice Z d l so that any vertex i ∈ Z d l is representative of the mesoscopic box B i in the original lattice Z d . The main result here is Proposition 5.2.8. Throughout this section the parameters d, k will be kept xed. Definition 5.2.4 (Paths). An up-right or oriented path γ in Z d l starting at i and of length n ∈ N is a sequence γ (1)

, . . . , γ (n) ⊂ Z d l such that γ (1) = i and γ (t+1) ∈ γ (t) + e 1 , γ (t) + e 2 for all t ∈ [n -1]. γ is focused if d γ (t) := d γ (t) , {j : j = i + s( e 1 + e 2 ), s ∈ N} satises max t∈[n] d γ (t) ≤ √ n.
Two consecutive elements of γ form an edge of γ and we say that γ, γ are edge-disjoint if they do not share an edge. Finally, we say that γ is good if γ (t) is good for all t ∈ [n].

Definition 5.2.5 (Good family of paths). Fix i ∈ Z d l . A family of paths G is said to form a good family for i if the following conditions hold:

(1) All paths in G are good up-right focused paths starting at i of length 2N .

(2) The paths of G are almost edge-disjoint i.e. any common edge is at distance at most √ N from i.

(

) |G| ≥ 1 2 √ N . 3
Remark 5.2.6. Since each vertex can be starting point of at most two edge disjoint paths, the cardinality of G necessarily satises |G| ≤ 2 √ N .

Given i ∈ Z d l let D i be the segment

D i = i + 1 2 √ N -t e 1 + 1 2 √ N + t e 2 | - 1 2 √ N ≤ t ≤ 1 2 √ N .
(

Let also H (n) , V (n) be the rectangular subsets of the form

H (n) = {j ∈ Z d l : j = i + a e 1 + b e 2 , a ∈ [0, l n ], b ∈ [0, l n-1 ]} V (n) = {j ∈ Z d l : j = i + a e 1 + b e 2 , a ∈ [0, l n-1 ], b ∈ [0, l n ]} from V (1) ≡ V (n 1 )
we can rst follows the lowest hard crossing of H (n 2 ) until we reach a hard crossing of V (n 2 ) . Then we follow the latter until meeting a hard crossing of H (n 3 ) and so on. At the end of this procedure the set V (1) , and a fortiori the box i, becomes connected by a good up-right path to the right short side of H (n * ) i

and hence also to one of the vertices of D i ∩ H n * . The same construction can be repeated symmetrically by inverting the role of H

(n) n and V (n) i .
Therefore we conclude that there exists a good up-right path connecting i to D i ∩ H n * and a good up-right path connecting i to D i ∩ V n * .

Suppose without loss of generality that

l n * = √ N . Then, since |D i ∩ Z d l ∩ H n * | = |D i ∩ Z d l ∩ V n * | =
√ N /10 and since each each vertex can be the starting point of at most two edge disjoint paths, event A guarantees that there are at least (1.9

√ N -2 √ N /10 -2 √ N /10)/2 = 0.75 √ N sites in D i \ (H n * ∪ V n *
) that are the starting point of an edge-disjoint up-right paths crossing R i . Thus, by using event B and noticing that

|D i \ (H n * ∪ V n * ) ∩ Z d l | = 0.8
√ N , we get that there are at least 0.65

√ N vertices of D i \ (H n * ∪ V n *
) which are at the same time the starting point of edge-disjoint up-right paths crossing R i and the ending points of up-right paths from ∪ t∈[0,

√ N ] {i + t e 1 } ∪ {i + t e 2 } to D i . Using now the fact that i is connected by a good up-right path to the set D i ∩ H n * and to the set D i ∩ V n * , we conclude that there exist at least 0.65

√ N

good up-right paths from i to D i + 2N ( e 1 + e 2 ) which, after crossing D i become edge-disjoint and never leave R i . The thick path of Fig. 5.2.1 is one of these paths, drawn up to its crossing with D i (R i is not depicted in the gure due to lack of space). These paths form the sought good family as required.

Our next task is to prove that A, B and C n are very likely if π l := π l (d, k) is suciently close to one uniformly in n. As proved in Section 5.2.6 that will be the case if the mesoscopic scale l is suitably chosen as a function of q, d, k.

Proposition 5.2.8. For any λ > 0 there exists π * < 1 such that for π l ≥ π * and all n, N ∈ N

(a) µ(C n ) ≥ 1 -e -λl n-1 , (b) µ(B) ≥ 1 -e -λ √ N , (c) µ(A) ≥ 1 -e -λ √ N .
In particular a family of good paths starting at i exists w.h.p if π l is suciently close to one.

Proof. (a) This can be proven by a contour argument. Consider the rectangle V (n) , and assume that it does not contain a good hard crossing. Then consider the path on the dual lattice that forms the upper contour of the set of sites that are connected to the bottom of the rectangle via an up-right good path. Since there is no vertical crossing, this path necessarily takes l n steps to the right and ends somewhere on the right boundary of V (n) . By using the fact that each time this dual path makes a step to the right or downwards, this implies the presence of a bad vertex, it is not dicult to prove that for π l suciently large depending on λ it holds µ(there is not a good hard crossing) = µ(C c n ) ≤ e -λln (b) Consider the down-left good oriented paths starting from sites of D i \ (H n * ∪ V n * ). The event B certainly occurs if at least 7/8 of the points in this set are the starting point of an innite down-left good oriented path. The upper bound on the probability of B then follows directly from [23, Theorem

(c) The main tool here is the max-ow min-cut theorem (see e.g. [START_REF] Bollobás | Modern graph theory[END_REF]). For any directed graph (V, E) we consider a capacity function, giving every edge e ∈ E a positive number c e ∈ R + .

For two sets of vertices s and t, we say that a ow from s to t is a positive function of the edges, f : E → R + such that :(i) for all e ∈ E it holds f e ≤ c e , (ii) for all v ∈ s ∪ t it holds u:(u,v)∈E f u,v = w:(v,w)∈E f v,w , namely for vertices outside s ∪ t the incoming ow equals the outgoing ow. The value of the ow is dened as the total ow going in t (which is the same as the ow leaving s), namely w∈t v:(v,w)∈E f v,w . A cut (S, T ) will be a partition of V in two subsets S and T , such that s ⊆ S and t ⊆ T . The value of the cut is the the sum of capacities of the edges pointing from S to T . Theorem 5.2.9. (Max-Flow Min-Cut theorem) The maximal value of a ow is equal the minimal value of a cut. Moreover, if all capacities are in Z, there is a maximal ow with integer values.

In order to use this theorem, we rst dene our graph. The vertex set is

V = i + a e 1 + b e 2 : a, b ∈ [N ] , a + b ≥ √ N , |a -b| ≤ √ N ∩ Λ l ,
and the edges are E = {(j, j ) : j is good and j ∈ {j + e 1 , j + e 2 }} .

We dene s:

s = j ∈ V : i -j 1 = √ N ,
and t:

t = V ∩ {j | ( e 1 , j) = N or ( e 2 , j) = N } .
Giving all edges capacity 1, the maximal value of a ow will be the number of edge disjoint paths that we are after. We have thus reduced the problem to the following claim: Claim 5.2.10. If π l is large enough, for the graph above with probability greater than 1 -e -λ √ N , the value of any cut is at least 1.9 √ N .

Proof of the claim. In order to prove the claim, we will construct, for every xed cut (S, T ), a dual path γ * S,T that will separate S from T . We will then show that such a path intersects at least 1.9

√

N edges in E.

1 Though the Theorem is stated for the contact process, it also holds for oriented percolation as stated in [START_REF] Durrett | Large deviations for the contact process and two-dimensional percolation[END_REF]).

First, let us dene a dual graph V * for some xed (S, T ). Its vertices will be the faces of Λ l that have at least three neighbors in V . That is,

V * = i * ∈ Λ l + 1 2 e 1 + 1 2 e 2 : # {i ∈ V : i * -i 1 = 1} ≥ 3 . i √ N

Right boundary

Left boundary Proof. Its (directed) edges will depend on the cut (S, T ). For i * , j * ∈ V * , (i * , j * ) is an edge if i * -j * 1 = 1, and if it has a site of S to its left and a site of T to its right. We will separate the vertices of V * in three parts:

(1) The right boundary i +

√ N + 1 2 + a e 1 + 1 2 + a e 2 : a ∈ [N ] ∪ V * , (2)
the left boundary i +

√ N + 1 2 + a e 1 + 1 2 + a e 2 : a ∈ [N ] ∪ V * , (3)
the interior, which will include all vertices that are neither in the right nor in the left boundary.

Focusing on a xed vertex j * ∈ V * , we can count the edges going into j * and the edges going out of j * if we know which of the neighboring vertices of V (namely {j ∈ V : j * -i 1 = 1}) are in S and which are in T . By checking all possibilities, one can verify that the incoming degree of a vertex in the interior of V * equals its outgoing degree (see right part of Fig. 5.2.3).

At the boundaries, however, there could be vertices that have an outgoing degree dierent

j * a = i + √ N + 1 2 + a e 1 + 1 2
+ a e 2 . Let j + a = j * a + 1 2 e 1 + 1 2 e 2 and j - a = j * a -1 2 e 1 -1 2 e 2 . If both j + a and j - a are in S, or if both are in T , then the incoming degree of j * a is the same as its outgoing degree. However, if j + a ∈ S and j - a ∈ T then the incoming degree is 1 and the outgoing degree is 0. For the case j + a ∈ T and j - a ∈ S, we have an outgoing degree 1 and incoming degree 0. j + a = j - a+1 , therefore the total outgoing degree of sites on the right boundary is # a : j - a ∈ S, j - a+1 ∈ T and the total incoming degree is # a : j - a ∈ T, j - a+1 ∈ S .

But since the rst site (i.e., j - 0 ) is in s and the last site is in t, the incoming degree must be smaller by 1 than the outgoing degree.

By the exact same argument, we can nd that the incoming degree of the left boundary is larger by 1 than its outgoing degree. This implies that there exists a dual path γ * = j

(1) * , . . . , j

, where j

(1) * in on the right boundary and j

(n) * is on the left boundary. In partic-

ular, n ≥ 2 √ N .
The value ospring the cut (S, T ) is at least the number of edges in E pointing from S to T and crossing γ * . Thanks to the choice of the direction of the edges in V * , this could be written as # t : j (t+1) * -j (t) * ∈ {-e 1 , e 2 } and j (t+1) * , j (t) * crosses an edge in E .

We therefore consider the number of steps that γ * takes in each direction:

R = # t : j (t+1) * -j (t) * = e 1 , L = # t : j (t+1)
1 -(2 d -1)(1 -π l ), the proof of the latter is now identical to the one given in [START_REF] Martinelli | Towards a universality picture for the relaxation to equilibrium of kinetically constrained models[END_REF]Theorem 2.6]. 5.2.4. Constructing the T -step moves. In this section we will construct a set of T -step moves sequences of at most T ∈ N legal moves for the KA dynamics that could be chained together in order to ip the state of an arbitrary point x ∈ Z d .

The next denition describes how to move from one conguration to the other using only legal KA exchanges. Definition 5.2.12. Given a nite connected subset V of Λ and M ⊂ Ω, a T -step move M = (M 0 , . . . , M T ) taking place in V and with domain Dom(M) = M is a function from M to Ω T +1 such that the sequence M η = (M 0 η, . . . , M T η) , η ∈ M, satises:

(1) M 0 η = η, (2) for any t ∈ [T ], the congurations M t-1 η and M t η are either identical or linked by a legal KA-transition contained in V . Definition 5.2.13. Given a T -step move M its information loss Loss t (M ) at time t ∈ [T ]

is dened as

2 Losst(M ) = sup η ∈Dom(M ) # {η ∈ Dom(M) | M t η = M t η , M t+1 η = M t+1 η } .
In other words, knowing M t η and M t+1 η, we are guaranteed that η is one of at most 2 Losst(M ) congurations. We also set Loss(M ) := sup t Loss t (M ). The energy barrier of M is dened as

E(M ) = sup η∈Dom(M ) sup t∈[T ]
(# {empty sites in M t η} -# {empty sites in η}) .

The main result is as follows. Recall that

Q i = i + {0, 1} d \ {0} d ⊂ Z d l and that N = L/l.
Proposition 5.2.14. Fix i ∈ Λ l and x ∈ B i . If i + e 1 + e 2 ∈ Λ l x also an up-right path γ connecting i + e 1 + e 2 to ∂Λ l . Then there exists a T -step move M with Dom(M) = {η | γ is good and all j ∈ Q i ∩ Λ l are good} , taking place in ∪ j∈γ B j ∪ (Q i ∩ Λ l ) and such that, for all η ∈ Dom(M) and all t ∈ [T ], M t η ∈ Dom(M) and M T η is the conguration η ipped at

x. Moreover M can be chosen to satisfy:

T ≤ CN l λ , T (j) M ≤ Cl λ ∀j ∈ Λ l for k = 1, 2, T ≤ CN 2 l d , T (j) M ≤ C2 l d ∀j ∈ Λ l for k ≥ 3, and Loss(M) ≤ C log 2 (l) l d-1 , E (M) ≤ Cl d-1
for all k, where T (j) M is the set of indices t ∈ [T ] such that for some η ∈ Dom(M) the congurations (M t η, M t+1 η) are linked together by a legal KA-transition inside B j . The constants C, λ may depend only on k and d.

We start with a few denitions that we will use in this construction of this move.

# {1 ≤ α ≤ d : x α = 1} ≥ d -k + 1 (5.2.6)
then η (x) = 0. In particular, being framed does not depend on permutations of e 1 , . . . , e d , but only on their signs.

Proof. By induction. For k = 1 the box is always framed i the site (1, . . . , 1) is empty, which is exactly the condition given in equation (5.2.6). For d = k -1 equation (5.2.6) is satised for all x, therefore the box must be entirely empty. For d ≥ k > 1 equation (5.2.6) is satised i: We continue with more denitions that will help us describing T -step move. Observation 5.2.22. Let M be a T -step move taking place in V . Then the loss of M is at most the number of sites in V . Definition 5.2.23. Fix a T -step move M taking place in V ⊆ Λ, η ∈ DomM , and a sequence of permutation (σ 0 , . . . , σ T ) on V , such that σ -1 t-1 σ t is either the identity or a nearest neighbors transposition for all t ∈ [T ]. We say that (σ 0 , . . . , σ T ) is compatible with M η if for all t ≤ T and x ∈ Λ M t η (x) = η (σ t x) .

(1) x 1 = 1 and # {2 ≤ α ≤ d : x α = 1} ≥ (d -1) -k + 1, (2) x 1 = 1 and # {2 ≤ α ≤ d : x α = 1} ≥ (d -1) -(k -1) + 1.
We say that M η and the permutation σ are compatible if there exists such a sequence with σ T = σ. If the sequence (σ 0 , . . . , σ T ) does not depend on η we say that M η and σ are deterministically compatible.

Observation 5.2.24. Let M be a T -step Λ, and assume that it is deterministically compatible with a permutation σ. Then LossM = 0. Observation 5.2.25. Fix a T -step move M taking place in V ⊆ Λ. Let σ be a random permutation compatible with M , i.e., for all η ∈ DomM the permutation σ (η) is compatible with M η. Then there exists a T step move M with the same domain that is also compatible with σ, and T = |V |!. If σ is deterministic and M is deterministically compatible with σ, than M will also be deterministically compatible with σ.

Proof. There could only be |V |! unique permutations on V , so any sequence (σ 0 , . . . , σ T ) of length T ≥ T contains two equal permutations σ t = σ s for t < s. It could then be shortened by removing the entries t + 1, . . . , s. Continue this procedure until T ≤ T and pad it to obtain a T time move. Definition 5.2.26. Let M 1 be a T 1 -step move and M 2 a T 2 -step move. Assume that for all η ∈ DomM 1 , the conguration M 1

T 1 η is in DomM 2 . Then the composition M 2 • M 1 will be a (T 1 + T 2 )-step move with DomM 2 • M 1 = DomM 1 , such that M 2 • M 1 t η =    M 1 t η t ≤ T 1 M 2 t-T 1 M T 1 η T 1 < t ≤ T 2 .
Observation 5.2.27. Fix M 1 a T 1 -step move and M 2 a T 2 -step move. Then the loss of their composition, when it is dened, is LossM

2 • M 1 = max LossM 1 , Loss T 1 M 1 + LossM 2 .
Another operation we on moves is choosing one out of a set of moves for dierent values of η.

Definition 5.2.28. Let M 1 , . . . , M n be a sequence of T -step move. Fix a set M ⊂ Ω Λ , and a choice function h form M to [n]. Assume that for every η ∈ M η ∈ DomM h(η) .

Then we may dene a T -step move M with domain M such that

M t η = M h(η) t η.
Observation 5.2.29. Consider a sequence M 1 , . . . , M n and a choice function h as in the above denition, and let M be the corresponding move. Then LossM ≤ log 2 n + sup i∈[n] LossM i .

We are now ready to construct some basic T -step moves, by recursion on d and k, and using previously dened moves on smaller d and k. Unless written otherwise, moves are assumed to be dened for the KAkf in d dimensions.

Proposition 5.2.30. Fix x 0 ∈ Λ, l 2 , . . . , l d . Let

F 1 = x 0 + {1} × [l 2 ] × • • • × [l d ] and F 2 = x 0 + {2} × [l 2 ] × • • • × [l d ].
Then there exists a T -step move M taking place in F 1 ∪ F 2 satisfying the following properties: (4) If M 1 is compatible with a permutation σ than M is also compatible with σ. Moreover, if M 1 is deterministically compatible with σ than M will also be deterministically compatible with σ.

By isometry this could also be dened for all other orientations. In the following we will refer to this move as the application of M 1 on the face

x 0 + {2} × [l 2 ] × • • • × [l d ] with the help of the face x 0 + {1} × [l 2 ] × • • • × [l d ].
From now on, in order to simplify notation, we only consider l Fr (l 1 , . . . , l d ).

1 = • • • = l d = l.
In some cases we will need to frame boxes will smaller loss of information. In the following we will refer to this move as the information saving framing move of the box

x 0 + [l] d in the directions ζ 1 e 1 , . . . , ζ d e d . We denote T by T k,d
Fr (l 1 , . . . , l d ). By isometry this could also be dened for boxes framed in all other directions. In the following we will refer to this move as the permutation move that applies σ to x 0 + {2, . . . , l} d . We denote

T by T k,d
Per . Moreover, the move is deterministically compatible with the permutation that sends

x 0 + x to x 0 + R e,e x
In the following we will refer to this move as the (k, d) framed reection move of x 0 + [l] d in the directions e, e . We denote T by T k,d fRef .

Proposition 5.2.37. Fix x 0 ∈ Λ and e, e ∈ {±e 1 , . . . , ±e d }. Then there exists a T -step move M taking place in x 0 + [l] d satisfying the following properties:

(1) For k = 1 and k = 2 the time T is bounded by a polynomial in l, and for k ≥ 3 That is, the move is compatible with the permutation that sends x 0 + x to x 0 + R e,e x

T ≤ 2 l d × polynomial in l, (2) DomM = η | x 0 + [l] d is (k, d) almost good and x 0 + {1} × [l] d-1 is (d -1, k) -framed , (3) Loss T M = 0, (4)
In the following we will refer to this move as the (k, d) reection move of x 0 + [l] d in the directions e, e . We denote T by T k,d

Ref .

x 0 + [l] α-1 × {-1} × [l] d-α are (k -1, d -1) frameable for η * ,
and the face Jmp .

x 0 + [l] α-1 × {0} × [l] d-α is (k, d -1) framed , (3)
For the construction of the next moves we will use the notion of geometric paths, which are the same as the paths of the previous sections but with some extra information.

in , e

out ∈ {±e 1 , . . . , ±e d }, such that i τ +1 -i τ ∈ {±e 1 , . . . , ±e d } for all τ < n. We will denote, at each step τ , e (τ ) in = i τ -i τ -1 and e (τ ) out = i τ -i τ +1 . We say that the geometric path is good if for a conguration η of the box B iτ is good for all τ , and super-good if it is good and the face li

1 + R e 1 ,e (1) in {1} × [l] d-1 is (k, d -1)
-frameable for all congurations that dier from η at at most one site.

We will also need to keep track of the time a move spends at some xed box Definition 5.2.40. Consider a T -step move M and some set V ⊂ Z d . Then the time M spends in V for a conguration η is

T V M,η = {t ∈ [T ] : ∃x ∈ B j such that M t η (x) = M t+1 η (x)} . We denote T V M = ∪ η∈DomM T V M,η . When V = B i for some i ∈ Z d l we will use the notation T (i) M,η and
T (i) M .
Proposition 5.2.41. Fix a geometric path i 1 , . . . , i n with directions e

in , e

out , and For l 2 = 2, by Proposition 5.2.18, the box

x * ∈ [l] d-1 . Let x * e (1) in = li 1 + R e 1 ,e (1)
[2]×{1}×[l 3 ]ו • •×[l d ] is (k, d -
1) framed being framed does not depend on the order in which we take the directions, therefore [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF]

×[l 2 ]ו • •×[l d ] is (k, d)-framed also in the directions e 2 ,
(d -1, k -1) moves to [2] × {2} × [l 3 ] × • • • × [l d ]. We also know that [2] × {2} × [l 3 ] × • • • × [l d ] is (k -1, d -1) framed, so η is in the domain of the (k -1, d -1) frame exchange move that exchanges {1} × {2} × [l 3 ] × • • • × [l d ] and {2} × {2} × [l 3 ] × • • • × [l d ].
Proposition 5.2.32 thus allows us to exchange these two faces. In order to nish we need to

exchange {1} × {1} × [l 3 ] × • • • × [l d ] and {2} × {1} × [l 3 ] × • • • × [l d ]. This could be done using the (k, d -1) framed exchange move [2] × {1} × [l 3 ] × • • • × [l d ] is (k, d -1) framed, so η is indeed in its domain. If l 2 > 2, we start by exchanging the faces [2]×{1}×[l 3 ]ו • •×[l d ] and [2]×{2}×[l 3 ]ו • •×[l d ].
This could be done since these two faces are in the domain of the (k, d)-frame exchange move, with faces whose smallest side is 2. For this new conguration, will will rst consider the sites of [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF]

× {1} × [l 3 ] × • • • × [l d ],
and then the sites of [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF]

× {2, . . . , l 2 } × [l 3 ] × • • • × [l d ]. The face [2]×{2}×[l 3 ]ו • •×[l d ] is now (k, d -1
) framed, so we will use Proposition 5.2.32 in order to apply (d -1, k -1) moves to [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF]

×{1}×[l 3 ]ו • •×[l d ]. The face [2]×{1}×[l 3 ]ו • •×[l d ] is (k -1, d -1)-framed in the directions e 1 , e 3 , . . . , e d . That is, {1} × {1} × [l 3 ] × • • • × [l d ] is (k -1, d -2)-framed and {2} × {1} × [l 3 ] × • • • × [l d ] is (k -2, d -
2)-framed. This allows us to exchange these two faces using the (k -1, d -2) framed exchange move.

The box [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF]

× {2, . . . , l 2 } × [l 3 ] × • • • × [l d ] is (k, d)
-framed in the directions e 1 , . . . , e d , so we apply (by induction) the (k, d) framed exchange move on it with a smaller value of l 2 .

Finally, we exchange back the two faces [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF]

×{1}×[l 3 ]ו • •×[l d ] and [2]×{2}×[l 3 ]ו • •×[l d ],
and this conclude the construction of the move. See gure 5.2.4.

5.2.4.2.

The frame sliding move (Proposition 5.2.31). Assume WLOG x 0 = 0, and set x = (x 1 , . . . , x d ). Use the framed exchange move x 1 times in order to move the face {1}×

[l 2 ]ו • •×[l d ] to {x 1 } × [l 2 ] × • • • × [l d ]. Consider now the box {x 1 , . . . , l 1 } × [l 2 ] × • • • × [l d ].
It is framed in the directions e 1 , . . . , e d , so we can apply the sliding move by induction into the point x. Similarly, the box domain is {η : x is empty}, deterministically compatible with a permutation σ that satises σx = x 0 + (1, . . . , 1). Since the dynamics is not constrained, we can construct such a move with T = dl. We then use the choice function dened for η ∈ DomM , that assigns to η the move M

[x 1 ] × [l 2 ] × • • • × [l d ]
x , for x ∈ x 0 + [l 1 ] × • • • × [l d ]
that is empty for η (when ambiguous we take the minimal one in some arbitrary order). This function is well dened since η ∈ DomM means (for k = 1) that at least one of the sites in x 0 + [l] d is empty. We can then dene M as in Denition 5.2.28, and Observation 5.2.29 completes the proof for this case.

For k > 1, by denition of frameability there exists a move that frames the box. The bounds on the time and on the loss come from the fact that there are at most Note that for η ∈ DomM the box x 0 is frameable, so it suces to consider k = 2.

The face {1}×[l] d-1 is framed, therefore by Proposition 5.2.32 we can apply (d -1, 1) moves to {2} × [l] d-1 . This face is (d -1, 1)-frameable, so we may apply the framing move in order to frame it. Then we use the framed exchange move and exchange {1} × [l] d-1 with {2} × [l] d-1 . In the same way we frame {3} × [l] d-1 and exchange it with {2} × [l] d-1 , until framing {l} × [l] d-1 . We can then exchange back {l -1} × [l] d-1 with {l -2} × [l] d-1 and so on until it is back to {1} ×[l] d-1 . By Observation 5.2.27 and the fact that (d -1, 1) framing has loss d log l the result follows.

5.2.4.6. The permutation move (Proposition 5.2.35). Assume rst that σ is a transposition that exchanges two neighboring sites, without loss of generality x = (x 1 , . . . , x d ) and y = x + e d . If k = 1 we can simply exchange the two sites. Consider now k ≥ 2. We know that x is not on the frame of [l] d , so at least k of its coordinates are dierent than 1. We can assume that one of these coordinates is the rst one, i.e., x 1 > 1. We will then slide the frame of [l] d to the point (x 1 -1, 1, . . . , 1), without changing the sites of [x 1 , l] × [l] d . After this move, the face {x Finally, we note that every transposition can be written as a product of at most 2dl nearestneighbor transposition, and every permutation can be written as the sum of at most l d log l d permutations. This concludes the proof. See gure 5.2.7. 5.2.4.7. The framed reection move (Proposition 5.2.36). Assume without loss of generality x 0 = 0. First, slide the frame into the point R e,e (1, . . . , 1). The frame of the resulting conguration is indeed the reected frame, and for the other site we can use Proposition 5.2.35. 5.2.4.8. The reection move (Proposition 5.2.37). In order to reect a box, we start by framing it in the direction e 1 , . . . , e d . We then apply a framed reection, and nally unwrap the framing move that we have applied in the beginning. All that is left is to wind back the framing moves and we are done. See gure 5.2.8. 5.2.4.10. Propagating a site along a path (Proposition 5.2.41). We construct this move by induction over n. For n = 1 the reection move of the box B i 1 in the directions e in , e out will give the result. For n > 1, propagate the site along the rst n -1 boxes. We can then apply the jump move swapping x * 5.2.4.12. Flipping a site. The rst step is to frame the boxes of Q i \ {i + e 1 }. By creating O l k-1 zeros on the boundary, we can make the box i 1 frameable. Then we apply Proposition 5.2.41 d -1 times (with arbitrary x * ), and framing Q i \ {i + e 1 } in the directions required by Proposition 5.2.41. We can do that since by adding sites of Q i to the path i 1 , . . . , i n we can obtain a super-good path that reaches each of the boxes boxes in Q i . We then use the boundary condition and set the site li 1 + R e 1 ,e (1) in (2, x * 2 , . . . , x * d ) to have the occupation value 1 -η (li + x * ). Then propagate the site along the path using Proposition 5.2.41 and swap it with li + x * using Proposition 5.2. [START_REF] Martinelli | Kinetically constrained spin models on trees[END_REF]. We now roll back everything, and the proof is nished. 5.2.5. From the long range Poincaré inequality to the Kob-Andersen dynamics.

1 -1} × [l] d-1 is (k, d -1) framed, so we may apply (k -1, d -1) moves to the face {x 1 } × [l] d-1 . Note that {x 1 } × [l] d-1 is (k -1, d -1)
In this section we bound from above the Dirichlet form with the long range constraints appearing in the r.h.s. of (5.2.5) with that of the KA model in Λ (5.2.2). Given i ∈ Λ l our aim is to bound the quantity µ(ĉ i Var B i (f ) appearing in the r.h.s. of (5.2.5) using the T -step moves that have been constructed in the previous section. In order to do that, it is convenient to rst condition on the environment of the coarse-grained variables {1 {B j is good} }j∈Λ l j =i . The main advantage of the above conditioning is that the good family for the vertex i+ e 1 , whose existence is guaranteed by the long range constraint ĉi , become deterministic. We will thus work rst in a xed realization of the coarse-grained variables satisfying ĉi = 1 and only at the end we will take an average and we will sum over i. The main technical step of the above program is as follows.

Given i ∈ Λ l let γ be an up-right focused path γ of length 2N starting at i + e 1 and let G i,γ be the event that γ is good and all j ∈ Q i ∩ Λ l are good. Let also V i,γ := B i ∪ j∈γ∪Q i B j and let F i be the σ-algebra generated by the random variables {1 {B j is good} }j∈Λ l j =i . Notice that G i,γ is measurable w.r.t. F i . Finally write

D i,γ (f | F i ) := x,y∈V i,γ ∩Λ x-y 1 =1 µ c xy ∇ xy f 2 | F i + x∈V i,γ ∩∂Λ µ Var x (f ) | F i .
Clearly the average w.r.t. µ of D i,γ (f | F i ) represents the contribution coming from the set V i,γ ∩ Λ to the total Dirichlet form D(f ). . Hence, on the event G i,γ ,

Var x (f ) = pq f (η) -f (η x ) 2 ≤ T -1 t=0 f (M t η) -f (M t+1 η) 2 ≤ T T -1 t=0 f (M t η) -f (M t+1 η) 2 .
(5.2.7)

In order to proceed it is convenient to introduce the following notation.

A pair of congurations e = (η, η ) ∈ E 2 is called a KA-edge if η = η and η is obtained from η by applying to η either a legal exchange at some bond b e of Λ or a spin ip at some site z e ∈ ∂Λ. If b e or z e belong to a given V ⊂ Λ we say that the edge e occurs in V . Given a KA-edge e = (η, η ) we write ∇ e f := f (η ) -f (η). Finally the collection of all KA-edges in E 2 is denoted E KA .

By construction, if M t+1 η = M t η then e t := (M t η, M t+1 η) is a KA-edge and the r.h.s. of (5.2.7) can be written as (1) For any KA-edge e and any η such that e = (M t η, M t+1 η) for some t ≤ T it holds that (for q < 1/2) µ(η) ≤ q -E(M ) µ(M t η).

(2) Since the T -move M takes place in the set V i,γ ∩ Λ, in the r.h.s. of (5.2.8) we can replace e∈E KA by e∈E KA e occurs in V i,γ ∩ Λ .

(3) Given a KA-edge e occurring in some B j ⊂ V i,γ ∩ Λ, This expression, by Proposition 5.2.14, satises the required bound.

We are now ready to state the main result of this section. For simplicity in the sequel we shall write C(l, q) for any positive function such that C(l, q) = e O(l d-1 (| log(q)|+log(l))) , as l ↑ +∞, q ↓ 0. Corollary 5.2.46. Fix 2 ≤ k ≤ d together with q ∈ (0, 1). Assume that it is possible to choose the mesoscopic scale l depending only on k, d, q in such a way that π l (d, k) ≥ π * , where π * is the constant appearing in Proposition 5.2.11. Then Var(f ) ≤ O(N 2 )C(l, q)D(f ).

Equivalently

T rel (q, L) ≤ O(L 2 )C(l, q). Proof of Proposition 5.2.46. Recall denition (5.2.4) of the long range constraints ĉi and let us consider one term µ ĉi Var B i (f ) appearing in the denition of D l (f ). Observe that ĉi is measurable w.r.t. the σ-algebra F i . Conditionally on F i and assuming that ĉi = 1, let G be a family of good paths for the vertex i + e 1 + e 2 ∈ Z d l . Clearly ĉi = 1 implies that G i,γ occurs y 0 + a (n + n 0 ) -1 α-1 ≤ x n ≤ y 0 + an -1 α-1 , where a = (α -1) (1 -δ) -α c -1

α-1 , a = [(α -1) c] -1 α-1 , and n 0 = (x 0 -y 0 ) 1-α (α-1)(1-δ) -α c are all positive constants.

Proof. Let us rst dene a sequence t n = (x n -y 0 ) 1-α , and note that t n is positive for all n. Then using Claim A1 and Assumption A1, xing c = (α -1) (1 -δ) -α c and c = (ν -1) c: t n = (f (x n-1 ) -y 0 ) 1-α t n = (f (x n-1 ) -y 0 ) 1-α ≤ (x n-1 -c (x n-1 -y 0 ) α -y 0 )

1-α ≥ (x n-1 -c (x n-1 -y 0 ) α -y 0 ) 1-α = t 1 1-α n-1 -ct α 1-α n-1 1-α = t 1 1-α n-1 -ct α 1-α n-1 = t n-1 1 -ct -1 n-1 1-α = t n-1 1 -ct -1 n-1 1-α ≤ t n-1 1 + c t -1 n-1 ≥ t n-1 1 + c t -1 n-1 = t n-1 + c ; = t n-1 + c .
We have used here the fact that, for any 0 < z < δ < 1, we can approximate (1 -z) 1-α using its derivative at 0 and at δ:

-(1 -α) ≤ (1 -z) 1-α -1 z ≤ -(1 -α) (1 -δ) -α .
We then also use ct -1 n-1 = (x n -y 0 ) α-1 < δ α-1 ≤ δ.

Finally,

x n = y 0 + t

-1 α-1 n
x n ≥ y 0 + (x 0 -y 0 ) 1-α + c n ≤ y 0 + an -1 α-1 ; = y 0 + a (n + n 0 ) -1 α-1 .

Next, we will be interested in the behavior near the bifurcation point, just before the new xed point appears. For this purpose we will consider a family {x ε n } ∞ n=0 of sequences, each dened by the value x ε 0 and the recursion formula for n > 0: Proof. We will rst consider the case in which the integral passes through 0, that is 0 < w 0 < cw 2α 0 + ε. In this case,

x ε n = f ε (x n-1 ) , (
w 0 ≤ w 0 1 -cw 2α-1 0 1 -δ 2α-1 -1 ≤ C 1 ε, cw 2α 0 + ε ≤ 1 + C 2 ε 2α-1 ε, for C 1 = (1 -cδ 2α-1 ) -1
and C 2 = c (1 -cδ 2α-1 ) -2α .

We may then bound the nominator of the integrand for all w ∈ [w 0 -cw 2α 0 -ε, w 0 ] by

cw 2α 0 + ε -cw 2α -ε ≤ cw 2α 0 + cw 2α ≤ C 3 ε 2α , where C 3 = 1 + C 2 ε 2α-1 0 2α + C 2α 1 .
For the denominator, cw 2α + ε cw 2α 0 + ε ≥ ε 2 .

Putting both estimations together

|I| ≤

w 0 w 0 -cw 2α 0 -ε

cw 2α 0 + ε -cw 2α -ε (cw 2α + ε) (cw 2α 0 + ε) ≤ cw 2α 0 + ε C 3 ε 2α-2 ≤ C 4 ε 2α-1 for C 4 = 1 + C 2 ε 2α-1 0 C 3 .
Next, we consider the case in which the integral is over a positive interval, i.e., w 0 ≥ cw 2α 0 +ε. We can bound the integrand using convexity for all w ∈ (w 0 -cw 2α 0 -ε, w 0 )

1 cw 2α +ε -1 cw 2α 0 +ε w -w 0 ≥ - 2αcw 2α-1 (cw 2α + ε) 2 .
This implies that I ≤ cw 2α 0 + ε 2αcw 2α-1 (cw 2α + ε) 2 (w 0 -w)

≤ 2αcw 2α-1 ≤ 2αcδ 2α-1 .
We are left with the case w 0 ≤ -cw 2α 0 -ε, which could be analyzed using the exact same argument as the previous one to obtain the result.

Using this claim we can continue the estimation:

τ n ≤ τ n-1 + 1 + κ c,δ,ε 0 , which proves the upper bound. The lower bound could be found by the exact same calculation, replacing τ with τ and c with c. The result follows since c ≤ c, thus τ n ≤ τ n by monotonicity of the integral.

We are now ready to formulate the nal result: du cu 2α +1 , and κ δ,0 = max (κ c,δ,0 , κ c,δ,0 ) for κ given in Lemma A5. Assume further that κ δ,0 < 1. Then:

0 < 1 2 I (1 + κ δ,0 ) ≤ lim inf ε→0 N δ (ε) ε -1+ 1 2α ≤ lim sup ε→0 N δ (ε) ε -1+ 1 2α ≤ I (1 -κ δ,0 ) < ∞.
The factor of 1 2 in front of I could be removed when ε -1 2α (x ε 0 -y 0 ) → ∞ as ε → 0 (e.g., when x ε 0 -y 0 is positive uniformly in ε).

Proof. This theorem is a direct consequence of the fact that ζ shows an ε -1+ 1 2ν time scaling behavior. First, note that τ N δ (ε)-1 ≤ t(-δ) ≤ t(-δ) ≤ τ N δ (ε) .

We will then be interested in nding t(-δ), t(-δ):

t(-δ) = -δ z ε 0 dz -cz 2α -ε = ε -1+ 1 2α -δ z ε 0 ε -1 2α dz -c zε -1 2α 2α -1 = ε -1+ 1 2α ε -1 2α δ -ε -1 2α z ε 0 du cu 2α + 1 ,
where for t one should take c = c, and c = c for c.

All that is left is to use Lemma A5, nding t(-δ)

(1 + κ δ,ε ) ≤ N δ (ε) ≤ 1 + t(-δ) (1 -κ δ,ε )
, which, since the integrals dening I and I converge, concludes the proof.

Remark A8. When f ε satises not only Assumption A3, but also f ε (y) = y -c (y -y 0 ) 2α -ε + o (y -y 0 ) 2α + o (ε) ,

we can consider δ ε that goes to 0 with ε, e.g., 1

|log ε| , so that κ δ,0 will converge to 0 as well. In this case, we may choose c δ and c δ that converge to c, and thus Theorem A7 will give the limit of N δ (ε)

ε -1+ 1 2α
, rather than just bounds on its limsup and liminf. Such a direct application of the theorem, however, forces us to choose an initial condition x ε 0 that converges to y 0 as ε goes to 0. To overcome this issue, we can use the estimation above with a xed δ until x n reaches δ ε , which happens at n of order δε z 0 dz -cz 2α -ε ε -1+ 1 2α . Then restart the dynamics using the estimation with δ ε until reaching -δ ε , which takes an order ε -1+ 1 2α of steps, and then using again the estimation for our xed δ show that the number of steps required to reach -δ is much smaller than ε -1+ 1 2α . This would yield lim ε→0 N δ (ε)

ε -1+ 1 2ν = ∞ -∞ du cu 2ν + 1
.

1 .

 1 Glasses and the liquid-glass transition

( 3 η x+e 1 = 0 and η x+e 2

 312

1 x

 1 is present and has at least one empty present neighbor 0 otherwise (3.1.5) for the FA1f model (section 3.6), and c x (η) =    1 x is present and has at least two empty present neighbors 0 otherwise (3.1.6)

Theorem 3 . 2 . 1 .

 321 Consider the bootstrap percolation (see equation (1.3.1)) with constraints dened in equations (3.1.1) and (3.1.2) for d = 2.

  1 -e -s ) converges, so dening γ = -∞ 0 ds log (1 -e -s ) gives the result.

Figure 3 . 2 .

 32 Figure 3.2.1. Illustration of claims 3.2.8 and 3.2.9. 0 represents an empty site, otherwise the state is the initial one. e stands for an easy site.

Theorem 3 . 3 . 1 .

 331 Consider the KCM on Z 2 with the constraints dened in equations (3.1.1) and (3.1.

Figure 3 . 3 . 1 .Figure 3 . 3 . 2 .

 331332 Figure 3.3.1. Illustration of the proof of Lemma 3.3.8.We see here how to create an empty column and propagate it using the easy sites. 0 represents an empty site, otherwise the state is the initial one. e stands for an easy site.

  pairs of neighboring lines or d distinct pairs of neighboring columns with only dicult vertices. Being d-dicult depends only on the disorder ω, and not on η.

Claim 3 . 3 .

 33 11. If R is d-dicult and internally spanned, than it must contain at least d empty sites.

Observation 3 . 3 . 13 .

 3313 Under D L,d , all rectangles in [-L, L] 2 that contain the origin and at least one site on the boundary are d-dicult. Claim 3.3.14. There exist two positive constants c, C such that for all a satisfying cπ ≤

  3.3). Theorem 3.4.1. Consider the KCM on Z d with the constraints dened in equations (3.1.1) and (3.1.

3. 4 . 1 .

 41 Spectral gap (proof of part 1 of Theorem 3.4.1). Just like in the two dimensional case, the gap is bounded by that of the FAdf model on Z d , which by [43] yields the result. 3.4.2. Upper bound (proof of equation (3.4.1)). In order to prove equation (3.4.1) we

Observation 3 . 4 . 7 .

 347 If we take S = {0, 1} S 0 with the measure µ S 0 , and G = {S 0 is empty}, then L G given in Proposition 3.4.3 describes the same dynamics as L Sn on Lb

By Proposition 4 .

 4 4 of [19]: Claim 3.5.2.

Claim 3 . 6 . 13 .

 3613 Assume 0 ∈ G . Fix α ∈ R big enough, and let l c (V ) = α √ V , L(V ) = Ce γVfor C, γ small enough. Then almost surely G has an l c growth in the domain B 0 (L).

Claim 3 . 6 . 15 .

 3615 Fix β ∈ R, and let D(V ) = β √ V and L = Ce γD for γ small enough. Then ν-a.s. for all V ∈ N large enough max H∈C L(V ) diamH ≤ D(V ).

  dynamics described in equation (1.3.1).

Figure 4 .

 4 Figure 4.2.1. A schematic picture of φ ξ t as a function of t for a (ν 1 , . . . , ν n )metastable criticality at x 1 > • • • > x n .

4. 2 . 4 .

 24 Some remarks and open questions. The rst remark is about other possible discontinuities of φ. Consider, for example, r = 2 and ξ k = 3 5 1 k=2 + 2 5 1 k=5 . The function

Figure 4 .

 4 Figure 4.2.2. g ξ for r = 2 and ξ k = 3 5 1 k=2 + 2 5 1 k=5 . We show three lines 1

Observation 4 . 3 . 1 .

 431 Let L d be the generator of the dynamics on the d-ary tree (i.e., for ξ k = 1 k=d ). Then gapL 3 ≤ gapL ≤ gapL 4 .

3 L . 4 . 3 .0. 2 . 1 x

 34321 Proof of the lower bound. Fix l ∈ N, and consider the long range dynamics dened by c in empty for the bootstrap percolation after l + 1 steps 0 otherwise

( 4 . 3 . 1 )Claim 4 . 3 . 8 .

 431438 Let l = log 2 L+71. Then the (quenched) probability ν sup x∈G µ 1 -c

  Claim 4.3.11. Let G (l)

Remark 5 . 2 . 3 .

 523 For d = 2, k = 2 a box is (2, 2)-good if it contains at least two empty sites in every row and every column.

Figure 5 . 2 . 2 .

 522 Figure 5.2.2. Black dots are the vertices of V , gray dots are the vertices of V * , diamonds are the left and right boundary of V * .

Figure 5 . 2 . 3 .

 523 Figure 5.2.3. Incoming and outgoing degrees of vertices on the boundary of V * (left) and its interior (right)

Definition 5 . 2 . 15 .

 5215 Fix two directions e, e ∈ {±e 1 , . . . , ±e d }. Then the (e, e )-reection of a site x ∈[l 1 ] × • • • × [l d ] is the site R e,e x of [l 1 ] × • • • × [l d ] given byR e,e x = x -e, x e -e , x e + e, x e + e , x e mod (l 1 , . . . , l d ) for e = -e , and R e,e x = x -2 e, x e for e = -e . This is an isometry that sends the vector e to e . Definition 5.2.16. Fix l 1 , . . . , l d , and consider the boxB = [l 1 ] × • • • × [l d ]. Let η ∈ {0, 1} B . We dene the notion of (k, d)-framed in the directions e 1 , . . . , e d Case 1. For k = 1 we say that the box is (k, d)-framed if the site (1, . . . , 1) is empty. Case 2. For d = k -1 the box is (k, d)-framed when it is entirely empty. Case 3. For d ≥ k > 1 the box is framed when the rst face{1} × [l 2 ] × • • • × [l d ] is (k, d -1)-framed in the directions e 2 , . . . , e d , and each of the faces {m} × [l 2 ] × • • • × [l d ] , m = 2, . . . , d is (k -1, d -1)-framed in the directions e 2 , . . . , e d . Being framed in other directions (given by permutations of ± e 1 , . . . , ± e d ) is dened by isometry, that is, B is framed in the directions e 1 , . . . , e d for the conguration η if R e 1 e 1 . . . R e d e d B is framed in the direction e 1 , . . . , e d for the conguration η dened as η (x) = η (R e 1 ,ζe 1 x, . . . , R e d ,ζe d x) .

Example 5 . 2 . 17 .

 5217 For k = 2, d = 2 a box is framed if its bottom line and leftmost column are empty. For k = 2, d = 3 a box is framed if the three edges touching the box's corner are empty. For k = 3,d = 3 a box is framed if the three faces touching the corner are empty. The connection with the frameability dened in section 5.2.1 is given by the following characterization. Proposition 5.2.18. The box [l 1 ] × • • • × [l d ] is (k, d)-framed in the directions e 1 , . . . , e d for η ∈ {0, 1} [l] d i every k -1 dimensional face containing the corner (1, . . . , 1) is empty. That is, if x = (x 1 , . . . , x d ) satises

  The rst part describes equation(5.2.6) for the (d -1, k)-frameness of {1} × [l 2 ] × • • • × [l d ],and the second corresponds to the (d-1, k -1)-frameness of each of the faces {m} × [l 2 ] × • • • × [l d ] , m = 2, . . . , d. Corollary 5.2.19. Fix l 1 , . . . , l d and η ∈ Ω Λ . The box [l 1 ] × • • • × [l d ] is (d, k)-frameable for η if it is connected by legal FAkf moves in the box to a (k, d)-framed conguration.It will sometime be useful to use the convention that boxes are always (0, d)-frameable. Definition 5.2.20. Fix l 1 , . . . , l d , and consider the box [l 1 ] × • • • × [l d ]. We say that the box is (k, d)-almost good for the conguration η if all d -1 dimensional faces contained in it are (k -1, d -1)-frameable for η. The box is good for η if it is almost good for all congurations η that dier from η by at most one site. For k = 1 all boxes are good. Example 5.2.21. For k = 2,d = 2 a box is good if every column and every line contain at least two empty sites. For k = 2, d = 3 a box is good if each 2 dimensional section contains at least two empty sites. For k = 3, d = 3 a box is good if each 2 dimensional section contains at least two empty sites in each row and in each column, and at least two non-intersecting rows or columns are empty.

Proposition 5 . 2 . 33 .

 5233 Fix x 0 ∈ Λ and ζ 1 , . . . , ζ d ∈ {+, -}. Then there exists a T -step move M taking place in x 0 + [l] d satisfying the following properties: (1) For k = 1 the time T ≤ dl, and for k ≥ 2 it is bounded by T ≤ 2 l d , (2) DomM = η : the box x 0 + [l] d is (d, k) -frameable , (3) For k = 1 LossM ≤ d log l and for k ≥ 2 LossM ≤ l d . (4) In the nal state the box x 0 + [l] d is framed in the directions ζ 1 e 1 , . . . , ζ d e d . In the following we will refer to this move as the framing move of the box x 0 + [l] d in the directions ζ 1 e 1 , . . . , ζ d e d . We denote T by T k,d

Proposition 5 . 2 . 34 .

 5234 Fix x 0 ∈ Λ and ζ 1 , . . . , ζ d ∈ {+, -}. Then there exists a T -step move M taking place in x 0 + [l] d satisfying the following properties: (1) For k = 1 and k = 2 the time T is bounded by a polynomial in l, and for k ≥ 3 T ≤ 2 l d , (2) DomM = η | x 0 + {1} × [l] d-1 is (d -1, k) -framed and x 0 + [l] d is (d, k) almost good , (3) For k = 1 LossM ≤ d log l, for k = 2 LossM ≤ d 2 l log l, and for k ≥ 3 LossM ≤ l d , (4) In the nal state the box x 0 + [l] d is framed in the directions ζ 1 e 1 , . . . , ζ d e d .

Proposition 5 . 2 . 35 .

 5235 Fix x 0 ∈ Λ and a permutation σ of the sites in x 0 + [l] d . Assume that σ xes the frame dened as the set of sites satisfying 5.2.6. Then there exists a T -step move M taking place in x 0 + [l] d satisfying the following properties: (1) T is polynomial in l, (2) DomM = η | the box x 0 + [l] d is framed in the directions e 1 , . . . , e d , (3) LossM = 0, (4) The permutation σ is deterministically compatible with M .

Proposition 5 . 2 . 36 .

 5236 Fix x 0 ∈ Λ and e, e ∈ {±e 1 , . . . , ±e d }. Then there exists a T -step move M taking place in x 0 + [l] d satisfying the following properties: (1) T is polynomial in l, (2) DomM = η | the box x 0 + [l] d is framed in the directions e 1 , . . . , e d , (3) LossM = 0 (4) It the nal state the box x 0 + [l] d is reected according to e, e : M T η (x) = η (R e,e x) .

For k = 1

 1 LossM ≤ d log l, for k = 2 LossM ≤ d 2 l log l, and for k ≥ 3 LossM ≤ l d , (5) It the nal state the box x 0 + [l] d is reected according to e, e : M T η (x) = η (R e,e x) .

Proposition 5 . 2 . 38 .( 1 ) 4 T

 523814 Fix x 0 ∈ Λ, e ∈ {±e 1 , . . . , ±e d } andx * = x * 1 , . . . , x * d-1 ∈ [l] d-1 . Let α be such that e ∈ {±e α } and x * e = x 0 + x * 1 , . . . , x * α-1 , 0, x * α , . . . , x * d-1 . Then there exists a T -step move M taking place in x 0 +[l] α-1 ×{-1, 0, 1}×[l] d-α satisfying the following properties: For k = 2 and k = 3 the time T is bounded by a polynomial in l, and for k ≥ ≤ 2 l d × polynomial in l, (2) For a xed conguration η, let η * be the conguration that equals η for x / ∈ {x * e + e, x * e -e} and 1 for x ∈ {x * e + e, x * e -e}. With this notation, DomM = η | the face x 0 + [l] α-1 × {1} × [l] d-α and the face

For k = 2 ( 4 )

 24 LossM ≤ 2d log l, for k = 3 LossM ≤ 2d 2 l log l, and for k ≥ 4 LossM ≤ 2l d . It the nal state M T η (x) = e + e) x = x * e -e η (x * e -e) x = x * e + e η (x) otherwise ,i.e., M η is compatible with the permutation that exchanges x * e + e and x * e -e. In the following we will refer to this move as the jump move of the site x * e -e to x * e + e. We denote T by T k,d

in ( 2 ,Figure 5 . 2 . 5 .

 2525 Figure 5.2.5. The frame sliding move for k = d = 2

Figure 5 . 2 . 6 .Figure 5 . 2 . 7 .

 526527 Figure 5.2.6. The box framing move for k = d = 2

5 .

 5 Information saving framing. Assume WLOG that x 0 = 0 and ζ 1 = • • • = ζ d = +.

Figure 5 . 2 . 8 . 2 0Figure 5 . 2 . 9 .

 5282529 Figure 5.2.8. The jump move for k = d = 2

5. 2 . 4 . 9 .

 249 The jump move (Proposition 5.2.38). Start by framing the face x 0 + [l] α-1 × {0} × [l] d-α . Then, by Proposition 5.2.32 we can also frame the facesx 0 + [l] α-1 × {±1} × [l] d-αfor η * . When framing these faces, x * e -e 1 and x * e + e 1 could change position, so we denote by y -e 1 and y + e 1 their new positions. We can now exchangex 0 + [l] α-1 × {0} × [l] d-α and x 0 + [l] α-1 × {-1} × [l] d-α using the framed exchange, permute x e with y + e 1 with the permutation move, and exchange again x0 + [l] α-1 × {0} × [l] d-α and x 0 + [l] α-1 × {-1} × [l] d-α .

.

  This gives the required move. See gure 5.2.9. 5.2.4.11. The swap move (Proposition 5.2.42). Note that for η ∈ DomM the box i + [l + 1] d is framed in the directions -e 1 , . . . , -e d . We can thus apply the permutation move in order to move the site li + x * to li + (l, x * 2 , . . . , x * d ). Then the jump move allows us to swap li + (l, x * 2 , . . . , x * d ) with li + (l + 2, x * 2 , . . . , x * d ) = l (i + e 1 ) + (2, x * 2 , . . . , x * d ), and then applying the inverse permutation nishes the construction.

Lemma 5 . 2 . 44 .

 5244 On the event G i,γ µ Var B i (f ) | F i ≤ O(N )e O(l d-1 (| log(q)|+log(l))) D i,γ (f | F i ) ∀f : E Λ → R.for k = 2, andµ Var B i (f ) | F i ≤ O(N )e O(l d (| log(q)|+log(l))) D i,γ (f | F i ) ∀f : E Λ → R.when k ≥ 2.

Proof. Assume 1 µµ

 1 G i,γ = 1. Since the marginal of µ(• | F i ) on {0, 1} B i is a product measure we have immediately thatµ Var B i (f ) | F i ≤ x∈B i Var x (f ) | F i ,and it is sucient to prove that maxx∈B i Var x (f ) | F i ≤ O(N )e O(l d-1 (| log(q)|+log(l))) D i,γ (f | F i )for k = 2, and with l d in the exponent for k > 2. Given x ∈ B i , Proposition 5.2.14 and the assumption 1 G i,γ = 1 imply that there exists a T -step move M with Dom(M) = G i,γ , taking place in V i,γ ∩ Λ and such that for all η ∈ Dom(M) M T η is the conguration η ipped at x. Notice that M does not change the variables {1 {B j is good} }j∈Λ l j =i

T T - 1 t=0 c et ∇ et f 2 ,µ c e ∇ e f 2 1 ( 5 . 2 . 8 )

 121528 where c et is the kinetic constraint associated to the KA-edge e t . Taking the expectation over ηw.r.t. µ(• | F i ) yields µ Var x (f ) | F i ≤ T e∈E KA T t=0 {e=(Mtη,M t+1 η)} | F i .Next we use the following chain of observations (recall Proposition 5.2.14 and the relevant denitions therein).

1

  {e=(Mtη,M t+1 η)} ≤ 2 Loss(M) |T (j) M |.Using the above remarks, on the event G i,γ ,µ Var x (f ) | F i ≤ T 2 Loss(M) |T (j) M |q E(M) e=(η,η )∈E KA e occurs in V i,γ ∩ Λ µ(η | F i )c e (η) ∇ e f 2 .

( 5 . 2 . 9 ) for k = 2 ,

 5292 and with l d in the exponent for k ≥ 2. Of course the constant in the O(•) notation may change from line to line. Proposition 5.2.45. Let D l (f ) = µ i∈Λ l ĉi Var B i (f ) and let D(f ) be the Dirichlet form of the KA model. Then D l (f ) ≤ O(N 2 )C(l, q)D(f ).

  Proof of the Corollary. The rst part of the corollary follows at once from Propositions 5.2.11 and 5.2.45. The second part is an immediate consequence of the rst one and of the variational characterization of the relaxation time (see the beginning of Section 5.2).

- 1 α- 1 ≤ 1 α- 1 =

 1111 y 0 + (x 0 -y 0 ) 1-α + c n y 0 + c n + (x 0 -y 0 )

  There is a point y 0 such that for |y -y 0 | < δ and ε < ε 0 y -c (y -y 0 ) 2α -ε ≤ f ε (y) ≤ y -c (y -y 0 ) 2α -ε,for an integer α > 1 and positive constants c, c. Assumption A4. 0 < x 0 -y 0 < δ.Claim A6. Fix w 0 ∈ (-δ, δ), and c > 0. c,δ,ε 0 .

Theorem A7 .

 A7 Fix the family of sequences (indexed by ε) dened in equation (A2) satisfying assumptions A3 and A4. Consider the exit times N δ (ε) (see Denition A3). Let I =

  .3.2) Definition 2.3.1. Let E, A ⊆ Ω be two events. The time spent in E before hitting A is

  1. Illustration of claims 3.2.8 and 3.2.9. 0 represents an empty site, otherwise the state is the initial one. e stands for an easy site.

	The next two claims will show how a cluster of empty sites could propagate. See gure 3.2.1.
	Claim 3.2.8. Assume that [L] 2 is excellent, and that (1, 1) is initially empty. Then [L] 2 will
	be entirely emptied by time L 2 .

  1 , with empty boundary on Lb i + {n} × [L] d-1 and occupied elsewhere.

  4.2.2. Proof of Theorem 4.2.5. We start with a couple of small results. Claim 4.2.8. g k is a polynomial of degree k -1, whose lowest degree monomial is of degree k -r.

	Proof. By equations 4.2.6 and 4.2.2

  Definition 5.2.39. A geometric path of length n is a sequence i 1 , . . . , i n ∈ Z d

	l	n	, together
	with two directions e

  e 1 , e 3 , . . . , e d . We can thus use Proposition 5.2.32 in order to apply

RANDOM CONSTRAINTS ON Z d

MODELS ON THE GALTON-WATSON TREE

Remerciements

Proof. We start with a denition. Definition 4.3.4. Fix l ∈ N and a vertex x ∈ G. The subtree of G rooted at x of depth l is called bad if each vertex has only 3 children.

The spectral gap of L (3) is 0, so we can nd a local function f on the trinary tree such that D (3) f Varf is as small as we want. G will contain bad subtrees of all depth, so in particular we can dene f on G such that it is supported on a bad subtree. This shows that the spectral gap is 0.

We have thus identied two critical probabilities q c in which the model becomes ergodic, and q

(3) c in which a gap is opened. For q ∈ q c , q

(3) c the dynamics is ergodic, but with innite relaxation time.

More rened estimation could be made by considering only the rst L levels of the tree. We call this tree G L , and denote by L L the generator of the dynamics on G L with free boundary conditions. For concreteness we will take q = 0.1, which is between q c and q

(3) c . Theorem 4.3.5. Consider L L dened above and q = 0.1. With probability tending to 1 as L tends to ∞, L -15 ≤ gap (L L ) ≤ L -0.09 .

Before proving this theorem, note that a more interesting result would be if the spectral gap scaled like L -α for some α < 1 by a nite speed of propagation argument (like in the proof of Theorem 3.6.1) we would obtain a stretched exponential decay of correlation, i.e., for local f with mean 0 E µ [f (η (0)) f (η (t))] ≤ C f e -t 1-α .

By optimizing the proof, some improvement on the exponent 15 for the lower bound and 0.09

for the upper bound could be achieved; but the method we use does not enable us to nd a lower bound that scales with an exponent smaller than 1, nor an upper bound that will exclude this possibility.

4.3.0.1. Proof of the upper bound. In order to show that the spectral gap is small, we need to nd an appropriate test function. Fix L, and take l such that L ≥ 3 l + l. Proof. For a x vertex, the probability to be the root of a bad subtree of depth l is 1 2 3 l .

The number of vertices at level L -l is at least 3 L-l . Therefore, the probability that none of them is the root of a bad subtree is 1 -

Assume now that T 3 is a bad subtree of G with depth l, rooted at r 3 . Let f be the indicator of the function, that r 3 is in the span of T 3 . First, for l big enough φ

(3) l approaches its limit, which by Fact 4.2.2 and our choice of q is equal 5

6

. In particular

where l n = 10 n . We shall prove that the existence of a good family of paths is guaranteed by the simultaneous occurrence of certain events A, B and {C n } n * n=1 , where n * = min{n : Definition.

(1) Let R i be the rectangle in Z d l whose short sides are D i and D i + 2N ( e 1 + e 2 ). Then A is the event that there are at least 1.9 √ N edge-disjoint good up-right paths contained in R i and connecting D i with D i + 2N ( e 1 + e 2 ).

(2) B is the event that the set ∪ t∈[0,

) by a good up-right path, (3) C n is the event that i is good and there exists a good up-right hard-crossing of both V (n) and H (n) , i.e. a good up-right path connecting the two short sides of V n (H n ) and which is contained in V n (H n ).

Lemma 5.2.7. Assume that A ∩ B ∩ C n occurs for all n ∈ [n * ]. Then there exists a good family of paths for i.

Proof. We show rst that i is connected by a good up-right path to the set D i ∩ H n * and to the set D i ∩ V n * . Let n 1 = 1, and dene recursively n k+1 , k ∈ [n -1] as the largest integer n such that there exists a crossing of H (n∧n * ) starting from the set {i + t e 2 , t ∈ [0, l n k ]}.

By assumption, the sequence {n k } n k=1 is strictly increasing as long as n k ≤ n * . Then, starting

Observe that i = ( e 1 -e 2 , i)

We will consider the erased edges, namely {(j, j ) : j is bad and j ∈ {j + e 1 , j + e 2 }} .

Assume now that the value of the cut is less than 1.9

√ N , from the previous observations it follows that γ * must cross at least U + L -1.9 µ(value of any cut is ≥ 1.9

The proof of the proposition is complete.

and there exists a good family of paths for i + e 1 , 0 otherwise (5.2.4) In this section we shall prove the following result. Recall that π

Proposition 5.2.11. There exists π * < 1 such that for any π l ≥ π * and any local function

(5.2.5)

Proof. We will closely follow the proof of [START_REF] Martinelli | Towards a universality picture for the relaxation to equilibrium of kinetically constrained models[END_REF]Theorem 2.6]. Let ci be the indicator of the event A ∩ B ∩ n * n=1 C n (see Denition 5.2.2), together with the requirement that Q i is good. By Lemma 5.2.7 ci ≤ ĉi for all i ∈ Z d l . Hence, in order to prove (5.2.5), it is enough to prove the stronger constrained Poincaré inequality in which in the r.h.s. of (5.2.5) the constraint ĉi is replaced by ci . Using Proposition 5.2.8 together with the obvious bound µ

to the directions e 2 , . . . , e d ), (3) LossM = 0, (4) In the nal state the two faces F 1 and F 2 are exchanged for all η ∈ DomM

Moreover, M is deterministically compatible with the permutation that exchanges F 1 and F 2 .

By isometry this could also be dened for all other orientations. In the following we will refer to this move as the (k, d) framed exchange move of the faces F 1 and F 2 . We denote T by

Then there exists a T k,d -step move M taking place in B satisfying the following properties:

(

LossM = 0, (4) M is deterministically compatible with a permutation σ that satises the following properties: (a) σ sends the lower dimensional faces containing the site (1, . . . , 1) to the faces containing the site x. More precisely, x y = x 0 + (y 1 , . . . , y d ), and let y =

x -(1, . . . , 1) + (y 1 , . . . , y d ). Then y α = 1 implies y α = 1 for all α = 1, . . . , d. In particular, in the nal state all k -1 dimensional face containing the site x are empty. (b) σ xes the sites in x 0 + x + N d , i.e., the sites that are strictly greater than x 0 + x coordinate by coordinate.

By isometry this could also be dened for all other orientations. In the following we will refer to this move as the (k, d) sliding move of the frame of B into x. We denote T by T k,d Sld (l 1 , . . . , l d ).

Proposition 5.2.32. Fix x 0 ∈ Λ, and let M 1 be a T 1 -step move taking place in

for the KAkf dynamics satisfying the following properties:

(1) (1) T = polynom in l,

(2) For every box j ∈ Q i , we write j = α∈d c α e α for c α ∈ {0, 1}.

M is deterministically compatible with the permutation that swaps the sites li + x * and

In the following we will refer to this move as the swap move of li + x * and l (i + e 1 ) + (2, x * 2 , . . . , x * d ).

We are nally ready to show how to ip a single site.

Proposition 5.2.43. Fix a geometric path i 1 , . . . , i n , i n+1 with directions e

in , e

out such that i 1 -e is bounded by 2T n , uniformly for all j ∈ Z d l , (6) M T η = η li+x * , i.e., the site li + x * is ipped.

The move given in this proposition is the one we take for Proposition 5.2.14.

We can now construct these moves. 5.2.4.1. The framed exchange move (Proposition 5.2.30). Assume WLOG x 0 = 0, l 2 ≤ • • • ≤ l d , and take η ∈ DomM . Note that the denition of DomM is equivalent to the requirement that the box [START_REF] Aizenman | Metastability eects in bootstrap percolation[END_REF]

For k = 1, the KA-1f dynamics is the unconstrained one, so we may simply exchange the two frames site by site.

for each path γ ∈ G. Hence, by applying Lemma 5.2.44 to each path in G we get

(5.2.10)

For a given bond (x, y) ⊂ Λ (respectively x ∈ ∂Λ) let j = j(x) be such that B j x and let Π j denote the ( e 1 , e 2 )-plane in Z d l containing j. Since all the paths forming the family G belong to the plane Π i , and are focused we immediately get that

where R i is the set of points at distance at most √ N from the set {k : k = i+s( e 1 + e 2 ), s ∈ N}.

Next, for (x, y) ⊂ Λ (respectively x ∈ ∂Λ) In conclusion, the rst and second term inside the square bracket in the r.h.s. of (5.2.10) are bounded from above by

x,y∈Λ

respectively. Clearly the same bounds hold for their average w.r.t. µ.

In order to conclude the proof it is enough to sum over i the above expressions and use the fact that, uniformly in x ∈ Λ, i∈Λ l

5.2.6. Completing the proof of Theorem 5.1.1. Using Corollary 5.2.46, the proof of Theorem 5.1.1 is complete if we can prove that for all π * < 1, for any given q ∈ (0, 1) and 2 ≤ k ≤ d it is possible to choose l = l(q, k, d) in such a way that (i) the probability that any given i ∈ Z d l is (d, k)-good satises π l (d, k) ≥ π * ;

THE KOB-ANDERSEN MODEL ON Z d

(ii) C(l, q) ≤ C(q) as q → 0, where C(q) is as in (5.1.3) and C(l, q) satises (5.2.9).

Let us start by stating a key result on the probability of the set of frameable congurations.

Proposition 5.2.47 (Probability of frameable congurations [START_REF] Toninelli | Cooperative behavior of kinetically constrained lattice gas models of glassy dynamics[END_REF]). Fix q and let F q (l, d, j) be the probability that the cube C l = [l] d is (d, j)-frameable. Then there exists C > 0 s.t. for

Proof. The case j = 1 follows immediately from the denition of frameable congurations (see Denition 5.2.1). The cases j ∈ [2, d] are proven in Section 2 of [START_REF] Toninelli | Cooperative behavior of kinetically constrained lattice gas models of glassy dynamics[END_REF], see formula (34) 2 and (36), where the results are stated in terms of the parameter s = j -1. Actually, the denition of frameable in [START_REF] Toninelli | Cooperative behavior of kinetically constrained lattice gas models of glassy dynamics[END_REF] is more restrictive than our Denition 5.2.1. Indeed in [START_REF] Toninelli | Cooperative behavior of kinetically constrained lattice gas models of glassy dynamics[END_REF] the frame that should be emptiable is composed by all the faces of dimension j -1 containing one corner of C l (and not only those that contain the vertex (1, . . . , 1)). However, since we only need a lower bound on the probability of being frameable we can directly use the results of [START_REF] Toninelli | Cooperative behavior of kinetically constrained lattice gas models of glassy dynamics[END_REF].

Then, by using Proposition 5.2.47 and the Denition 5.2.2, we get that there exists c > 0

which goes to 1 as q → 0, and thus implies that condition (i) is satised for all q ∈ (0, 1) (since π l (d, k) is non decreasing with q) . Finally, it is immediate to verify that the above choice of l satises also condition (ii) for all k ∈ [2, d].

2

There is a misprint in formula [START_REF] Holroyd | Sharp metastability threshold for two-dimensional bootstrap percolation[END_REF] of [START_REF] Toninelli | Cooperative behavior of kinetically constrained lattice gas models of glassy dynamics[END_REF]: in the exponential a minus sign is missing • Can we extend these results to general random mixtures of constraints, each given by a general update family (see [START_REF] Marêché | Exact asymptotics for Duarte and supercritical rooted kinetically constrained models[END_REF][START_REF] Martinelli | Universality results for kinetically constrained spin models in two dimensions[END_REF])?

• How do these time scales behave on other random graphs, such as the random regular graph, conguration model, or the Poisson Voronoi tessellation?

• What can we say about models with random external eld, i.e., rather than having a constant q the equilibrium at each site x is determined by a random q x ? • What can we say beyond the emptying time of a site? The question closer to the physical behavior of the system would, in fact, be the time for correlations to decay. Theorem 3.6.1 treats this problem, but the methods used in order to prove it do not apply to the other models studied here.

• Another type of question is when starting out of equilibrium, for example, with an independent product measure of parameter greater than q. How will hitting times behave in this case? And how long will the process take to mix?

• Can we say something about kinetically constraint lattice gas models (namely Kawasaki type) in random environments?

The Kob-Andersen model

• Can we nd a lower bound on the relaxation time, showing that the constant C(q) of Theorem 5.1.1 scales as in equation (5.1.3)?

• Improve the bound of [START_REF] Cancrini | Kinetically constrained lattice gases[END_REF] on the loss of correlation in this model. For the two dimensional case it is bounded there between 1/t and (log t) 5 /t, and we expect that the correct behavior is 1/t. In higher dimension the lower bound is 1/t d/2 , which is even further from the upper bound, and trying to match them will be an interesting problem.

• Hydrodynamic limit some results are known for KCLG models, but only in the non-cooperative case [START_REF] Goncalves | Hydrodynamic limit for a particle system with degenerate rates[END_REF]. Is it possible to establish a hydrodynamic limit for the Kob-Andersen model, and to which degenerate diusion equation does it correspond?

• Understanding the dynamics of a single tagged particle. The diusion constant is known to be positive, but the known bound decays extremely fast with q [START_REF] Blondel | Kinetically constrained lattice gases: tagged particle diusion[END_REF]. I APPENDIX A Dynamical systems near a bifurcation point Section 4.2 concerns with the analysis of a phase transition originating in the appearance of a new xed point for a certain recurrence relation, i.e., a bifurcation. In this appendix, we will try to understand in a more general context the time scaling in systems of that type. Let us then consider a sequence of reals {x n } ∞ n=0 , dened by the value x 0 and the a recursion formula for n > 0:

x n = f (x n-1 ) .

(A1)

We will also x now some positive δ < 1, that will be used throughout this appendix as the window around the new xed point in which we are interested.

First, we will study the time scaling at the bifurcation point, when the new xed point is rst created. In this case, we may expect f to be tangent to the identity function at the xed point, so we will start our discussion with the following assumptions: Assumption A1. f has a xed point y 0 , such that for y ∈ (y 0 , y 0 + δ) y -c (y -y 0 ) α ≤ f (y) ≤ y -c (y -y 0 ) α , for some α > 1, 0 < c ≤ c < δ -(α-1) .

Assumption A2. x 0 ∈ (y 0 , y 0 + δ).

We rst mention the following claim:

Claim A1. The sequence is decreasing and bounded from below by y 0 .

Proof. By Assumption A1, x n+1 < x n whenever x n ∈ (y 0 , y 0 + δ). Moreover:

Therefore, since x 0 ∈ (y 0 , y 0 + δ) by assumption A2, the entire sequence is in the interval (y 0 , y 0 + δ), and it is decreasing.

The following theorem will describe the asymptotic of the sequence: Theorem A2. Let {x n } be the sequence dened in equation (A1), satisfying assumptions A1 and A2. Then

A. DYNAMICAL SYSTEMS NEAR A BIFURCATION POINT

In order to study the asymptotic behavior of x ε n for small values of ε, we will need the following denition: Definition A3. The exit time N δ (ε) is the minimal n such that x ε n < y 0 -δ.

Replacing Claim A1 will be the following:

Claim A4. For all ε < ε 0 the exit time N δ (ε) is nite, and for n < N δ (ε) the sequence x ε n is decreasing.

Proof. By assumption A3, for n < N δ (ε), if x ε n < y 0 + δ then x ε n+1 < x ε n < y 0 + δ. Hence, the sequence remains in the interval (y 0 -δ, y 0 + δ) as long as n < N δ (ε). Since in this interval the sequence is decreasing, the results follows by Assumption A4.

For our analysis, we will compare this sequence to the solution of the following dierential equations, that will approximate x ε n -y 0 :

The solution ζ is strictly decreasing, and in particular one can dene its inverse t : [-∞, z ε 0 ] → [0, ∞], and τ n = t (x ε n -y 0 ). t and τ n will be dened in the same manner. Note that they depend on ε, even though this dependence is omitted from the notation. The next lemma shows that the continuous crossing times τ n and τ n are close to the discrete one, namely n. where for all c > 0, κ c,δ,ε = max (C 4 ε 2α-1 , 2αcδ 2α-1 ). C 4 is a positive constant depending on δ, c and ε 0 given explicitly in the proof, and bounded when δ and ε 0 are not too big. For example, if ε 0 < 1 and cδ 2α-1 < 1 2 , C 4 < (3 + 4 α c) 4α .

Proof. Let z n = x ε n -y 0 .

In order to study the error term, we use the following estimation: