Access the full text.

Sign up today, get DeepDyve free for 14 days.

Mathematics
, Volume 2020 (1904) – Apr 24, 2019

/lp/arxiv-cornell-university/diffusive-scaling-of-the-kob-andersen-model-in-mathbb-z-d-1e7Z4Bmmn3

- ISSN
- 0246-0203
- eISSN
- ARCH-3343
- DOI
- 10.1214/19-AIHP1035
- Publisher site
- See Article on Publisher Site

DIFFUSIVE SCALING OF THE KOB-ANDERSEN MODEL IN Z F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI ABSTRACT. We consider the Kob-Andersen model, a cooperative lattice gas with kinetic constraints which has been widely analysed in the physics literature in connection with the study of the liquid/glass transition. We consider the model in a ﬁnite box of linear size L with sources at the boundary. Our result, which holds in any dimension and signiﬁcantly improves upon previous ones, establishes for any positive vacancy density q a purely diffusive scaling of the relaxation time T (q, L) of the system. Furthermore, rel −2 as q ↓ 0 we prove upper and lower bounds on L T (q, L) which agree with the rel physicists belief that the dominant equilibration mechanism is a cooperative motion of rare large droplets of vacancies. The main tools combine a recent set of ideas and techniques developed to establish universality results for kinetically constrained spin models, with methods from bootstrap percolation, oriented percolation and canonical ﬂows for Markov chains. MSC 2010 subject classiﬁcations: 60K35 60J27 Keywords: Kawasaki dynamics, spectral gap, kinetically constrained models 1. INTRODUCTION Kinetically constrained lattice gases (KCLG) are interacting particle systems on the integer lattice Z with hard core exclusion, i.e. with the constraint that on each site there is at most one particle. A conﬁguration is therefore deﬁned by giving for each site x ∈ Z the occupation variable η ∈ {0, 1}, which represents an empty or occupied site respectively. The evolution is given by a continuous time Markov process of Kawasaki type, which allows the exchange of the occupation variables across a bond e = (x, y) of neighbouring sites x and y with rate c (η) (bonds are non oriented, namely (x, y) ≡ (y, x) and c (ω) = c (ω)). This exchange rate equals one if the current conﬁguration yx xy satisﬁes an a priori speciﬁed local constraint and zero otherwise. In the former case we say that the exchange is legal. A key feature of the constraint is that it does not depend on the occupation variables η , η and therefore for any q ∈ [0, 1] detailed balance x y w.r.t. (1 − q)-Bernoulli product measure µ is veriﬁed. Thus, µ is an invariant reversible measure for the process. However, at variance with the simple symmetric exclusion process (SSEP), that corresponds to the case in which the constraint is always veriﬁed, KCLG have several other invariant measures. This is related to the fact that due to the constraints there exist blocked conﬁgurations, namely conﬁgurations for which some exchange rates remain zero forever. KCLG have been introduced in physics literature (see [15,26] for a review) to model the liquid/glass transition that occurs when a liquid is suddenly cooled. In particular This work has been supported by the ERC Starting Grant 680275 “MALIG”, ANR-15-CE40-0020-01 and by PRIN 20155PAWZB “Large Scale Random Structures”. arXiv:1904.11078v2 [math.PR] 28 Oct 2019 2 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI they were devised to mimic the fact that the motion of a molecule in a low temper- ature (dense) liquid can be inhibited by the geometrical constraints created by the surrounding molecules. Thus, to encode this local caging mechanism, the exchange rates of KCLG require a minimal number of empty sites in a certain neighbourhood of e = (x, y) in order for the exchange at e to be allowed. There exists also a non- conservative version of KCLG, the so called Kinetically Constrained Spin Models, which feature a Glauber type dynamics and have been recently studied in several works (see e.g. [7,22,23] and references therein). In this paper we focus on the class of KCLG which has been most studied in physics literature, the so-called Kob-Andersen (KA) models [17]. Each KA model leaves on Z , with d ≥ 2, and is characterised by an integer parameter k with k ∈ [2, d]. The nearest neighbour exchange rates are deﬁned as follows: c (η) = 1 if at least k − 1 neighbours xy of x different from y are empty and at least k − 1 neighbours of y different from x are empty too, c = 0 otherwise. The name KA-kf model is used in the literature to xy refer to the model with parameter k . The choices k = 1 and k > d are discarded: k = 1 would correspond to SSEP; k > d would yield the existence of ﬁnite clusters of particles which are blocked, and therefore for this choice at any q < 1 the inﬁnite volume process would not be ergodic . For example for k = 3, d = 2 a 2 × 2 square fully occupied by particles is blocked: none of these particles can ever jump to their neighboring empty positions. In [30] it has been proven that for all k ∈ [2, d] the inﬁnite volume KA-kf models are ergodic for all q ∈ (0, 1], thus disproving previous conjectures [13, 17, 18] on the occurrence of an ergodicity breaking transition at q > 0 based on numerical simula- tions. In [4] it has been proved that for all q ∈ (0, 1] the rescaled position of a marked −2 particle at time ǫ t converges as ǫ → 0, to a d-dimensional Brownian motion with non-degenerate diffusion matrix. This again disproves a conjecture that had been put forward in physics literature on the occurrence of a diffusive/non-diffusive transition at a ﬁnite critical density q > 0 [17,18]. Motivated by the fact that numerical simula- tions [17,21] suggest the possibility of an anomalous slowing down at high density, in [8] the relaxation time T (namely the inverse of the spectral spectral gap) has been rel studied. For KA-2f in dimension d = 2 it has been proved that in a box of linear size L with boundary sources, T is upper bounded by L log L at any q ∈ (0, 1]. The same rel technique can be extended to establish an analogous upper bound for all choices of d and k ∈ [2, d]. By using this result in [8] it is also proved that the inﬁnite volume time auto-correlation of local functions decays at least as 1/t modulo logarithmic corrections d/2 [8]. A lower bound as 1/t follows by comparison with SSEP. The description of the state of the art for KCLG would not be complete without men- tioning that a purely diffusive scaling L for the inverse of the spectral gap has been established for some KCLG [3,16,25], with and without boundary sources. However, all the models considered in these papers belong to the so called class of non-cooperative KCLG, namely models for which the constraints are such that it is possible to construct Here f stands for ”facilitation”, since k denotes the minimal number of empty sites to allow motion. Here ergodic means that zero is a simple eigenvalue for the generator of the Markov process in L (µ ). 2 3 a ﬁnite group of vacancies, the mobile cluster, with two key properties. (i) For any con- ﬁguration it is possible to move the mobile cluster to any other position in the lattice by a sequence of allowed exchanges; (ii) any nearest neighbour exchange is allowed if the mobile cluster is in a proper position in its vicinity. The existence of ﬁnite mobile clusters is a key tool in the analysis of non-cooperative KCLG and allows the applica- tion of some techniques (e.g. paths arguments) developed for SSEP. It is immediate to verify that instead, for all k ∈ [2, d], KA models belong to the cooperative class, which contain all models that are not non-cooperative. For example for k = d = 2, one can easily check that there cannot exist a ﬁnite mobile cluster by noticing that any a fully occupied double column which spans the lattice can never be destroyed. Besides being a challenging mathematical issue, developing a new set of techniques to prove a purely diffusive scaling for KA and for cooperative models in general is impor- tant from the point of view of the modelization of the liquid/glass transition, since in this context cooperative models are undoubtedly the most relevant ones. Indeed, very roughly speaking, non cooperative models behave like a rescaled SSEP with the mobile cluster playing the role of a single vacancy and are less suitable to describe the rich behavior of glassy dynamics. Here we signiﬁcantly improve upon the existing results, by establishing T (L) ≈ rel 2 d L for all KA-kf models in a ﬁnite box of side L of Z , d ≥ 2, with sources at the boundary (Theorem 1). This is the ﬁrst result establishing a pure diffusive scaling for a cooperative KCLG. The technique that we develop, which is completely different from the one in [8], combines a set of ideas and techniques recently developed by two of the authors to establish universality results for kinetically constrained spin models [22], with methods from oriented percolation and canonical ﬂows for Markov chains. Although we have applied our technique for KA models, we expect our tools to be robust enough to be extended to analyse other KCLG in the ergodic regime. Our main result (cf. Theorem 1 ) establishes upper and lower bounds on T of the rel 2 2 form C (q) × L ≤ T (q, L) ≤ C (q) × L with two parameters C , C that diverge − rel + + − as q → 0 . Remarkably, the divergence of both C (q) and C (q) has the same leading − + behavior, and it is qualitatively in agreement with that conjectured by the physicists [30] and based on the assumption that the dominant mechanism driving the system to equilibrium is a complex cooperative motion of rare large droplets of vacancies. The plan of the paper is the following. In Section 2 we introduce the notation and the results. In Section 3 we prove the upper bound on the relaxation time in several steps. We start by performing a coarse graining (Section 3.1), and proving a coarse- grained constrained Poincar´e inequality (Section 3.3). A key ingredient for this proof is the probability that a certain good event has a large probability, a result that is proved in Section 3.2 by using tools from supercritical oriented percolation. In Section 3.4 and 3.5 we use canonical ﬂows techniques in order to bound from above the r.h.s. of the coarse-grained Poincar´e inequality with the Dirichlet form of KA model, and we conclude by using the variational characterization of the spectral gap. Finally, in Section 4 we prove the lower bound on the relaxation time, ﬁnding an appropriate test function and using again the variational characterization of the gap. 4 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI 2. THE KOB-ANDERSEN MODEL AND THE MAIN RESULT Given an integer L, and a parameter q ∈ (0, 1), we let Λ = [L] ∂Λ = {x ∈ Λ : ∃y ∈/ Λ with kx − yk = 1}. and consider the probability space (Ω , µ ) where Λ Λ n o Ω = η ∈ {0, 1} : η = 0 for all x ∈/ Λ Λ x and µ is the product Bernoulli(1-q) measure. Given η ∈ Ω and V ⊂ Λ, we shall say Λ Λ that V is empty (for η) if η = 0 ∀x ∈ V. Fix an integer k ∈ [2, d] and, for any given a pair of nearest neighbour sites x, y in Λ, write c (·) for the indicator of the event that both x and y have at least k − 1 empty xy neighbours among their nearest neighbours in Λ without counting x, y 1 if (1 − η ) ≥ k − 1 z:kx−zk =1,z6=y c (η) = and (1 − η ) ≥ k − 1, (2.1) xy z:ky−zk =1,z6=x 0 otherwise. and set η if z ∈/ {x, y} xy η := η if z = y η if z = x. η if z 6= x η := 1 − η 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 contin- uous time Markov process deﬁned through the generator which acts on local functions f : Ω → R as X X xy x Lf(η) = c (η)[f(η )−f(η)]+ [(1−η )(1−q)+η q][f(η )−f(η)]. (2.2) xy x x x,y∈Λ x∈∂Λ kx−yk =1 In words, every pair of nearest neighbours sites x, y such that c (η) = 1, with rate xy one and independently across the lattice, exchange their states η , η . In the sequel we x y 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 (q, L) be its relaxation time i.e. the rel inverse of the spectral gap in the spectrum of its generator L (see e.g. [19]). Theorem 1. For any q ∈ (0, 1) there exist two constants C (q), C (q) such that + − 2 2 C (q)L ≤ T (q, L) ≤ C (q)L . − rel + 5 Moreover, as q → 0 the constants C (q) can be taken equal to 1/(d−k+1) exp c/q if 3 ≤ k ≤ d, (k−1) C (q) = (2.3) 2 1/(d−1) exp(c log(q) /q ) if k = 2 ≤ d, ′ 1/(d−k+1) exp c /q if 3 ≤ k ≤ d, (k−1) C (q) = (2.4) ′ 1/(d−1) exp(c /q ) if k = 2 ≤ d, where exp denotes the r-times iterated exponential and c, c are a numerical constants. (r) 3. PROOF OF THE UPPER BOUND IN THEOREM 1 The standard variational characterisation of the spectral gap of L (see e.g. [19]) implies immediately that the upper bound on T (q, L) of Theorem 1 is equivalent to rel the Poincar´e inequality Var(f) ≤ C(q)L D(f) ∀ f : Ω 7→ R, (3.1) where C(q) is as (2.3). Above Var(f) denotes the variance of f w.r.t. the reversible measure µ and D(f) is the Dirichlet form associated to the generator (2.2) X X D(f) = µ c (∇ f) + µ Var (f) , (3.2) xy xy x x,y∈Λ x∈∂Λ kx−yk =1 xy where (∇ f)(η) := f(η ) − f(η) and Var (f) is the local variance w.r.t. η , i.e. the xy x x variance conditioned on {η } . y y6=x ′ ′ Remark 3.1. Consider two systems with sizes L < L , and let γ, γ be the spectral gaps associated with the two generators. Then γ ≤ (2d + 1)γ. (3.3) To see that, let Λ = Λ , Λ = Λ ′, and let D ,D ′ be the Dirichlet forms of the dynamics L L Λ Λ in Λ, Λ . Take a function f : Ω ′ 7→ R depending only on the variables in Λ and observe that Var ′(f) = Var (f). Next we bound D ′(f) as: Λ Λ Λ X X D (f) = µ c (∇ f) + µ (Var (f)) Λ xy xy x ′ ′ x∈∂Λ ∩ ∂Λ x,y∈Λ kx−yk =1 ≤ D (f) + µ c (∇ f) Λ xy xy x∈∂Λ,y∈Λ \Λ kx−yk =1 ≤ D (f) + µ (2 Var (f)) ≤ (2d + 1)D (f). Λ x Λ x∈∂Λ,y∈Λ \Λ kx−yk =1 The last line follows because f does not depend on η for y ∈/ Λ and therefore an exchange for the pair xy, x ∈ Λ and y ∈ Λ \ Λ, is equivalent to a spin ﬂip at x. Thus, 1 2d + 1 ′ ′ Var (f) = Var (f) ≤ D (f) ≤ D (f) Λ Λ Λ Λ ′ ′ γ γ 6 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI implying equation (3.3). We will prove (3.1) in several steps. The ﬁrst step consists in proving a coarse- grained constrained Poincar´e inequality with long range constraints (see Proposition 3.15) under the assumption that the probability π (k, d) of a certain good event (see Deﬁnition 3.9) is sufﬁciently large. Here ℓ is the mesoscopic scale characterising 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 3.1 and 3.2. The second step (see Section 3.4) consists developing canonical ﬂows techniques (see e.g. [19, Chapter 13.5]) for the KA model in order to bound from above the r.h.s. of the coarse-grained Poincar´e inequality by C(ℓ, q)(L/ℓ) D(f), with C(ℓ, q) ≤ d−1 O(ℓ (| log(q)|+log(ℓ))) e (see Proposition 3.24 and Corollary 3.25). The ﬁnal step (see Section 3.6) proves that it is possible to choose ℓ = ℓ(q, k, d) in such a way that π (d, k) is large enough and C(ℓ, q) ≤ C(q) as q → 0, where C(q) is as in (2.3). 3.1. Coarse graining. Let ℓ ∈ N to be ﬁxed later on. By Remark 3.1, we may assume n 1 that N := L/ℓ satisﬁes N = 100 , n ∈ N, so that, in particular, N ∈ N. Later on (see Section 3.6) we will choose ℓ as a function of q and suitably diverging as q → 0. We will then consider the coarse grained lattice of boxes with side ℓ. These boxes will be of d d the form B = ℓi + [ℓ] for i ∈ Z . In order to distinguish between the standard lattice and the coarse-grained lattice we denote the latter by Z . Vertices of the original lattice will always be called sites and they will be denoted using the letters x, y, . . . while the vertices of Z will represent boxes and they will always be denoted using the letters i, j, . . . . d d For x ∈ Z we let B(x) := B , where i(x) ∈ Z is such that B ∋ x. We also i(x) i(x) d d deﬁne Λ = [N] ⊂ Z so that, in particular, Λ = ∪ B . Sometimes we shall simply ℓ i∈Λ i ℓ ℓ write “the box i” meaning the box B and whenever we shall refer to a “box” it will be a generic box i. Deﬁnition 3.2 (Slice). Let E be a subset of the standard basis with size |E| ≤ d − 1, V ⊂ Z a set of sites, and ﬁx a site x ∈ V . Then the |E|-dimensional slice of V passing through x in the directions of E is deﬁned as V ∩ (x + spanE), where spanE is the linear span of E. Deﬁnition 3.3 (Frameable conﬁgurations). Given the d-dimensional cube C = [n] ⊂ d th Z and an integer j ≤ d we deﬁne the j -frame of C as the union of all (j − 1)- dimensional slices of C passing through (1, . . . , 1). Next we introduce the set of (d, j)- frameable conﬁgurations of {0, 1} as those conﬁgurations which are connected by legal th KA-jf exchanges inside C to a conﬁguration for which the j -frame of C is empty. n n We are ﬁnally ready for our deﬁnition of a box B being good for a given conﬁgura- tion. Deﬁnition 3.4 (Good boxes). Given η ∈ Ω , we say that the box B is (d, k)-good for η if all (d − 1)-dimensional slices of B are (d − 1, k − 1)-frameable for all conﬁgurations η ∈ Ω that differ from η in at most one site. The probability that the d-dimensional box B is (d, k)-good will be denoted by π (d, k). ℓ 7 Remark 3.5. 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. 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 is (d, k)-good if the box B is (d, k)-good. 3.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 aforemen- tioned coarse-grained constrained Poincar´e inequality. We shall work on the coarse- d d grained lattice Z so that any vertex i ∈ Z is representative of the mesoscopic box B ℓ ℓ in the original lattice Z . Given a conﬁguration η ∈ Ω we shall consider the induced subgraph of Z whose vertices are the representatives of the good boxes for η. In other words, under the measure µ, we declare each vertex of Z good with probability π (d, k) and bad with probability 1 − π (d, k), independently of all the other vertices. We shall study certain oriented percolation features of the random subgraph of Z consisting of the good vertices when π is sufﬁciently large and the main result here is Proposi- tion 3.11. Throughout this section the parameters d, k will be kept ﬁxed and we shall write π := π (d, k). In the sequel, and up to Proposition 3.11, we shall assume that a ℓ ℓ partition of the vertices of Z into good and bad ones has been given. Deﬁnition 3.6 (Paths). An up-right or oriented path γ in Z starting at i and of length (1) (n) d (1) (t+1) (t) (t) n ∈ N is a sequence γ , . . . , γ ⊂ Z such that γ = i and γ ∈ {γ +~e , γ + (t) ~e } for all t ∈ [n − 1]. γ is focused if d (t) := d γ ,{j : j = i + s(~e + ~e ), s ∈ N} 2 γ 1 2 satisﬁes max d (t) ≤ n. Two consecutive elements of γ form an edge of γ and we say t∈[n] γ ′ (t) that γ, γ are edge-disjoint if they do not share an edge. We say that γ is good if γ is good for all t ∈ [n]. Deﬁnition 3.7 (Good family of paths). Fix i ∈ Z . 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. (3) |G| ≥ N. √ √ Remark 3.8. There are N sites at distance N from i that can be reached by an up- right path (recall that distances are in the ℓ -norm). Consider now the paths of G passing through a vertex j whose distance from i is N. Such a path could go either up or to the right, and since these edges are at distance larger than N from i, (2) in the above deﬁnition implies that only two such paths could exist. Therefore, |G| ≤ 2 N. Given i ∈ Z let D be the segment n o √ √ √ √ 1 1 1 D = i + N − t ~e + N + t ~e | − N ≤ t ≤ N . (3.4) 1 2 2 2 2 2 8 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI Let also H , V be the rectangular subsets of the form n n H = {j ∈ Z : j = i + a~e + b~e , a ∈ [0, ℓ ], b ∈ [0, ℓ ]} n 1 2 n n−1 V = {j ∈ Z : j = i + a~e + b~e , a ∈ [0, ℓ ], b ∈ [0, ℓ ]} n 1 2 n−1 n where ℓ = 10 . We shall prove that the existence of a good family of paths for the vertex i ∈ Z is guaranteed by the simultaneous occurrence of certain events A,B and {C } , where, recalling the choice of L in the beginning of Section 3.1, n is such n ∗ n=1 that ℓ = N (cf. Figure 1). ℓ ∗ = N FIGURE 1. A graphical illustration of the proof of Lemma 3.10. For better rendering the drawn paths are not perfectly oriented and the ratio among the sides of rectangles in the drawings is not 1/10 as it should be. The blue segment corresponds to the set D . The red paths are the good up-right paths guaranteed by the event B. The blacks paths are the good up-right hard crossings guaranteed by the events C . Deﬁnition 3.9 (The events A, B and C ). (i) Let R be the rectangle in Z whose short sides are D and D + 2N(~e +~e ). Then A i i i 1 2 is the event that there are at least 1.9 N edge-disjoint good up-right paths contained in R and connecting D with D + 2N(~e + ~e ). i i i 1 2 (ii) B is the event that the set ∪ {i+t~e }∪{i+t~e } is connected to at least 0.7 N 1 2 t∈[0, N ] vertices of D \ (H ∪ V ) by a good up-right path, i n n ∗ ∗ 9 (iii) C is the event that i is good and there exists a good up-right hard-crossing of both V and H , i.e. a good up-right path connecting the two short sides of V (H ) and n n n n which is contained in V (H ). n n The next lemma guarantees the existence of a good family of paths for i ∈ Z . We emphasise that these are paths whose vertices represent good boxes. Lemma 3.10. Assume that A ∩ B ∩ C occurs for all n ∈ [n ]. Then there exists a good n ∗ family of paths for i ∈ Z . Proof. We show ﬁrst that i is connected by a good up-right path to the set D ∩ H i n and to the set D ∩ V . Let n = 1, and deﬁne recursively n , k ∈ [n − 1] as the i n 1 ⋆ ∗ k+1 largest integer n ∈ [n ] such that there exists a crossing of H starting from the set ∗ n {i + t~e , t ∈ [0, ℓ ]}. Since the events C all occur, the sequence {n } is strictly 2 n n k k k=1 increasing as long as n ≤ n . k ∗ Then, starting from V ≡ V we can ﬁrst follows the lowest hard crossing of H 1 n n 1 2 until we reach a hard crossing of V . Then we follow the latter until meeting a hard crossing of H and so on. At the end of this procedure the set V , and a fortiori the n 1 box i, becomes connected by a good up-right path to the right short side of H and hence also to one of the vertices of D ∩ H . The same construction can be repeated i n symmetrically by inverting the role of H and V . Therefore we conclude that there exists a good up-right path connecting i to D ∩ H and a good up-right path connecting i to i n D ∩ V . See Figure 1. i n √ √ Recall that ℓ = N. Then, since |D ∩ H | = |D ∩ V | = N/10 and since n i n i n ∗ ∗ ∗ each each vertex can be the starting point of at most two edge disjoint paths, there could be at most 2|(D ∩ H ) ∪ (D ∩ V )| = 0.4 N edge-disjoint path starting from i n i n ∗ ∗ (D ∩ H )∪ (D ∩ V ). Hence, the event A guarantees that there are at least 1.9 N − i n i n ∗ ∗ √ √ 0.4 N = 1.5 N edge-disjoint paths starting in D \ (H ∪ V ). Since each starting i n n ∗ ∗ point for these paths could belong to at most two paths, at least 0.75 N boxes of D \ (H ∪ V ) are the starting point of an edge-disjoint up-right paths crossing R . i n n i ∗ ∗ √ √ Using event B and noticing that |D \ (H ∪ V )| = 0.8 N, at most 0.1 N boxes i n n ∗ ∗ in D \ (H ∪ V ) are not connected to ∪ {i + t~e } ∪ {i + t~e }. That is, the i n n 1 2 ∗ ∗ t∈[0, N ] number of boxes in D \ (H ∪ V ) that are at the same time the starting point of an i n n ∗ ∗ edge-disjoint up-right path crossing R and connected to ∪ {i + t~e } ∪ {i + t~e } i 1 2 t∈[0, N ] √ √ √ is at least 0.75 N − 0.1 N = 0.65 N. Using now the fact that i is connected by a good up-right path to the set D ∩ H i n and to the set D ∩ V , we conclude that there exist at least 0.65 N good up-right i n paths from i to D + 2N(~e + ~e ) which, after crossing D become edge-disjoint and i 1 2 i never leave R . The thick path of Fig. 1 is one of these paths, drawn up to its crossing with D (R is not depicted in the ﬁgure due to lack of space). These paths form the i i sought good family as required. Our next task is to prove that if π is sufﬁciently close to one then, uniformly in n, A,B and C are very likely. As proved in Section 3.6 that will be the case if the mesoscopic scale ℓ is suitably chosen as a function of q, d, k. 10 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI Proposition 3.11. For any λ > 0 there exists π < 1 such that for π ≥ π and all ∗ ℓ ∗ n, N ∈ N −λℓ n−1 (a) µ (C ) ≥ 1 − e , −λ N (b) µ (B) ≥ 1 − e , −λ N (c) µ (A) ≥ 1 − e . In particular a family of good paths starting at i exists w.h.p if π is sufﬁciently close to one. Proof. (a) This can be proven by a contour argument. Consider the rectangle V , 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 ℓ steps to the right and ends somewhere on the right boundary of V . 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 difﬁcult to prove that for π sufﬁciently large depending on λ c −λℓ µ (there is not a good hard crossing) = µ (C ) ≤ e . (b) Consider the down-left good oriented paths starting from sites of D \(H ∪V ). i n∗ n∗ The event B certainly occurs if at least 7/8 of the points in this set are the starting point of an inﬁnite down-left good oriented path. The upper bound on the probability of B then follows directly from [11, Theorem 1] . (c) The main tool here is the max-ﬂow min-cut theorem (see e.g. [5]). Given a directed graph (V, E) a ﬂow f is a non-negative function deﬁned on the edges; we −→ −→ write f(u, v) instead of f(uv) for the value of the ﬂow on the directed edge uv. Given two disjoint sets of vertices s = {s , . . . , s }, t = {t , . . . , t } called the sources and 1 k 1 m the sinks respectively we say that f : E → R is a ﬂow from s to t if for all v 6∈ {s , . . . , s } ∪ {t , . . . , t } 1 k 1 m X X f(u, v) = f(v, w). u:(u,v)∈E w:(v,w)∈E In other words, for all vertices outside s∪ t the incoming ﬂow equals the outgoing ﬂow. Finally, given a capacity function c : E → R we say that a ﬂow f satisﬁes the capacity constraint if f(e) ≤ c(e) for all e ∈ E. Given a ﬂow from s to t the value of the ﬂow v(f) is deﬁned as the total ﬂow going in the sinks (which is the same as the ﬂow leaving the sources), namely X X v(f) := f(v, t ). j=1 v:(v,t )∈E Though the Theorem is stated for the contact process, it also holds for oriented percolation as stated in [11]). 11 A cut (S, T ) is a partition of V in two subsets S and T , such that all the sources belong to S and all the sinks belong to T . The capacity of a cut (S, T ) is the sum of capacities of the edges pointing from S to T . Theorem (Max-Flow Min-Cut theorem). Given a set of sources s and a set of sinks t and a capacity function c, the maximum value of a ﬂow from s to t satisfying the capacity constraint is equal the minimum capacity of a cut. Moreover, if all capacities are integers, there is a ﬂow f satisfying the above requirements such that f(e) ∈ N for all e ∈ E and its value v(f) is maximal. In order to use this theorem for the proof of part (c) of the proposition we ﬁrst deﬁne our graph G = (V, E). The vertex set is n o √ √ V = i + a~e + b~e : a, b ∈ [N] , a + b ≥ N, |a − b| ≤ N ∩ Λ , 1 2 ℓ and the directed edges are ′ ′ E = j, j : j is good and j ∈ {j + ~e , j + ~e } . 1 2 Remark 3.12. Notice that the requirement that edges have their starting point only at the good vertices of V is the only place where randomness enters. We then choose as source set the set: n o s = j ∈ V : ki − jk = N , and as sink set the set: t = V ∩ {j | (~e , j) = N or (~e , j) = N} . 1 2 Finally we assign unitary capacity to all edges of E. With this choice, the maximal value of a ﬂow f from s to t satisfying f(e) ∈ {0, 1} will be exactly the number of edge- disjoint good up-right paths contained in R and connecting D with D + 2N(~e + ~e ). i i i 1 2 We have thus reduced the proof of part (c) to the following claim: −λ N Claim 3.13. If π is large enough, with probability greater than 1 − e the graph constructed above is such that the capacity of any cut is at least 1.9 N. Proof of the claim. In order to prove the claim, for every cut (S, T ) we will construct a dual path γ := γ that will separate S from T satisfying the following property. If the S,T √ √ capacity of the cut is smaller than 1.9 N then there are at least |γ|/2− 0.9 N vertices in V which are bad and which neighbor γ. Here |γ| ≥ 2 N is the length of γ. A simple −λ N Peierls argument then proves that the latter event has probability at most e for any π large enough. First, let us deﬁne a dual graph V for some ﬁxed (S, T ). Its vertices will be the faces of Λ that have at least three neighbors in V . That is, 1 1 ∗ ∗ ∗ V = i ∈ Λ + ~e + ~e : #{i ∈ V : ki − ik = 1} ≥ 3 . ℓ 1 2 1 2 2 12 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI Left boundary Right boundary FIGURE 2. Black dots are the vertices of V , grey dots are the vertices of ∗ ∗ V , diamonds are the left and right boundary of V . ∗ ∗ ∗ ∗ ∗ Its (directed) edges will depend on the cut (S, T ). For i , j ∈ V , (i , j ) is an edge ∗ ∗ if ki − j k = 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 1 1 i + N + + a ~e + + a ~e : a ∈ [N] ∩ V , 1 2 2 2 (2) the left boundary 1 1 i + N + + a ~e + + a ~e : a ∈ [N] ∩ V , 1 2 2 2 (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 neighbouring vertices of V (namely {j ∈ V : kj − ik = 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. 3). At the boundaries, however, there could be vertices that have an outgoing degree different from the incoming degree. Consider a site on the right boundary (see left ∗ 1 1 + ∗ 1 1 part of Fig. 3) j = i + N + + a ~e + + a ~e . Let j = j + ~e + ~e and 1 2 1 2 a a a 2 2 2 2 − ∗ 1 1 + − j = j − ~e − ~e . If both j and j are in S, or if both are in T , then the incoming a a 1 2 a a 2 2 ∗ + − degree of j is the same as its outgoing degree. However, if j ∈ S and j ∈ T then a a a + − the incoming degree is 1 and the outgoing degree is 0. For the case j ∈ T and j ∈ S, a a + − we have an outgoing degree 1 and incoming degree 0. j = j , therefore the total a+1 13 S S S S S T S T T T S S S T T S T S S T S T S T S S T S FIGURE 3. Incoming and outgoing degrees of vertices on the boundary of V (left) and its interior (right) outgoing degree of sites on the right boundary is − − # a : j ∈ S, j ∈ T a+1 and the total incoming degree is # a : j ∈ T, j ∈ S . a a+1 But since the ﬁrst site (i.e. , j ) 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 bound- ary is larger by 1 than its outgoing degree. This implies that there exists a dual path (1) (n) (1) (n) γ = j , . . . , j , where j in on the right boundary and j is on the left bound- ∗ ∗ ∗ ∗ ∗ ary. In particular, n ≥ 2 N. The capacity of 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 n o (t+1) (t) (t+1) (t) # t : j − j ∈ {−~e ,~e } and j , j crosses an edge in E . ∗ ∗ 1 2 ∗ ∗ We therefore consider the number of steps that γ takes in each direction: n o (t+1) (t) R = # t : j − j = ~e , ∗ ∗ 1 n o (t+1) (t) L = # t : j − j = −~e , ∗ ∗ 1 n o (t+1) (t) U = # t : j − j = ~e , ∗ ∗ 2 n o (t+1) (t) D = # t : j − j = −~e . ∗ ∗ 2 14 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI (n) (1) Observe that i − i = (R − L)~e + (U − D)~e , and since ∗ ∗ 1 2 (1) ~e − ~e , j = (~e − ~e , i) + N, 1 2 ∗ 1 2 (n) ~e − ~e , j = (~e − ~e , i) − N, 1 2 ∗ 1 2 √ √ U + L − D − R = 2 N. Therefore, since U + L + R + D = n we get U + L = + N. Deﬁnition 3.14. We will say that a pair (j, j ) of vertices of V form a erased edge if the vertex j is bad and j ∈ {j + ~e , j + ~e }. In other words, these are the edges of the original 1 2 Λ that do not belong to our graph G = (V, E). Assume now that the capacity of the cut is less than 1.9 N. From the previous √ √ observations it follows that γ must cross at least U + L − 1.9 N = n/2 − 0.9 N erased edges. Since every such erased edge comes from a bad vertex, and since at most two erased edges could share the same bad vertex, at least n/4−0.45 N of the vertices to the left of γ are bad. Therefore, the probability that there exists a cut with capacity less than 1.9 N is upper bounded by the probability that there exists a dual path of √ √ length n ≥ 2 N with at least n/4 − 0.45 N bad vertices on its left. Since there are at most 2 dual paths of length n, if π was taken large enough depending on λ, we get µ (capacity of any cut ≥ 1.9 N) ∞ n X X n −λ N ≥ 1 − 2 (1 − π) ≥ 1 − e . √ √ n=2 N k=n/4−0.45 N The proof of the proposition is complete. 3.3. A long range Poincare´ inequality. Recall the setting of Sections 3.1, 3.2 and in particular Deﬁnition 3.7 of a good family of paths for a vertex i ∈ Z . Let Q = d d d i + {0, 1} \ {0} ⊂ Z and deﬁne 1 if any j ∈ Q is good and there exists a good family of paths for i +~e , i 1 cˆ = 0 otherwise. (3.5) In this section we shall prove the following result. Recall that π := π (d, k) is the ℓ ℓ probability that any given i ∈ Z is (d, k)-good. Proposition 3.15. There exists π < 1 such that for any π ≥ π and any local function ∗ ℓ ∗ f : Ω → R Var(f) ≤ 4 µ cˆ Var (f) . (3.6) i B i∈Λ Proof. We will closely follow the proof of [22, Theorem 2.6]. Let c˜ be the indicator of the event A ∩ B ∩ C (see Deﬁnition 3.9), together with the requirement that Q is n i n=1 good. By Lemma 3.10 c˜ ≤ cˆ for all i ∈ Z . Hence, in order to prove (3.6), it is enough i i to prove the stronger constrained Poincar´e inequality in which in the r.h.s. of (3.6) the 15 constraint cˆ is replaced by c˜ . Using Proposition 3.11 together with the obvious bound i i µ (Q is good) ≥ 1 − (2 − 1)(1 − π ), the proof of the latter is now identical to the one i ℓ given in [22, Theorem 2.6]. 3.4. Constructing the canonical path on the coarse-grained lattice. In this section we will construct a set of T -step moves – sequences of at most T ∈ N legal moves for the KA dynamics (i.e. legal exchanges or resampling of boundary sites) that could be chained together in order to ﬂip the state of an arbitrary point x ∈ Z . The construction of the move is quite cumbersome, so we will only give here the required deﬁnitions and the statement of the result. For details see [28, Chapter 5] and the supplementary ﬁle to the arXiv version of this paper. The next deﬁnition describes how to move from one conﬁguration to the other using only legal KA exchanges. It will provide a way to construct, for a given initial con- ﬁguration, a certain path in conﬁguration space. We emphasise that, unlike the paths introduced earlier, this is not a geometric path in Λ , but a path in the much larger conﬁguration space Ω . Deﬁnition 3.16 (T -step move). Fix an integer k ≤ d. Given a ﬁnite connected subset V of Λ and M ⊂ Ω, a T -step move for KA-kf dynamics M = (M , . . . , M ) taking place in 0 T T +1 V and with domain Dom(M) = M is a function from M to Ω such that the sequence M(η) = (M (η), . . . , M (η)) , η ∈ M, satisﬁes: 0 T (i) M (η) = η, (ii) for any t ∈ [T ], the conﬁgurations M (η) and M (η) are either identical or linked t−1 t by a legal move contained in V , i.e. either a legal KA-kf exchange among sites x, y ∈ V or a resampling at a boundary site z ∈ ∂V . Deﬁnition 3.17 (Information loss and energy barrier). Given a T -step move M its in- formation loss Loss (M) at time t ∈ [T ] is deﬁned as Loss (M) ′ ′ 2 = sup # η ∈ Dom(M)| M (η) = M (η ), M (η) = M (η ) . t t t+1 t+1 η ∈Dom(M) In other words, knowing M (η) and M (η), we are guaranteed that η is one of at most t t+1 Loss (M) 2 conﬁgurations. We also set Loss(M) := sup Loss (M). The energy barrier of M is deﬁned as E(M) = sup sup |#{empty sites in M (η)} − #{empty sites in η}| . η∈Dom(M) t∈[T ] The main result is the following proposition that guarantees the existence of a T - step move with a bounded information loss and energy barrier that allows to ﬂip the conﬁguration at x (namely to go from η → η ) provided η has a certain up-right good d d d path. Recall that Q = i + {0, 1} \ {0} ⊂ Z and that N = L/ℓ. Proposition 3.18. Fix an integer k ≤ d. Fix i ∈ Λ and x ∈ B . If i + ~e ∈ Λ ﬁx also an ℓ i 1 ℓ up-right path γ connecting i + ~e to ∂Λ . Then there exists a T -step move M with 1 ℓ Dom(M) = {η | γ is good and all j ∈ Q ∩ Λ are good} , i ℓ 16 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI taking place in ∪ B ∪ (Q ∩ Λ ) and such that, for all η ∈ Dom(M) and all t ∈ [T ], j∈γ j i ℓ M (η) ∈ Dom(M) and M (η) is the conﬁguration η ﬂipped at x. Moreover, E (M) ≤ t T k−1 Cℓ , and for all j ∈ Λ (j) λ λ Loss(M) ≤ C log (ℓ)ℓ, T ≤ CNℓ , T ≤ Cℓ for k = 2 d d (j) d ℓ ℓ Loss(M) ≤ Cℓ , T ≤ CN2 , T ≤ C2 for k ≥ 3 (j) where T is the set of indices t ∈ [T ] such that for some η ∈ Dom(M) the conﬁgurations (M (η), M η) are linked together by a legal KA-transition inside B . The constants C, λ t t+1 j may depend only on k and d. In order to ﬂip the state of a site x we must perform a legal KA exchange touching x which in turn requires having enough empty sites in the vicinity of x. Patches of empty sites (e.g. a super-good box i.e. a good box with an empty row for d = k = 2) are certainly present inside the percolation structure of the good boxes. However, typically they will be quite far from x because q ≪ 1. The main idea behind the proof of the proposition is to prove that such super-good boxes can be moved at will inside the good percolation network and brought near x by concatenating suitable “elementary” T -steps moves. This concatenation will form the sought global T -step move M. Unfortunately the general construction of the elementary moves is a bit cumbersome and technical. For the interested reader we refer to [28, Chapter 5] and to the supple- mentary ﬁle attached to the arXiv version of this paper. Still, we will present a sketch of the construction for the particular case k = d = 2 that will give a ﬂavour of the type of arguments used there. 3.4.1. Sketch of the proof of Proposition 3.18 for k = 2, d = 2. We will ﬁrst introduce the notion of almost good – a box is said to be almost good if it contains at least one empty site in every line and every column. Recall that a good box is a box that remains almost good even after ﬁlling one of its sites. Claim 3.19 (Exchanging rows). Fix y ∈ Z , and consider the conﬁgurations in which the row y + [ℓ] × {0} is empty, and the row above it contains at least one empty site. Then there exists a T -step move M whose domain consists of these conﬁgurations, and in the ﬁnal state M (η) the rows y + [ℓ] × {0} and y + [ℓ] × {1} are exchanged. Moreover, Loss(M) = O(log ℓ) and T = O(ℓ). See Figure 4. Note that even though the claim is formulated for exchanging rows, the same will hold for columns. The path γ in Proposition 3.18 is a general up-right path, but imagine for the moment that it is a straight path going right all the way to the boundary of Λ . In this case, we can create an empty column on the boundary of Λ, and use Claim 3.19 to propagate it until it reaches the right side of the box B . Assume further that all of the boxes in Q are connected to the boundary by straight paths. The same construction as before will then allow us to empty all the sites in the 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 FIGURE 4. This ﬁgure shows how to exchange an empty row with a neighbouring row containing at least one empty site (see Claim 3.19). The loss comes from the fact that there are ℓ options for the position of the empty site in the upper row. outer up-right boundary of B . Figure 6 shows how in this state one can permute sites in B , so in particular we are able to change the occupation at x. This, however, only allows us to exchange x with another site in the same box; in order to ﬂip its state without changing the other sites we must exchange it with a boundary site, which is connected to the reservoir (namely, it is being resampled from equilibrium, and in particular the number of particles is not conserved). In order to move the site to the other side of the empty column we use the following claim: Claim 3.20 (Moving a marked site). Fix y ∈ Z and some marked site ⋆ ∈ y +{−1}×[ℓ]. Consider the conﬁgurations in which the column y + {0} × [ℓ] is empty, and each of the columns y + {±1} × [ℓ] contains at least one empty site, not counting the site ⋆. Then there exists a T -step move M whose domain consists of these conﬁgurations, and in the ﬁnal state M (η) the sites ⋆ and ⋆ + (2, 0) change their occupation values. Moreover, Loss(M) = O(log ℓ) and T = O(ℓ). See Figure 7. For this (very untypical) case, when the paths have no turns, the last claim will ﬁnish the construction – after emptying the outer up-right boundary of B and bringing the site x to the rightmost column of B , apply consecutively Claim 3.19 and Claim 3.20. The energy barrier is at most 3ℓ since we empty three rows/columns, and the time is O(Lℓ ). The loss of information is also O(ℓ), since at each step we only need to reconstruct the three empty row/columns. If we are in the course of a move described in Claim 3.19 we must also pay its loss, but this gives a lower order contribution. When the paths turn, however, we cannot propagate the empty line like before, and a more complicated mechanism is required. The ﬁrst step consists in framing a frameamble box (recall Deﬁnition 3.3). When d = k = 2, it means the following: Claim 3.21 (Framing a box). Fix a box, and consider the conﬁgurations for which the box is almost good, and, in addition, its bottom row is empty. Then there exists a T -step move M whose domain consists of these conﬁgurations, and in the ﬁnal state M (η) the left column is also empty. Moreover, Loss(M) = O(ℓ log ℓ) and T = O(ℓ ). See Figure 5. Once a box is framed, we can use again Figure 6 in order to construct a general permutation inside it, and in particular we are able to reﬂect the conﬁguration. 18 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI Claim 3.22 (Reﬂecting a framed conﬁguration). Fix a box, and consider the conﬁgura- tions for which the box is framed, i.e. , its bottom row and left column are empty. Then there exists a T -step move M whose domain consists of these conﬁgurations, and in the ﬁnal state M (η) the conﬁguration inside the box is reﬂected along the axis connecting its bottom left corner with its up right corner. Moreover, Loss(M) = 0 and T = O(ℓ ). 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 FIGURE 5. Framing an almost good box. See Claim 3.21 Now we are allowed, when reaching a turn of the path, to frame the box, reﬂect the conﬁguration, ”unframe” the reﬂected box, and continue propagating the marked site to ﬁnish the construction as in the corner-less case. The dominating contribution to the total loss is coming from the framing move, O(ℓ log (ℓ)), the energy barrier remains the one coming from the creation of empty sites on the boundary, O(ℓ), and the time is O(L ℓ ). 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a a a b 0 b 0 b 0 b 0 0 0 0 0 FIGURE 6. This ﬁgure shows how to exchange two arbitrary neighbour- ing sites of a box if the external top row and right column are empty. By a concatenation of such moves it is possible to exchange any two internal sites. a a ⋆ ⋆ 0 0 0 0 0 0 0 0 ⋆ 0 a ⋆ 0 0 ⋆ 0 a a 0 a 0 ⋆ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 FIGURE 7. This ﬁgure shows how to make a marked site jump beyond an empty column. See Claim 3.20. 19 3.5. From the long range Poincare inequality to the Kob-Andersen dynamics. In this section we bound from above the Dirichlet form with the long range constraints appearing in the r.h.s. of (3.6) with that of the KA model in Λ (3.2). Given i ∈ Λ our aim is to bound the quantity µ (cˆ Var (f) appearing in the r.h.s. of (3.6) using the i B 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 } . The main advantage of the above conditioning is that the good {B is good} j∈Λ ,j6=i j ℓ family for the vertex i +~e , whose existence is guaranteed by the long range constraint cˆ , become deterministic. We will thus work ﬁrst in a ﬁxed realisation of the coarse- grained variables satisfying cˆ = 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 ∈ Λ let γ be an up-right focused path γ of length 2N starting at i+~e and let ℓ 1 G be the event that γ is good and all j ∈ Q ∩Λ are good. Let also V := B ∪ i,γ i ℓ i,γ i j∈γ∪Q B and let F be the σ-algebra generated by the random variables {1 } . j i j∈Λ ,j6=i {B is good} j ℓ Notice that G is measurable w.r.t. F . Finally write i,γ i X X D (f |F ) := µ c ∇ f |F + µ Var (f)|F , i,γ i xy xy i x i x,y∈V ∩Λ x∈V ∩∂Λ i,γ i,γ kx−yk =1 where Var (f), as before, is the variance conditioned on the occupation of the sites in Λ \ {x}. Clearly the average w.r.t. µ of D (f |F ) represents the contribution coming i,γ i from the set V ∩ Λ to the total Dirichlet form D(f). i,γ For simplicity in the sequel we shall write C(ℓ, q) for any positive function such that, as ℓ ↑ +∞, q ↓ 0, O(ℓ| log(q)|+ℓ log(ℓ)) C(ℓ, q) = e for k = 2, (3.7) k−1 d O(ℓ | log(q)|+ℓ log(ℓ)) C(ℓ, q) = e for k ≥ 3. (3.8) Of course the constant in the O(·) notation may change from line to line. Lemma 3.23. On the event G i,γ µ Var (f)|F ≤ O(N)C(ℓ, q)D (f |F ) ∀f : Ω 7→ R. B i i,γ i Λ Proof. Assume 1 = 1. Since the marginal of µ (·|F ) on {0, 1} is a product measure G i i,γ we have immediately that µ Var (f)|F ≤ µ Var (f)|F , B i x i x∈B and it is sufﬁcient to prove that max µ Var (f)|F ≤ O(N)C(ℓ, q)D (f |F ). x i i,γ i x∈B Given x ∈ B , Proposition 3.18 and the assumption 1 = 1 imply that there exists i G i,γ a T -step move M with Dom(M) = G , taking place in V ∩ Λ and such that for all i,γ i,γ η ∈ Dom(M) M η is the conﬁguration η ﬂipped at x. Notice that M does not change T 20 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI the variables {1 } . Hence, on the event G , j∈Λ ,j6=i i,γ {B is good} j ℓ T−1 Var (f) = pq f(η) − f(η ) ≤ f(M (η)) − f(M (η)) x t t+1 t=0 T−1 ≤ T f(M (η)) − f(M (η)) . (3.9) t t+1 t=0 In order to proceed it is convenient to introduce the following notation. ′ 2 ′ ′ A pair of conﬁgurations e = (η, η ) ∈ Ω is called a KA-edge if η 6= η and η is obtained from η by applying to η either a legal exchange at some bond b of Λ or a spin ﬂip at some site z ∈ ∂Λ. If b or z belong to a given V ⊂ Λ we say that the edge e occurs in e e e ′ ′ V . Given a KA-edge e = (η, η ) we write ∇ f := f(η ) − f(η). Finally the collection of all KA-edges in Ω is denoted Ω . KA By construction, if M (η) 6= M (η) then e := (M (η), M (η)) is a KA-edge and t+1 t t t t+1 the r.h.s. of (3.9) can be written as T−1 T c ∇ f , e e t t t=0 where c is the kinetic constraint associated to the KA-edge e . Taking the expectation e t over η w.r.t. µ (·|F ) yields X X µ Var (f)|F ≤ T µ c ∇ f 1 |F . (3.10) x i e e i {e=(M (η),M (η))} t t+1 e∈Ω t=0 KA Next we use the following chain of observations (recall Proposition 3.18 and the rele- vant deﬁnitions therein). (i) For any KA-edge e and any η such that e = (M (η), M (η)) for some t ≤ T it t t+1 holds that (for q < 1/2) −E(M) µ (η) ≤ q µ (M (η)). (ii) Since the T -move M takes place in the set V ∩ Λ, in the r.h.s. of (3.10) we can i,γ replace by e∈Ω KA e∈Ω KA e occurs in V ∩ Λ i,γ (iii) Given a KA-edge e occurring in some B ⊂ V ∩ Λ, j i,γ XX (j) Loss(M) 1 ≤ 2 |T |. {e=(M (η),M (η))} t t+1 M η∈Ω t=1 Using the above remarks, on the event G , i,γ (j) Loss(M) E(M) µ Var (f)|F ≤ T 2 |T |q µ (η |F )c (η) ∇ f . x i i e e e=(η,η )∈Ω KA e occurs in V ∩ Λ i,γ 21 This expression, by Proposition 3.18, satisﬁes the required bound. We are now ready to state the main result of this section. Proposition 3.24. Let D (f) = µ cˆ Var (f) and let D(f) be the Dirichlet form i B i∈Λ i of the KA model. Then ℓ 2 D (f) ≤ O(N )C(ℓ, q)D(f). Corollary 3.25. Fix 2 ≤ k ≤ d together with q ∈ (0, 1). Assume that it is possible to choose the mesoscopic scale ℓ depending only on k, d, q in such a way that π (d, k) ≥ π , ℓ ∗ where π is the constant appearing in Proposition 3.15. Then Var(f) ≤ O(N )C(ℓ, q)D(f). Equivalently T (q, L) ≤ O(L )C(ℓ, q). rel Proof of the Corollary. The ﬁrst part of the corollary follows at once from Propositions 3.15 and 3.24. The second part is an immediate consequence of the ﬁrst one and of the variational characterisation of the relaxation time (see the beginning of Section 3). Proof of Proposition 3.24. Recall deﬁnition (3.5) of the long range constraints cˆ and let us consider one term µ cˆ Var (f) appearing in the deﬁnition of D (f). Observe i B that cˆ is measurable w.r.t. the σ-algebra F . Conditionally on F and assuming that i i i cˆ = 1, let G be a family of good paths for the vertex i + ~e + ~e ∈ Z . Clearly cˆ = 1 i 1 2 i implies that G occurs for each path γ ∈ G. Hence, by applying Lemma 3.23 to each i,γ path in G we get µ Var (f)|F ≤ O(N)C(ℓ, q) D i,γ B i |G| γ∈G X X = O(N)C(ℓ, q) µ c ∇ f |F 1 xy xy i {(x,y)⊂V } i,γ |G| x,y∈Λ γ∈G kx−yk =1 X X + µ Var (f)|F 1 . (3.11) x i {x∈V } i,γ |G| x∈∂Λ γ∈G For a given bond (x, y) ⊂ Λ (respectively x ∈ ∂Λ) let j = j(x) be such that B ∋ x and let Π denote the (~e ,~e )-plane in Z containing j. Since all the paths forming the j 1 2 family G belong to the plane Π , and are focused we immediately get that X X 1 1 1 = 1 1 1 , {(x,y)⊂V } {j∈Π } {j∈R } {(x,y)⊂V } i,γ i i i,γ |G| |G| γ∈G γ∈G X X 1 1 1 = 1 1 1 {x∈∂V } {j∈Π } {j∈R } {x∈∂V } i,γ i i i,γ |G| |G| γ∈G γ∈G where R is the set of points at distance at most N from the set {k : k = i + s(~e + i 1 ~e ), s ∈ N}. Next, for (x, y) ⊂ Λ (respectively x ∈ ∂Λ) such that ki − jk ≤ N we bound 1 22 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI P P 1 1 1 (respectively 1 ) by one. If instead ki − jk > {(x,y)⊂V } {x∈∂V } |G| γ∈G i,γ |G| γ∈G i,γ N then we use the fact that the paths of G are almost edge-disjoint to bound from above both sums by 2/|G| ≤ 2/ N. In conclusion, the ﬁrst and second term inside the square bracket in the r.h.s. of (3.11) are bounded from above by √ √ µ c ∇ f |F 1 1 1 + √ 1 xy xy i {j∈Π } {j∈R } i i {ki−j(x)k ≤ N} {ki−j(x)k > N} 1 1 x,y∈Λ kx−yk =1 and √ √ µ Var (f)|F 1 1 1 + √ 1 x i {j∈Π } {j∈R } i i {ki−j(x)k ≤ N} {ki−j(x)k > N} 1 1 x∈∂Λ 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 ∈ Λ, √ √ 1 1 1 + √ 1 ≤ O(N). {j∈Π } {j∈R } i i {ki−j(x)k ≤ N} {ki−j(x)k > N} 1 1 i∈Λ 3.6. Completing the proof of the upper bound. Using Corollary 3.25, the proof of the upper bound 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 ℓ = ℓ(q, k, d) in such a way that (i) the probability that any given i ∈ Z is (d, k)-good satisﬁes π (d, k) ≥ π ; ℓ ∗ (ii) C(ℓ, q) ≤ C(q) as q → 0, where C(q) is as in (2.3) and C(ℓ, q) satisﬁes (3.7). Let us start by stating a key result on the probability of the set of frameable conﬁgura- tions Proposition 3.26 (Probability of frameable conﬁgurations [30]). Fix q and let F (ℓ, d, j) be the probability that the cube C = [ℓ] is (d, j)-frameable. Then there exists C > 0 s.t. for q → 0 −ℓ /Ξ d,j F (ℓ, d, j) ≥ 1 − Ce ∀ℓ s.t. Ξ (q) = O(ℓ ) q q q d,k with 1/d Ξ (q) := d,1 and Ξ (q) := exp ∀j ∈ [2, d]. d,j (j−1) 1 d−j+1 Proof. The case j = 1 follows immediately from the deﬁnition of frameable conﬁg- urations (see Deﬁnition 3.3). The cases j ∈ [2, d] are proven in Section 2 of [30], see formula (34) and (36), where the results are stated in terms of the parameter There is a misprint in formula (34) of [30]: in the exponential a minus sign is missing 23 s = j − 1. Actually, the deﬁnition of frameable in [30] is more restrictive than our Def- inition 3.3. Indeed in [30] the frame that should be emptiable is composed by all the faces of dimension j − 1 containing one corner of C (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 [30] . Then, by using Proposition 3.26 and the Deﬁnition 3.4, we get that there exists c > 0 s.t. by choosing d−j+1 ℓ(q, k, d) = exp c/q ∀k ∈ [3, d] (k−2) and d−1 ℓ(q, 2, d) = | log q|/q we get ℓd −ℓ/Ξ d−1,k−1 π (d, k) ≥ 1 − C exp which goes to 1 as q → 0, and thus implies that condition (i) is satisﬁed for all q ∈ (0, 1) (since π (d, k) is non decreasing with q) . Finally, it is immediate to verify that the above choice of ℓ satisﬁes also condition (ii) for all k ∈ [2, d]. 4. PROOF OF THE LOWER BOUND IN THEOREM 1 In this section we will prove the lower bound on the relaxation time by ﬁnding suitable positive constants c, λ depending on d, k and a function f such that λm 2 Var(f) ≥ e L D(f), (4.1) where m := m(q) satisﬁes d−1 cq k = 2 m(q) = 1 (4.2) d−k+1 exp cq k ≥ 3. (k−2) Note that m deﬁned here, up to logarithmic corrections, describe a length scale similar to ℓ of the previous section. Roughly speaking, this is the scale at which large structures that contain many empty sites could propagate and inﬂuence their neighborhood. 4.1. Bootstrap percolation. In order to deﬁne f we ﬁrst need to introduce the k- neighbor bootstrap percolation (see e.g. [24] and references therein). Fix V ⊆ Λ, and consider a set A ⊆ Λ. The k-neighbor bootstrap percolation in V starting at A is the deterministic growth process in discrete time, deﬁned as A = A ∩ V, A = A ∪ {x ∈ V : |{y ∈ A such that y ∼ x}| ≥ k} , t ∈ N. t+1 t t That is, at each step the set A is obtained by adding to the set A the sites that have t+1 t at least k neighbors already in A . The set ∪ A will be denoted by [A] and it forms t t≥0 t a subgraph of Λ whose connected components will be referred to as clusters. Given V V V x ∈ V we shall write C for either the cluster of [A] containing x if x ∈ [A] or for the set {x} otherwise. Given η ∈ Ω we shall deﬁne the bootstrap percolation process started from η as the above process with initial set A = A := {x ∈ Λ : η = 0} . η x 24 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI 4.2. Construction of the test function. We start with a few geometric deﬁnitions: Deﬁnition 4.1. Denote the box x + [−m, m] by B . Its inner boundary is denoted by ∂B . We say that an edge y ∼ z crosses ∂B , and write yz ∈ ∂B , if one of its endpoints x x x is in B and the other is not. Deﬁnition 4.2. Fix a conﬁguration η ∈ Ω and a site x ∈ Λ, and consider the cluster of x in [A ] . We deﬁne r (η) to be the maximal site in this cluster, according to the η x lexicographic order. We are now ready to deﬁne the function f. Let g : [0, 1] → R a positive smooth function supported in [0.1, 0.9] . Then f(η) = g r (η)/L η . (4.3) x x x∈Λ Remark 4.3. The above choice is inspired by the test function ϕ = g (x/L) η for x∈Λ the symmetric simple exclusion process, with g related to the lowest eigenfunction of the discrete Laplacian in Λ (see e.g. [9, Section 4.1]). The only crucial difference between f and ϕ is the choice of r (η) instead of x inside the slowly varying function g(r (η)/L) as a x x proxy for the effective position of the particle at x. Actually any other quantity depending only the cluster C (e.g. its center of mass) would work as well. Evaluating g at this λm 2 effective position is the cause of the prefactor e in front of the diffusive term L in (4.1). In fact, as proved below, the cluster C is inﬂuenced by an exchange of the KA dynamics −O(m) in the box B only if C ∩ ∂B 6= ∅. Since the latter event has probability e if the x x x constant c appearing in (4.2) is small enough, the sought prefactor emerges. We shall now bound separately the variance and Dirichlet form of f. In the sequel, c and λ will denote generic positive constants that may depend only on k, d, and g. 4.3. Bounding the variance. Proposition 4.4. For q small enough and L large enough, Var(f) ≥ c qL . Proof. Let H = (2m + 1)Z , and for ξ ∈ B let H = (ξ + H) ∩ Λ. Clearly H ∩ H = ∅ 0 ξ ξ ′ ′ ′ iff ξ 6= ξ and ∪ H = Λ. Note also that for any x, x ∈ H , x 6= x , B ∩ B = ∅. ξ∈B ξ ξ x x For ξ ∈ B denote by f (η) the part of the sum in equation (4.3) that corresponds to 0 ξ H : f (η) = g (r /L) η . ξ x x x∈H By the previous observation this is a sum of independent variables so that X X Var(f ) = Var g r (η) η = Var [(1 + O(m/L))g (x/L) η ] ξ x x x x∈H x∈H ξ ξ X X 2 2 g(x/L) pq (1 + O(m/L)) ≥ pq g(x/L) . x∈H x∈H ξ ξ 25 The notation O(·) stands for a random variable deterministically bounded by the ex- pression inside the parentheses times a constant. Above we used |r (η)| = O(m) to write g(r (η)/L) = g(x/L)(1 + O(m/L)), (4.4) recalling that g is smooth. Next, for ξ 6= ξ , X X Cov f , f ′ = Cov (g (r /L) η , g (r ′/L) η ′) ξ ξ x x x x x∈H x ∈H X X ′ ′ = 1 ′ Cov (g (r /L) η , g (r /L) η ) . x x x x kx−x k≤2m+1 x∈H x∈H ξ ′ Considering one of these terms, using equation (4.4) and Cov(η , η ) = 0, we ﬁnd that x x Cov (g (r /L) η , g (r ′/L) η ′) = O(m/L), x x x x yielding X X Cov f , f ′ = 1 ′ O (m/L) ≤ |H | (4m + 3) O(m/L). ξ ξ kx−x k≤2m+1 ξ x∈H x∈H Putting everything together, X X X Var(f) = Var f = Varf + Cov f , f ξ ξ ξ ξ ξ∈B ξ ξ6=ξ X X X 2 d+1 ≥ pq g(x/L) − |H | O m /L ξ x∈H ξ6=ξ 1 1 2d+1 d−1 d 2 = pq g (x/L) − O(m L ) ≥ pq L g(s) ds 2 4 for L large enough. 4.4. Bounding the Dirichlet form. In order to bound D(f), we will use [10, Lemma 5.1]. Plugging our choice of m for small enough c in their result yields the following lemma : Lemma 4.5. Consider the bootstrap percolation in the box B starting at A , where η 0 η is a conﬁguration distributed according to µ . Then the probability that the cluster of the 0 −λm origin in [A ] contains a site in ∂B is bounded from above by e . The same bound η 0 holds replacing B by the box [−m, m + 1] × [−m, m] (or any of its rotations). We will now make a few combinatorial observations. U U∪V Observation 1. Fix a conﬁguration η, and two sets U, V ⊆ Λ. Then [A ] ⊂ [A ] . η η Observation 2. Fix a conﬁguration η, two sets U ⊆ V ⊆ Λ, and a site x ∈ V \U. Assume V V \U that x ∈ [A ] , but x ∈/ [A ] . Then C ∩ U 6= ∅. η η Note that in [10] the parameter k is called ℓ, and that the length scale m of equation (4.2) corresponds (up to a constant) to m of [10]. − 26 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI Observation 3. Fix a conﬁguration η, a set V ⊆ Λ, and two sites y ∼ z ∈ V . Assume the constraint c is satisﬁed in V (i.e. , when ﬁxing all sites outside V to be occupied), and yz V V that η 6= η . Then both y and z are contained in [A ] . In particular, C = C . y z η y z Observation 4. Fix a conﬁguration η, a set V ⊆ Λ, and two sites y ∼ z ∈ V . Assume the V V yz constraint c is satisﬁed in V . Then [A ] = [A ] . yz η η Claim 4.6. Fix a conﬁguration η and an edge y ∼ z, such that c = 1 and η 6= η . yz y z B ∪B y z yz Assume that C ∩ ∂(B ∪ B ) = ∅. Then r (η) = r (η ). y y z y z B B Proof. Using observation 3 and the fact that y ∼ z we have that C = C for B ∈ y z {B , B , B ∪ B }. Moreover, using observation 4 these clusters are the same for η y z y z yz B and η . We will show that C is the same for all three boxes, which will imply the B B ∪B B B ∪B y y z y y z result. We start by showing that C = C . By observation 1 C ⊆ C . In y y y y B ∪B z y the other direction, let, by contradiction, w ∈ C \ [A ] . Then, setting V = y η B ∪B z y B ∪ B and U = (B ∪ B ) \ B , observation 2 implies that C ∩ U 6= ∅. Noticing z y z y y that U ⊂ ∂(B ∪ B ), this contradicts the assumption of the claim. We conclude that y z B ∪B B B ∪B z y y z y Bz C = C . Similarly one proves that C = C , and the result follows. y y y Claim 4.7. Fix x ∈ Λ and y ∼ z. Then: (1) If yz ∈ ∂B (so in particular x ∈/ {y, z}), 2 −λm 2 2 µ (c (∇ [g (r /L) η ]) ) ≤ e m /L . yz yz x x (2) If x ∈ {y, z}, −λm 2 2 µ c ∇ g r /L η + g r /L η ≤ e m /L . zy yz y y z z (3) Otherwise, c ∇ g r /L η = 0. yz yz x x Proof. Since ∇ (·) = 0 whenever η = η , we may assume throughout the proof of this xy y z claim that η 6= η , using freely observation 3 and Claim 4.6. y z For the ﬁrst part, we note that η does not change when exchanging the sites y and z, so the only contribution to ∇ [g (r /L) η ] comes from the change of r . Assume yz x x x Bx without loss of generality that y ∈ B and z ∈/ B . By observations 1 and 2, [A ] (and x x η B B x x therefore r ) cannot change when changing η , unless y ∈ [A ] ∪ [A yz] . Hence, x y η η B B yz x x by equation (4.4), Lemma 4.5 and deﬁning C to be C (η) when η = 0 and C (η ) x y x x when η = 0, 2 2 µ (c (∇ [g (r /L) η ]) ) = µ (c (∇ [g (r /L) η ]) 1 ) yz yz x x yz yz x x y∈Cx 2 2 −λm 2 2 ≤ O(m /L )µ (y ∈ C ) ≤ e m /L . In order to prove the second part, note ﬁrst that y, z ∈ B ∩ B so that observation y z By By yz 4 together with c (η) = 1 implies that C (η) = C (η ) and in particular r (η) = yz y y y yz yz yz r (η ). In the same manner r (η) = r (η ). Suppose now that r (η) = r (η ), so y z z y z yz also r (η) = r (η ). Then z y yz yz yz yz g (r (η)/L) η + g (r (η)/L) η = g (r (η )/L) η + g (r (η )/L) η . y y z z z y z y 27 Therefore, c 1 yz ∇ [g (r (η)/L) η + g (r (η)/L) η ] = 0. We are thus left yz yz y y z z {r (η)=r (η )} y z with estimating µ c 1 yz ∇ [g (r (η)/L) η + g (r (η)/L) η ] . xy yz y y z z {ry(η)6=rz(η )} Using (4.4) |∇ [g (r (η)/L) η + g (r (η)/L) η ]| = O(m/L). yz y y z z −λm Moreover, by Claim 4.6 and Lemma 4.5, µ c 1 yz ≤ e , and this con- xy {r (η)6=r (η )} y z cludes the proof. The third part is a direct consequence of Observation 4. We are now ready to bound from above the Dirichlet form D(f). Proposition 4.8. For any small enough c > 0 in (4.2) there exists λ > 0 such that −λm d−2 D(f) ≤ e L . Proof. First, note that, since g is supported in [0.1, 0.9], the term Var (f) in D(f) x∈∂Λ equals 0. Consider then one of the exchange terms c (∇ f) , and split the sum over yz yz x according to the different cases in Claim 4.7: 2 2 c ∇ f = c ∇ [g (r (η)/L) η ] yz yz yz yz x x x∈Λ = c ∇ [g (r (η)/L) η + g (r (η)/L) η ] + ∇ [g (r (η)/L) η ] yz yz y y z z yz x x x: yz∈∂B d−1 2 2 ≤ cm c (∇ [g (r (η)/L) η + g (r (η)/L) η ]) + (∇ [g (r (η)/L) η ]) , yz yz y y z z yz x x x: yz∈∂B where we have used the Cauchy-Schwarz inequality and the fact that the sum x: yz∈∂B d−1 d−1 contains 2 (2m + 1) terms corresponding to the (2m + 1) possible translations of the face crossing the edge, doubled by the reﬂection along it. By Claim 4.7, this inequality implies d−1 −λm 2 2 d−1 −λm 2 2 −λm 2 µ c (∇ f) ≤ cm e m /L + m e m /L ≤ e /L . yz yz In conclusion, " # X X 2 −λm d−2 D(f) = µ Var (f) + c (∇ f) ≤ e L . x yz yz z∼y x∈∂Λ Propositions 4.4 and 4.8 show that indeed that the relaxation time is greater than λm 2 e L , which by the choice of m coincides with the lower bound of Theorem 1. 28 F. MARTINELLI, A. SHAPIRA, AND C. TONINELLI 5. CONCLUDING REMARKS AND FURTHER QUESTIONS The general scheme of the proof has already been proven effective in the study of kinetically constrained spin models (and speciﬁcally in obtaining universality results [23]). It consists in analysing the microscopic dynamics up to some mesoscopic scale ℓ; and then understanding the long range dynamics, which depends on connectivity properties of a percolation process on the lattice of mesoscopic boxes. The long range dynamics depends very weakly on the details of the model. For example, we were able to restrict this dynamics to paths in two dimensions rather than d, since already in two dimensions percolation with large enough parameter is supercritical, and satisﬁes strong enough connectivity properties. We believe that applying these methods to other cooperative kinetically constrained lattice gases could yield new interesting results. In the context of the Kob-Andersen model, the techniques presented in this paper can be used in order to ﬁnd the diffusion coefﬁcient of a marked particle ([12]). We believe that they may also help understanding further properties of the this model, e.g., im- proving the bound of [7] on the loss of correlation for local functions, or understanding its hydrodynamic limit. See also [28, Chapter 6]. REFERENCES [1] Hans C. Andersen and Glenn H. Fredrickson, Kinetic Ising Model of the Glass Transition, Phys. Rev. Lett. 53 (1984), no. 13, 1244–1247. [2] A. Barrat, J. Kurchan, V. Loreto, and M. Sellitto, Edwards measures for powders and glasses, Phys. Rev. Lett. 85 (2001), 5034-7. [3] L. Bertini and C. Toninelli, Exclusion processes with degenerate rates: convergence to equilibrium and tagged particle, J.Stat.Phys. 117 (2004), 549-580. [4] O. Blondel and C. Toninelli, Kinetically constrained models: tagged particle diffusion, Ann. Inst. H. Poincar´e Probab. Statist. 54 (2018), no. 4, 2335-2348. [5] B. Bolloba´s, Modern Graph Theory, Graduate texts in mathematics, Springer, Heidelberg, 1998. [6] N. Cancrini, F. Martinelli, C. Roberto, and C. Toninelli, Facilitated spin models: recent and new re- sults, Methods of contemporary mathematical statistical physics, Lecture Notes in Math., vol. 1970, Springer, Berlin, 2009, pp. 307–340. [7] , Kinetically constrained spin models, Prob. Theory Rel. Fields 140 (2008), no. 3-4, 459–504. [8] , Kinetically Constrained Lattice Gases, Communications in Mathematical Physics 297 (2010), no. 2, 299–344. [9] Pietro Caputo, Thomas M. Liggett, and Thomas Richthammer, Proof of Aldous’ spectral gap conjecture, J. Amer. Math. Soc. 23 (2010), no. 3, 831–851. [10] R. Cerf and F. Manzo, The threshold regime of ﬁnite volume bootstrap percolation, Stochastic Process. Appl. 101 (2002), no. 1, 69–82. [11] Richard Durrett and Roberto H. Schonmann, Large deviations for the contact process and two dimen- sional percolation, Probability Theory and Related Fields 77 (1988), 583–603. [12] Anatole Ertul and Assaf Shapira, Work in progress. [13] S. Franz, R. Mulet, and G. Parisi, Kob-andersen model: A nonstandard mechanism for the glassy transition, Phys.Rev.E 65 (2002), 021506. [14] J. P. Garrahan, P. Sollich, and C. Toninelli, Kinetically constrained models, in “Dynamical hetero- geneities in glasses, colloids, and granular media” (Eds.: L. Berthier, G. Biroli, J.-P. Bouchaud, L. Cipelletti and W. van Saarloos), Oxford Univ. Press (2011). [15] J.P. Garrahan, P. Sollich, and C. Toninelli, Kinetically constrained models, in ”Dynamical hetero- geneities in glasses, colloids, and granular media”, Oxford Univ. Press, Eds.: L. Berthier, G. Biroli, J-P Bouchaud, L. Cipelletti and W. van Saarloos (2011). 29 [16] P. Goncalves, C. Landim, and C. Toninelli, Hydrodynamic limit for a particle system with degenerate rates, Ann. Inst. Henri Poincar´e Probab. Stat. 45 (2009), no. 4, 887–909. [17] W. Kob and H. C. Andersen, Kinetic lattice-gas model of cage effects in high-density liquids and a test of mode-coupling theory of the ideal-glass transition, Physical Review E 48 (1993), 4364–4377. [18] J. Kurchan, L. Peliti, and M. Sellitto, Aging in lattice-gas models with constrained dynamics, Euro- physics Lett. 39 (1997), 365–370. [19] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times, American Mathematical Society, 2008. [20] T.M. Liggett, Interacting particle systems, Springer-Verlag, New York, 1985. [21] E. Marinari and E. Pitard, Spatial correlations in the relaxation of the Kob-Andersen model, Euro- physics Lett. 69 (2005), 235-241. [22] Fabio Martinelli and Cristina Toninelli, Towards a universality picture for the relaxation to equilibrium of kinetically constrained models, Ann. Prob. 47 (2019), no. 1, 324–361. [23] Fabio Martinelli, R. Morris, and Cristina Toninelli, Universality Results for Kinetically Constrained Spin Models in Two Dimensions, Commun. Math. Phys. (2018), https://doi.org/10.1007/s00220- 018-3280-z. [24] Robert Morris, Bootstrap percolation, and other automata, Europ. J. Combin. 66 (2017), 250–263. [25] Y Nagahata, Lower bound estimate of the spectral gap for simple exclusion process with degenerate rates, Electron. J. Probab. 17 (2012), paper n.92, 19 pages. [26] F. Ritort and P. Sollich, Glassy dynamics of kinetically constrained models, Advances in Physics 52 (2003), 219–342. [27] Laurent Saloff-Coste, Lectures on ﬁnite Markov chains (Pierre Bernard, ed.), Lecture Notes in Mathe- matics, vol. 1665, Springer Berlin Heidelberg, 1997. [28] Assaf Shapira, Bootstrap percolation and kinetically constrained models in homogenous and random environment, Ph.D thesis, Universit´e Paris Diderot (2019), available at https://assafshap.github.io/thesis.pdf. [29] P. Sollich and M.R. Evans, Glassy time-scale divergence and anomalous coarsening in a kinetically constrained spin chain, Phys. Rev. Lett 83 (1999), 3238–3241. [30] C. Toninelli, G. Biroli, and D.S. Fisher, Cooperative Behavior of Kinetically Constrained Lattice Gas Models of Glassy Dynamics, J.Stat.Phys. 120 (2005), no. 1–2, 167-238. E-mail address: martin@mat.uniroma3.it DIPARTIMENTO DI MATEMATICA E FISICA, UNIVERSIT` A ROMA TRE, LARGO S.L. MURIALDO 00146, ROMA, ITALY E-mail address: assafshap@gmail.com LPSM UMR 8001, UNIVERSIT´ E PARIS DIDEROT, CNRS, SORBONNE PARIS CIT´ E, 75013 PARIS, FRANCE E-mail address: toninelli@ceremade.dauphine.fr CEREMADE UMR 7534, UNIVERSITE PARIS-DAUPHINE, CNRS, PSL RESEARCH UNIVERSITY, PLACE DU MARECHAL DE LATTRE DE TASSIGNY, 75775 PARIS CEDEX 16, FRANCE

Mathematics – arXiv (Cornell University)

**Published: ** Apr 24, 2019

Loading...

You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!

Read and print from thousands of top scholarly journals.

System error. Please try again!

Already have an account? Log in

Bookmark this article. You can see your Bookmarks on your DeepDyve Library.

To save an article, **log in** first, or **sign up** for a DeepDyve account if you don’t already have one.

Copy and paste the desired citation format or use the link below to download a file formatted for EndNote

Access the full text.

Sign up today, get DeepDyve free for 14 days.

All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.