Bootstrap percolation on rhombus tilings
S Esnay V Lutfalla G Theyssier


Fundamental properties of linear factor models


    Peter M. Kraus
    3 September 2024
================================================



§ ABSTRACT 
  2-boostrap percolation on a graph is a diffusion process where a vertex gets infected whenever it has at least 2 infected neighbours, and then stays infected forever.
  It has been much studied on the infinite grid for random Bernoulli initial configurations, starting from the seminal result of van Enter that establishes that the entire grid gets almost surely entirely infected for any non-trivial initial probability of infection.

  In this paper, we generalize this result to any adjacency graph of any rhombus tiling of the plane, including aperiodic ones like Penrose tilings. We actually show almost sure infection of the entire graph for a larger class of measure than non-trivial Bernoulli ones.

  Our proof strategy combines a geometry toolkit for infected clusters based on chain-convexity, and uniform probabilistic bounds on particular geometric patterns that play the role of 0-1 laws or ergodicity, which are not available in our settings due to the lack of symmetry of the graph considered.





§ INTRODUCTION



Bootstrap percolation was first introduced by <cit.> as a simplified model of a magnetic system progressively loosing its magnetic order[Due to initial non-magnetic impurities and competition between exchange interactions (which tends to align atomic spins) and crystal fields interactions (which tends to force atoms into a singlet state, and thereby suppressing magnetic moments).].
When abstracted away from this physical modeling, it can be seen as a simple growing or diffusion process on a graph: at each time step, any vertex with m or more infected neighbours becomes infected, and infected vertices remain infected forever.
As in classical percolation theory, this system is usually studied on random initial condition (each vertex is initially infected with some probability p), and the main question is to determine whether the entire graph will be infected almost surely (depending on p).

This process has been first studied on the bi-dimensional grid where the case m=2 is the most interesting one. 
<cit.> proved in that case that whenever p>0, the entire graph is infected almost surely. 
Then <cit.> and later <cit.> obtained sharp thresholds on p for finite grids as a function of their size.
Still on the grid (in dimension two or higher), these seminal results were considerably generalized to a large class of monotone cellular automata called U-bootstrap and introduced in <cit.> (see <cit.> for a detailed survey of this family and <cit.> for a taste of the most recent results).

On the other hand, bootstrap percolation was studied on many different graphs: finite ones like in <cit.>, tilings by regular polygons <cit.> where critical probabilities are trivial (0 or 1) like on the infinite grid, or hyperbolic lattices <cit.> or regular trees and Cayley graphs of non-amenable groups <cit.> where non-trivial critical probabilities were established.
A common aspect to these works (and to most of the literature to our knowledge) is that the graphs considered are highly symmetric which gives, on one hand, powerful probabilistic tools for tackling the problem (0-1-laws, ergodicity, etc), and, on the other hand, a nicer and more uniform geometry to infected clusters.

There is a general observation (or belief) in statistical mechanics that many features of studied systems only depend on a few parameters and should be independent of the details of the system.
This is often referred to as universality, but there is no rigorous mathematical definition of the concept to our knowledge. More modestly and back to the precise context of bootstrap percolation, one could ask how robust is the seminal result of <cit.> when modifying the underlying graph. First, as mentioned above, there is a dramatic change of behavior when going from the grid to trees, Cayley graphs of non-amenable groups or hyperbolic graphs (non-critical probabilities arise).
But what is special about the regular grid ^2 among planar graphs that are quasi-isometric to it?
what is the importance of symmetry (in particular translation invariance) that allows to make concise proofs?


In this paper, we consider boostrap percolation on any adjacency graph of any rhombus tiling  of the plane with finitely many tile types up to translation, including the regular grid but also highly non-symmetric ones like Penrose tilings.
Our main result is a generalization of the seminal result of <cit.> to this entire class of graphs, precisely: on the adjacency graph of any rhombus tiling, for any non-zero initial probability of infection, the entire graph will get infected almost surely.

Classical percolation was already studied on Penrose tilings in <cit.>, where the lack of translation invariance and symmetry is tackled by introducing an ergodic measure that averages over all possible Penrose tilings. Our approach is different and gives results for bootstrap percolation on any single tiling without averaging. We generalize Enter's argument to this setting by combining a geometrical analysis of blocked infected cluster based on chain-convexity (which are simply rectangles in the case of the grid) and uniform probability upper bounds on blocked cluster events that bypass the lack of translation invariance (whereas thanks to ergodicity in the case of the grid, it is enough to bound the probability of a blocked infected cluster containing the origin).



  
*Contents of the paper. In section <ref>, we introduce bootstrap percolation cellular automata on any graph, the main problem, and some basic probabilistic notions and ingredients to be used later. In section <ref>, we introduce rhombus tiling and some of their geometric features. The two previous objects introduced separately meet in section <ref>, where we establish our main result in two steps: first, by a detailed analysis of infection clusters based on chain-convexity (sub-section <ref>), and then, by a probabilistic argument applied to specific geometric objects previously identified (sub-section <ref>).
In the appendices we present two examples that limit the generalization of our result to other graphs and percolation processes.
In Appendix <ref> we show that 2-neighbour percolation does not have a critical threshold (or 0-1) behaviour on the adjacency graphs of arbitrary quadrilater tilings.
In Appendix <ref> we show that arbitrary percolation processes (here a variant of oriented bootstrap percolation) do not have a critical threshold behaviour on the adjacency graphs of arbitrary rhombus tilings.



§ BOOTSTRAP CELLULAR AUTOMATON AND PROBABILITY MEASURES



In this section, we introduce the bootstrap cellular automaton on an arbitrary abstract graph and present basic facts around probability measures (to be used later in Section <ref>).

Given a graph G=(,E), a configuration is a map giving a value 0 or 1 to each vertex.
We denote by = {0,1}^ the set of configurations.
If c∈ and v∈, we use notations c(v) and c_v interchangeably.
The set X can be endowed with the pro-discrete topology (product of the discrete topology over {0,1}) which is generated by the collection of cylinder sets for D⊆ a finite domain of  and P:D→{0,1} a partial configuration of domain D:

    [P] = {c∈|∀ t∈ D, c(t)=P(t)}.

X endowed with this topology is compact.
We will often use the notation shortcut q^D for q∈{0,1} and D⊆ to denote the constant partial configuration equal to q on domain D. 
Therefore [q^D] denotes the set of configurations in state q on domain D.

In this paper, we are interested in a dynamical process acting on configurations which is a particular cellular automaton often called bootstrap percolation <cit.>.

The m-neighbour contamination or m-bootstrap cellular automaton F:→ for some integer m is defined as follows:

    F(c)_v =
      
        1     if c_v=1 or |{v' | (v',v)∈ E and c_v'=1}|≥ m,
    
        0     else,

for any configuration c∈ X and any vertex v∈.

This cellular automaton is both freezing and monotone (see <cit.>), which means that:


  * F(c)_v≥ c_v for any c∈ and v∈ (freezing),

  * F(c')_v≥ F(c)_v for all v∈ whenever c'_v≥ c_v for all v∈ (monotone).


The freezing property lets us see F as a growing process: starting from any initial configuration seen as a set of selected vertices of value 1, F can only make this set increase with time.
In particular, for any c∈ and any v∈, the sequence (F^n(c)_v)_n is ultimately constant of limit value c^∞_v. Equivalently, the sequence of configurations (F^n(c))_n always converges and its limit is precisely c^∞.

We will focus on the set  of initial configurations that invade the entire graph during this growing process, formally:

    = {x∈|∀ v∈, ∃ n∈, F^n(c)_v = 1}.


Clearly not all configurations lie in .
We want to understand how big  is.
Topologically, it is a G_δ set (intersection over v∈ of sets ∪_n{c | F^n(c)_v=1} which are open), but following motivations from statistical physics and percolation theory, we will study  through probability measures.

A Borel probability measure is uniquely determined by its value on cylinders (by Carathéodory-Fréchet extension theorem, see <cit.>).
We mainly consider Bernoulli measures μ_p which are product measures determined by a parameter p∈[0,1] giving the “probability of having a 1 at one vertex”, as follows:

    μ_p([P]) = ∏_v∈ D, P(v)=1 p   ×∏_v∈ D, P(v)=0(1-p).


The monotony property of F mentioned above implies that the measure of I under Bernoulli measures can only increase with p: μ_p(I)≤μ_p'(I) whenever p≤ p' (this can be shown by a straightforward coupling argument).
Since μ_0()=0 and μ_1()=1, there are two critical values of the parameter p to consider: = sup{p |μ_p()=0} and = inf{p |μ_p()=1} which verify ≤.


  In many proofs, an event is shown to be of probability either 0 or 1 for a given measure μ using 0-1 laws.
  
  One of them is the Kolmogorov 0-1-law; but it applies to tail events, which  is not: it might depend on a finite portion of the configuration.
  
  Another of them is that, if the graph G has enough symmetry, Bernoulli measures follow a 0-1 law on Borel sets of configurations that preserve these symmetries.
  
  More precisely, denoting Γ the group of automorphisms of graph G, if the action of Γ on G has an infinite orbit (intuitively meaning that infinitely many vertices of G are indistinguishable) and if G is locally finite, then, for any Bernoulli measure μ and any set X of configurations which is invariant under Γ (i.e., c∈ X and ϕ∈Γ implies c∘ϕ^-1∈ X), we have μ(X)∈{0,1} (see <cit.>).
  
  Whatever the graph G, the set  is always invariant under Γ, simply because F(c)∘ϕ^-1=F(c∘ϕ^-1) for any configuration c and c∈ I is determined by a uniform constraint on all vertices: ∀ v∈, c^∞(v)=1.
  Consequently, for this 0-1 law to hold on , the only requirement is for the graph to have enough symmetry. It is the case in particular for Cayley graphs of infinite groups (typically ^2), and is often expressed as the fact that the action of translation with Bernoulli measure is ergodic <cit.>.


Following remark <ref>, in the case of a graph with enough symmetry, μ_p(I)∈{0,1} for all p so that =.
We will however consider graphs that have few or no symmetry and there is a priori no reason to expect this 0-1 law to hold (see counter-example in appendix <ref> and Proposition <ref> therein).

Furthermore, this 0-1 law uses Bernoulli measures: percolation theory often focuses on these measures to study critical values of parameter p.
Here, we will actually consider a larger class of measures in Section <ref> that are not necessarily product measures but are sufficiently well-behaved.

Our goal here is not to look for abstract generality, but rather to make explicit and clear the requirements we use in the probabilistic arguments of our main result (Section <ref>).
There are three such requirements that we detail below: bounded correlations (Markov property), non-vanishing probability of patches of 1 of any fixed size, and positive correlation of upward-closed sets. 

Fix some integer k∈. We say that a measure μ is k-Markov if, for any finite D⊆ V and any set X⊆ V which is at distance at least k from D in graph G and any patterns u:D→{0,1} and P:X→{0,1}, the following holds:

    μ([u]∩ [P]) = μ([u])μ([P]).


In addition, we say a measure is non-vanishing if for all r there is some constant α>0 such that for all v∈ V, μ([1^B(v,r)])≥α where B(v,r) is the ball of radius r centered in v in graph G.
Finally, a set of configurations X⊆ is upward-closed if, whenever x∈ X  and x_v≤ y_v for all v∈ V, then y∈ X.

A measure μ is called  (Markov-Non Vanishing-Positively Correlated) if it is k-Markov for some k, non-vanishing, and any pair X,Y of upward-closed Borel sets are positively correlated, i.e. μ(X∩ Y)≥μ(X)μ(Y).


  Any non-trivial Bernoulli measure on a bounded degree graph is .


  Any such measure is clearly 1-Markov. It is non-vanishing on any graph of bounded degree because the cardinal of balls of radius r is uniformly bounded.
  Finally, Bernoulli measures are positively correlated on upward-closed events, a fundamental fact often referred to as Harris inequality (see <cit.> for a complete proof).




One of the basic property of  measures is that imposing a large patch of 0 at a fixed position has a decreasing probability with the patch size that can be uniformly exponentially upper-bounded.


  If G is of bounded degree and μ a  measure, then there is some β with 0<β<1 such that, for any D⊆ V with |D|=n it holds that μ([0^D])≤β^n.


  Let k be such that μ is k-Markov, and α>0 be such that μ([1^{v}])≥α for all v (α exists because μ is non-vanishing).
  If Δ is a bound on the degree of G then any ball of radius k in G has cardinality at most Δ^k.
  Therefore, one can choose at least N=⌊n/Δ^k⌋ vertices v_1,…, v_N in D which are pairwise separated by distance at least k.
  By the k-Markov property we get
  
    μ([0^D])≤∏_1≤ i≤ Nμ([0^{v_i}])≤ (1-α)^N.

  Taking β = (1-α)^1/2Δ^k proves the lemma.




§ RHOMBUS TILINGS


We call tiling, denoted by , a countable set of tiles that covers the euclidean plane ℝ^2without overlap. That is, = {t_i, i ∈} is a tiling when ⋃_i∈ t_i = ^2 and for any i,j∈, t_i∩t_j = ∅.
In all that follow, we consider the case of rhombus tilings, where there are finitely many tiles up to translation, all the tiles are rhombuses and the tiling is edge-to-edge, i.e., any two tiles either intersect on a single common vertex, on a full common edge, or not at all.
Throughout the article we use the famous example of Penrose rhombus tilings <cit.>, see Fig. <ref>.






In the case of edge-to-edge tilings, the condition that there are finitely many tiles up to translation is equivalent to finite local complexity (FLC) <cit.> that is: for any given size there are finitely many patches of that size.

We say that two tiles t and t' are adjacent, denoted by t t', when they share a full edge, that is, when there exists an edge e such that t ∩ t' = e.
This notion, also called edge-adjacency, is the natural notion of adjacency on edge-to-edge tilings.
However, we also define a weaker notion of vertex-adjacency.
We say that two tiles t and t' are vertex-adjacent, denoted by t t',  when they are distinct and share at least one vertex, i.e. t ∩ t' ≠∅ and t ≠ t'.

Given a tiling  and a tile t∈, we define the neighbourhood of t, denoted by t, as the set of tiles which are adjacent to t, i.e., t:= { t' ∈| t  t'}.
We also define the weaker vertex-neighbourhood of t, t:= {t' ∈| t  t'}.
We define similar notions for a set of tiles S, that is, S:= { t' ∈∖S|∃ t ∈ S, t  t'} and S:= { t' ∈∖S|∃ t ∈ S, t  t'}. They are respectively the tiles adjacent and vertex-adjacent to the set S.
Note that all these notions are not neighbourhoods in the topological sense, notably since they do not contain the original set. However, this denomination, which is ultimately about adjacent tiles, is widely used and understood in tilings theory.

We call patch  a set of adjacent tiles in a tiling. We also sometimes consider vertex-patches, which are sets of vertex-adjacent tiles.
We consider only finite patches unless specified otherwise.



The key structure in rhombus tilings are the chains which generalize the rows and columns of the square grid.


  Given a rhombus tiling .

  Given an edge direction e⃗, we say that two tiles t and t' are e⃗-adjacent, denoted by t e⃗∼ t',  when they share an edge of direction e⃗.

  Given an edge direction e⃗ and a normal vector n⃗ (orthogonal to e⃗), we say that a tile t' is e⃗-adjacent to t in direction n⃗ when t e⃗∼ t' and ⟨t⃗t⃗'⃗ | n⃗⟩ > 0 where t⃗t⃗'⃗ is the vector from the barycenter of t to the barycenter of t' and ⟨ | ⟩ denotes the scalar product.

  We call chain  of edge direction e⃗ a bi-infinite patch = (t_i)_i∈ such that there exists n⃗ orthogonal to e⃗ such that for any i, t_i+1 is e⃗-adjacent to t_i in direction n⃗.
  

  We call half-chain ^+ of edge direction e⃗, orientation n⃗ and  starting tile t the infinite patch ^+ = (t_i)_i∈ such that t_0 = t and for any i, t_i+1 is e⃗-adjacent to t_i in direction n⃗.

  We call chain segment a finite connected subset of a chain. For a chain  and i < j, we write _i^j to denote the subset {t_i, …, t_j}.



We denote ≡' when two chains are identical up to shift of index and/or multiplication of one's indices by -1.






  Given a rhombus tiling  and two chains  of direction e⃗ and ' of direction e⃗'⃗.
  The following hold:
  
  
  * if ≢' then  and ' intersect at most once;
  
  * if ≢' and ∩' ≠∅ then the intersection tile t has edge directions e⃗ and e⃗'⃗
  
  * if e⃗ = ±e⃗'⃗ then either ≡' or ∩' = ∅
  


Note however that, in an arbitrary rhombus tiling, non-intersecting chains might have different edge directions. 


	
  Let  be a rhombus tiling with finitely many edge directions.
  There exists a constant θ>0 such that any chain  is θ-uniformly monotonous, that is, if =(_i)_i∈ has direction e⃗, there exists a unit normal vector n⃗ orthogonal to e⃗ such that for any i∈, ⟨t⃗_⃗i⃗t⃗_⃗i⃗+⃗1⃗ | n⃗⟩≥θ where t⃗_⃗i⃗t⃗_⃗i⃗+⃗1⃗ is the vector from the barycenter of t_i to the barycenter of t_i+1.



  Let  be a rhombus tiling with d edge directions {e⃗_⃗0⃗, …e⃗_⃗d⃗-⃗1⃗}.
  Denote e⃗^ the unit vector orthogonal to e⃗ in the positive orientation.

  Let θ := min_0≤ i,j < d, i≠ j |⟨e⃗_⃗i⃗ | e⃗_⃗j⃗^⟩|.

  Any chain ⊂ is θ-uniformly monotonous.
  Indeed, let  be a chain of edge direction e⃗.
  Let t and t' be two consecutive tiles in .
  There exists two directions e⃗_⃗i⃗ and e⃗_⃗j⃗ (possibly the same) such that t has edge directions e⃗ and e⃗_⃗i⃗ and t' has edge directions e⃗_⃗j⃗ and e⃗.
  Without loss of generality (changing the choice of orientations of the directions), assume ⟨e⃗_⃗i⃗|e⃗^⟩ >0 and ⟨e⃗_⃗j⃗ | e⃗^⟩ > 0.
  Since t and t' are parallelograms and adjacent along an e⃗ edge, this means that t⃗t⃗'⃗ = 12(e⃗_⃗i⃗ + e⃗_⃗j⃗).
  So ⟨t⃗t⃗'⃗ | e⃗^⟩ = 12(⟨e⃗_⃗i⃗|e⃗^⟩  + ⟨e⃗_⃗j⃗|e⃗^⟩ )≥θ.   








  The keen reader might have already noticed that the combinatorial structure of chains only uses the fact that rhombuses have two pairs of opposite parallel edges, that is, they are parallelograms.
  However for simplicity of redaction we chose to only mention rhombus tilings as any edge-to-edge parallelogram tiling is combinatorially equivalent to an edge-to-edge rhombus tiling, meaning they have the same adjacencies.
  Indeed the transformation consisting in rescaling all edge directions so they have the same length transforms an edge-to-edge parallelogram tiling to a combinatorially equivalent edge-to-edge rhombus tiling.
  Note however that, by transforming a tileset in this manner we might allow more tilings as collinear edge directions merge in this process.











§ CRITICAL PROBABILITY FOR 2-BOOTSTRAP PERCOLATION ON RHOMBUS TILINGS





The 1-bootstrap dynamics is not interesting on connected graphs ( contains all configurations except one). Moreover, on rhombus tilings, the 3-bootstrap dynamics always admits finite obstacles and therefore has a trivial critical probability (p_c^0=p_c^1=1): indeed, considering any vertex of the tiling and assuming that all tiles sharing this vertex are in state 0 (not infected), then they will stay in state 0 forever, because each of them has at most 2 neighbours in state 1 at any moment.

In this section we investigate 2-neighbour contamination on rhombus tilings, and we prove almost sure invasion on any rhombus tiling with finitely many edge directions for any  measure μ.
In particular, it implies almost sure invasion for any non-trivial Bernoulli measure so that the critical percolation threshold of 2-neighbour contamination on any rhombus tiling with finitely many edge directions  is p_c^0=p_c^1=0.

Formally, to fit the formalism of Section <ref>, we can consider the adjacency graph of the rhombus tilings.
The adjacency graph, or dual graph, G_ of the rhombus tiling  is G_ = (, E_) where (t,t')∈ E_⇔ t t'.
However, for simplicity, we identify  and G_ in this section.

In Section <ref>, we study the geometry and combinatorics of clusters (stable contaminated patterns) and prove that any finite cluster is enclosed in a “wall” which is a polygon of a bounded number of chain segments, generalising the fact that in ℤ^2 clusters are enclosed in a rectangle that is in particular a polygon of 4 chain segments.
We also prove that infinite clusters are bounded by some chain path including an infinite half-chain.

In Section <ref> we use the geometrical and combinatorial results on clusters to prove that invasion is almost sure for any  measure.
The key idea is counting the possible finite “walls” of length n around a tile and bounding their number by a polynomial in n.
From this we deduce for any  measure μ :

  
  * a uniform bound λ<1 on the measure of the event E_t of a tile being enclosed in a finite “wall”, and
  
  * a uniform approximation of E_t by the tail event E_t,≥ n of the tile t being enclosed in a finite “wall” of length more than n.

Remarking that the head events E_t,≤ n of being enclosed in a wall of length less than n are independent for sufficiently far away tiles for Markov measures, we obtain almost independence of far away events E_t from which we conclude almost sure invasion for any  measure.



 §.§ Geometrical and combinatorial elements


The first observation that we can make is that a chain of 0s can stop a contaminated cluster, see Fig <ref>. Actually we prove that chains of 0s are the only possible “walls” for 2-neighbour contamination.
To formalize this we introduce the notion of chain-convexity.





  A connected set of tiles S⊂ is called chain-convex when for any chain of tiles =(_i)_i∈ the following hold:
  
  
  * {j ∈|_j ∈ S} is an interval of ;
  
  * if there exist i< j such that _i and _j are vertex-neighbours of S (that is {_i, _j}⊂S) then either _i+1^j-1⊂S and no tile of  is in S, or S∩ = {_i, _j} and the tiles of  that belong to S are exactly _i+1^j-1.
  


Note that a chain convex set of tiles, as it is connected and contains no hole due to item 1 of the definition, is simply connected.


	If a tile _i from a chain  is vertex-adjacent to a set S, then among _i+1 and _i-1, one of them is either vertex-adjacent to S too, or in S. Indeed, _i+1 shares half the vertices of _i with it, and _i-1 the other half; consequently one of them also shares a vertex with a tile of S, unless it is itself a tile of S.



  This definition states that if  is a chain and S is chain-convex, we have the following possibilities for the adjacency of  and S:
  
  
  *  has no element that is vertex-adjacent to S (this also holds if ⊂ S);
  
  *  has exactly one element χ_i that is vertex-adjacent to S; then by the above remark either {χ_i+1, χ_i+2, …} or {χ_i-1, χ_i-2, …} is in S;
  
  *  has exactly two elements _i and _j that are vertex-adjacent to S (and in particular no other element can be adjacent to S); then _i and _j are adjacent to S and the intersection with S is exactly the (possibly empty) set {_i+1, …, _j-1};
  
  *  has at least three elements that are vertex-adjacent to S (and notably not in S), and a finite number of them; then let us take _i and _j be the ones with smallest and largest indices. We cannot have the second case of point 2 of the definition above, therefore  does not intersect S, all elements in {_i+1, …, _j-1} neighbour S, and no element of  outside of _i^j is adjacent or vertex-adjacent to S.
  
  *  has infinitely many elements that are vertex-adjacent to S. Then similarly  does not intersect S, and either has a half-chain adjacent to S, or is adjacent to S in its entirety.
  


With the following two results, we prove that any vertex-connected set of tiles that is stable for 2-neighbour contamination is chain convex, as we would want it to be. We start by a more technical lemma on vertex-connected stable sets of tiles.



  Let S be a  vertex-connected set of tiles S⊂ that is stable for 2-neighbour contamination.
  Let ∈ be a chain of rhombuses of edge direction  such that there exist i<j ∈ with _i, _j ∈S.
  Denote v_i (resp. v_j) a vertex common to _i and S (resp. common to _j and S).

  If no tile of _i+1^j-1 is in S, and if v_i and v_j are in the same half-space of ∖,
  (that is, v_i and v_j are connected in S∩ (∖), as in Fig. <ref>),
  then the edge path _ from v_i to v_j along the boundary of  is also in the boundary of S.


Note that in the following proofs, ∖ and S ∩ (∖) are understood as sets of tiles.


  Let S be a vertex-connected set of tiles S⊂ that is stable for 2-neighbour contamination.
  Let i<j ∈ and =(_i)_i∈ a chain of rhombuses of edge direction  satisfying the condition above.
  Notably, _i+1^j-1 has no tile in S; and there are vertices v_i and v_j vertices of _i∩ S and _j ∩ S which are in the same half-space of ∖, and connected in S∩ (∖) as depicted in Fig. <ref>.
  
  We prove that all the rhombuses _k∈_i+1^j-1 are adjacent to S through a non- edge.
  More precisely, the edge path _ from v_i to v_j along the boundary of  (it exists as v_i and v_j are in the same half-space) is also in the boundary of S.

  
  
  Denote _S a path from v_j to v_i along the boundary of S such that S does not intersect the domain delimited by _·_S, where · is the path concatenation. To obtain such a path, one can first take an arbitrary path p_0 along the boundary of S connecting v_j to v_i (v_j and v_i lie on the boundary of S by hypothesis, since _i, _j ∈S). If the (finite) domain D_0 delimited by _· p_0 doesn't intersect S we are done, otherwise there must be a tile t∈ S∩ D_0 with a vertex on p_0. Considering the edge-connected component of S∩ D_0 containing t, we can define a new path p_1 along the boundary of S still connecting v_j to v_i but such that the domain D_1 delimited by _· p_1 is included in D_0 but does not contain t.
  
  Iterating this process a finite number of times (since S ∩ D_0 is finite), we obtain the desired path _S.

  First, remark that if _S is trivial, that is if v_i=v_j, then by uniform monotonicity of  in direction ^ (Lemma <ref>), j=i+1 and so the conclusion holds vacuously with _i+1^j-1 = ∅.

  Now we assume that _S is non trivial, as depicted in Fig. <ref>.
  Assume for contradiction that the finite patch of tiles D defined as the interior of the cycle = _·_S is non empty.
  We now construct a subset D'⊊ D that satisfies the same hypothesis and has to be non-empty. We consequently reach a contradiction by iterating this construction which builds a strictly decreasing sequence of non-empty finite sets of tiles.

  As D is non-empty and delimited by _S, there exists a tile t∈ D∩S. As S is stable for 2-neighbour contamination, S touches exactly one edge of t. So t has another edge direction e⃗_⃗t⃗ so both e⃗_⃗t⃗-edges of t are not in _S. Denote ' the chain of rhombuses of edge direction e_t passing through '_0:=t.
  As  is a closed curve containing t, and ' is uniformly monotonous in direction e_t^, ' crosses  at least twice. As chains can cross at most once, the _ part of  cannot be crossed twice by ', and so ' crosses _S at least once.
  Therefore there exists t':='_k such that '_0^k⊂ D and '_k+1∈ S.
  In particular, '_k is adjacent to S through an e_t edge.
  Denote D' the subset of D delimited by the subpath '_S between t and t' along the boundary of S and the path _' between t and t' on the boundary of ', as depicted in Fig. <ref>.
  D'⊊ D and D'≠∅ as otherwise t' would be adjacent to S through both a e_t edge and a non-e_t edge, contradicting the stability of S.
  Additionnally, the chain ' from t to t' satisfies the same hypothesis as the chain  from _i to _j. 
  So we can repeat this decomposition process to reach a contradiction.

  

  Therefore _S=_ and all the tiles along the chain  from v_i to v_j are adjacent to S through a non- edge.



A direct consequence of that lemma is that if a chain  (of direction ) touches a connected set S of tiles that is stable for 2-neigbour contamination through two vertices v_i ∈_i and v_j ∈_j lying in two different half-spaces of ∖, then the whole portion of chain _i+1^j-1 is in S.

This follows from the fact that v_i and v_j are connected in S by some edge path , which crosses  by Jordan's theorem.

Denote v_i_1,…, v_i_k the vertices of intersection of  with , including v_i and v_j, named from the smallest index i_1 to the biggest index i_k of tiles in the chain  that contain these vertices (up to using ' if a given tile has several vertices involved in the process). Applying Lemma <ref> on the elementary intervals between consecutive intersection points, we obtain that all tiles of _i_1+1^i_k-1 are adjacent to S through a non- edge.

Additionally, if  crosses , then S also contains some tile _k'∈, with i_1 ≤ k' ≤ i_k. Then _k'+1 (or _k'-1 if k' = i_k) is adjacent to S both through _k' and a non- edge. Hence _k'+1∈ S (or _k'-1) by stability of S for 2-neighbour contamination. With a finite number of steps, we deduce that the entire _i_1+1^i_k-1 chain portion is in S. Notably, _i+1^j-1 is in S.








  Any vertex-connected set of tiles S⊂ that is stable for 2-neighbour contamination is chain convex.



  Let S⊂ be a vertex-connected set of tiles that is stable for 2-neighbour contamination.


  We prove, using Lemma <ref>, that S is chain-convex, by checking all the items of that definition.
  Let  be a chain of rhombuses in .

  We prove that {j ∈, _j ∈ S} is an interval of .
  Let _j∈ S and _j+k∈ S.
  If _j and _j+k are not connected in S∩(∖), then as remarked in Remark <ref>, we have _j+1^j+k-1⊂ S.
  Otherwise, denote  the edge path from a vertex v_j of _j to a vertex v_j+k of _j+k in the same half-space such that v_j and v_j+k are connected in S∩ (∖).
  For contradiction, assume that _j+1^j+k-1 is not entirely in S. This means it contains a sub-interval that is entirely not in S. Up to renaming, we keep the notations j and j+k for that sub-interval, taken as big as possible (so that we still have _j and _j+k in S).
  By Lemma <ref>, if _j+1^j+k-1 does not intersect S then  is in the boundary of S. Moreover, _j+1∉ S. And yet, _j+1 has two edge neighbours in S: its neighbour on the other side of the edge path , and _j. This contradicts the stability of S for 2-neighbour contamination.
  Consequently, _j+1^j+k-1 is entirely in S and so {j ∈, _j ∈ S} is an interval of .
  

  We now prove the second chain-convexity condition.
  Let i<j such that _i and _j are in S (not in S).
  Denote v_i (resp. v_j) the vertex of _i (resp. _j) the vertex touching S.
  As explained in Remark <ref>, if v_i and v_j are not in the same half-space or not connected in S∩ (∖) then _i+1^j-1 is included in S.
  We now assume that v_i and v_j are in the same half-space and connected in S ∩(∖).
  Denote  the edge path from v_i to v_j along the boundary of _i^j.
  Up to decomposing _i^j in smaller intervals whose endpoints are not in S, we assume that _i+1^j-1 either is entirely in S or has no tile in common with S, while _i, _j ∉ S.
  
  In the first case we have _i+1^j-1⊂∩ S and _i, _j ∉ S. By the fact we proved above that {j ∈, _j ∈ S} is an interval of , we obtain that S∩ = _i+1^j-1. Additionally, the only elements of  in S are _i and _j. Indeed, if it weren't the case, then there exists k (assume by symmetry k>j) such that _k∈S, and then by applying Lemma <ref> we obtain that the edge path  from _j to _k is on the boundary of S. So _j has two edge neighbours in S: its neighbour on the other side of the edge path , and _j-1. This would contradict the stability of S.
  
  In the second case, _i+1^j-1 has no tile in common with S. By applying Lemma <ref>, we obtain that the edge path  from v_i to v_j is on the boundary of S and so _i+1^j-1⊂S. In that case we also have that no tile of  is in S. Indeed, if there exist _k∈ S (assume by symmetry that k>j) then taking the smallest such k, we have _k-1∈S, and the edge path ' from v_j to v_k (a common vertex to _k and _k-1) is in the boundary of S. And so once again _k-1 has two neighbours in S (_k and some t∈ S through '), contradicting stability.

  Overall, we have proved that S is chain-convex.



We call fortress (or finite obstacle) a non-empty finite patch R that resists outside contamination.
That is, the configuration c_R where tiles in R are 0s and all other tiles are 1s is stable for 2-neighbour contamination. See Fig. <ref> for an example of fortress for 2-neighbour contamination with quadrilater tiles.



Straightforwardly, the existence of fortresses in a structure is incompatible with a critical percolation threshold less than 1.
Our first step to prove the existence of a non-trivial critical percolation threshold is to use Lemma <ref> to prove the absence of such fortresses.


	In an edge-to-edge rhombus tiling there is no fortress (finite obstacle) for 2-neighbour contamination.



	Let R be a fortress and S be its complement.
	By definition, S is stable for 2-neigbour contamination.
	
	Let  be a chain that intersects R. As R is finite,  enters and leaves R.
	That is, there exist i<j such that _i,_j ∈ S, _i+1, _j-1∈ R.
	Up to restricting to a sub-segment of chain, we assume that _i+1^j-1⊂ R.
	
	Denoting v_i and v_i' (resp. v_j and v_j') the vertices of _i ∩_i+1 (resp. _j-1∩_j) such that v_i and v_j are in the same half-space delimited by .
	Denoting  (resp. ') the edge path from v_i to v_j along  (resp. from v_i' to v_j') and applying Lemma <ref> on both we obtain that the tiles of _i+1^j-1 are edge adjacent to S through both  and ', contradicting the stability of S.



In what follows, we define some nice notions of polygons and paths in the rhombus tiling, then use Lemma <ref> and the results above to prove that any chain-convex patch has such a well-behaved boundary.



 
  We say that =(_i)_0≤ i <m is a chain polygon in  when :
  
    
  * the _i are distinct tiles, 
    
  * consecutive _i are edge adjacent, that is : for any i, _i+1 m∈_i,
    
  * the cycle has no cords, that is: for any i,j such that j≠ i ± 1  m, _j∉_i.
  
  
  
  Note that any chain polygon =(_i)_0≤ i < m can be partitoned into k chain segments for some integer k, that is: there exists chains _1,…_k and indices i_1,… i_k-1 such that {_0, …_i_1}⊂_1, {_i_1,…_i_2}⊂_2, …{_i_k-1,…_m-1,_0}⊂_k. Indeed, one can always choose m chain segments made of only two tiles each.

  A chain polygon is called a chain n-gon if it can be partitioned into at most n chain segments.

  We say that = (_i)_i∈ℤ is a simple path in  when the _i are distinct tiles, consecutive _i are edge-adjacent and there are no cords.

  We call chain polypath a simple path (_i)_i∈ that can be partitioned into k half-chains and chain segments for some integer k.
  A chain polypath is called a n-polypath if it can be partitioned into at most 2 half-chains and at most n-2 chain segments.





  Let S⊊ be a chain-convex set of tiles, and d be the number of edge directions in the tiling.

  If S is finite, then the exterior tile boundary of S is a chain 2d-gon.

  If S is infinite, then the exterior tile boundary of S contains an infinite chain 2d-polypath. More precisely, the exterior tile boundary of S is the disjoint union of one or more chain polypaths of which the sum of the number of chain segments is at most 2d.  



  Let S be a finite chain-convex set of tiles.

  First note that we can partition S (which is finite, as S is) as a chain-polygon of chains that do not intersect S. Indeed, any two consecutive tiles in S (when going around S in a given rotationnal order) are edge-adjacent and the chain connecting them does not intersect S (by definition of chain-convexity). So grouping the tiles of S by common edge direction, we get finitely many segments of chain.

  Actually, we have at most 2d chain segments in S because for each edge orientation  there are at most two chain segments of edge direction  in S.
  This follows from the uniform monotonicity of chains, see Lemma <ref>, and the fact that chains of same edge direction cannot cross.
  Indeed assume that for some edge direction , there are three distinct chains , ' and ” that do not intersect S but have tiles in the vertex-neighbourhood of S. Up to renaming assume that ' is between  and ” as in Fig. <ref>. By uniform monotonicity, ' either crosses S (which is a contradiction) or  or ” (which is also a contradiction).

  


  

  Let S be an infinite chain-convex set of tiles. Let P be a connected component of S, we prove that P is an infinite chain 2d-polypath.
  This proof is decomposed in two parts: first we prove that P is infinite, and second we prove that it intersects non-trivially (meaning for at least two consecutive tiles) at most two chains for each chain direction.
  As P is a connected component of S and S is infinite and chain-convex, each tile t∈ P has two edge-neighbours in P, either two opposite edges (the tiles are along a chain) if P shares an edge with S, or two adjacent edges if P only shares a vertex with S.
  This implies that if P is finite, then it is a chain polygon. This polygon induces a finite interior and an infinite exterior. As S is infinite it cannot be the interior, and hence P together with its interior forms a fortress (finite obstacle) for 2-neighbour contamination which contradicts Lemma <ref>. So P is infinite.
  
  As detailed in the first part of the proof, each chain that has two consecutive tiles in S does not insersect S.
  This implies, using the same proof as above, that for each chain directions there are at most two segments (or half-chains) of chain of that direction in P.
  This implies that P is an infinite chain 2d-polypath (recall that 2d-polypath means it has at most 2d components).


Note that in the case of infinite S, S might be an infinite strip between two non-intersecting chains of rhombuses. In that case, S contains exactly 2 connected components which are both an infinite chain.








  Any finite patch of tiles P⊂ that is stable for 2-neighbour contamination is delimited by a chain-polygon with at most 2d sides with all 0s.

  The exterior boundary of any infinite simply-connected set of tiles P⊊ that is stable for 2-neighbour contamination contains an infinite half-chain with all 0s.





 §.§ Probabilistic arguments



In this subsection, we fix a rhombus tiling T and a  measure μ.

Let  be the set of configurations that contain at least a half-chain of zeros,i.e.,

    := { x ∈|∃ a half-chain =(_i)_i∈, ∀ i≥ 0, x__i=0}
.


	
  μ() = 0.



  For a fixed half-chain =(_i)_i∈ the set _ := { x ∈|∀ i≥ 0, x__i=0} has measure 0 because
  
    _ = ⋂_i∈ [0^χ_i]

  and μ(⋂_0≤ i≤ n[0^χ_i])≤β^n by Lemma <ref> where 0<β<1.

  Since there are only countably many half-chains (a half-chain is uniquely identified by an initial tile, a direction and an orientation), the union bound gives μ()=0 because
  
    = ⋃_ half-chain_.




Let  be the set of configurations that do not invade but do not contain any half-chain of zeros, i.e.,

    := ^∁∩^∁



Recall that we call chain 2d-gon a chain polygon with at most 2d sides.


	
  In the finitely blocking configurations , every 1 is enclosed in a closed chain 2d-gon of 0, i.e.,
  
    ⊂{ x ∈|∀ v ∈, [x_v=1 ⇒∃closed chain 2d-gon  c  around  v   of  0]}




  This derives from the definition of  together with Corollary <ref>.
  Consider some configuration c∈. As the 2-neighbour contamination F is monotone and freezing, there exists a limit configuration c^∞ = lim_n→∞F^n(c) and since c ∈⊂^∁, c^∞ is not the 1-uniform configuration, i.e., c^∞≠ 1^.

  Recall that because F is freezing, we have that for any tile t∈ T, c_t ≤ c^∞_t.
  So we also have c^∞∈.

  As c^∞ is stable for  and not the 1-uniform configuration, any 1 in c^∞ is in a stable contaminated cluster.
  Corollary <ref> states that any stable contaminated cluster is either infinite or enclosed in a chain 2d-gon of zeros.
  The case of an infinite contaminated cluster P ⊊ T is impossible, as the exterior boundary of P would contain an infinite half-chain of zeros which is a contradiction with c^∞∈.

  So any tile t is either in state 0 in c, in which case it is enclosed in the trivial chain 2d-gon of zeros that is itself; or in state 1 in c in which case it is also in state 1 in c^∞ and therefore belongs to some finite stable cluster and is enclosed in a non-trivial chain 2d-gon of zeros.





  Let t be the set of configurations x such that tile t is enclosed in a closed chain 2d-gon of 0s, including the configurations where x_t = 0 as t is enclosed in a trivial 2d-gon.

  Let t,≤ n be the set of configurations x such that t is enclosed in a closed chain 2d-gon of 0s of length at most n, and t,>n be t∖t,≤ n.


By definition, for any t and any n, we have t,n⊆t and μ(t,n)≤μ(t). 
We will actually show that μ(t) is uniformly bounded away from 1.
The first step is the following polynomial bound on the number of 2d-gons.


  Given a rhombus tiling T with finitely many edge directions.
  There exists a polynomial Q such that for any tile t, the number of closed convex chain 2d-gons around t of length n is at most Q(n).
  


  Let us first remark that a chain 2d-gon of length n is in particular a 2d-partition of [n].

  Remark also that, when walking a convex chain 2d-gon with exactly 2d sides in clockwise orientation, the order of the chain edge directions is fixed. If the 2d-gon has less than 2d sides some directions are absent but the order of chain edge directions respects the fixed order. 

  This implies that given a tile t, and a starting point p_0 there are at most as many convex chain 2d-gons of length n arount t and starting at p_0 as there are 2d partitions of [n]. In particular there are less than n^2d such chain 2d-gons. 

  Now remark that since p_0 is the starting point of a chain 2d-gon of length n that encloses t, the adjacency distance d_T(p_0,t) is less than n.

  As the tiling T has finitely many tiles up to translation, there is a maximal diameter of tiles D and a minimal area of tiles A. So the euclidean distance from p_0 to t is at most D(n-1), and there are at most π D^2n^2/A such starting points p_0 in T.

  Overall there are at most Q(n):=π D^2A n^2d+2 convex chain 2d-gons of length n around t.


  This polynomial depends only on the tileset, that is, the set of tiles in T up to translation. In particular Q(n) is of degree 2d+2 where d is the number of edge directions in T, and the leading coefficient depends on the shapes of the tiles (minimal area and maximal diameter).





  There exists a λ<1 such that for any tile t∈ T, μ(t)≤λ < 1.
  



  This lemma is a consequence of Lemma <ref>. The key element is that there are polynomially many convex 2d-gons of length n, but having 0s on the whole 2d-gon has exponential probabilistic cost.

  Consider the series ∑_n≥ 0 Q(n)β^n where 0<β<1 is the constant given by Lemma <ref> on measure μ. As β<1, and Q is a polynomial the series converges. This implies that there exists N∈ℕ such that ∑_n≥ NQ(n)β^n < 1. Denote λ_0 := ∑_n≥ NQ(n)β^n.

  Now consider a tile t∈ T and the patch P=B(t,N) made of all tiles around t up to distance N.
  Since μ is non-vanishing, there is some constant α>0 depending on N but not on t such that μ([1^P])≥α.
  
  1cm 
     
      μ([1^P] ∩t^∁)≥α(1-λ_0)
    
    
      Denote P the set of configuration where P is enclosed in a convex chain 2d-gon of zeros (not intersecting P), and P,=n the subset where it is enclosed in a convex chain 2d-gon of length exactly n.
      
      Remark that [1^P]∩t^∁ = [1^P]∩P^∁ since any chain 2d-gon of zeros around t in a configuration of [1^P] necessarily avoids and encloses P.
      
      Remark also that if n<N, P,=n = ∅ and for n≥ N we have μ(P,=n)≤ Q(n)β^n, by the union bound, as there are at most Q(n) convex 2d-gons of length n around P and P,=n is the union on all these 2d-gons  of the event [0^] which has measure less than β^n by Lemma <ref>.
      With P = ⋃_n∈ℕP,=n we have μ(P) ≤λ_0 = ∑_n≥ N Q(n)β^n.
      
      
Both [1^P] and P^∁ are upward-closed events so by hypothesis on μ they are positively correlated. Therefore we have: μ([1^P]∩t^∁) ≥α(1-λ_0) which proves the claim.
    
    
From the claim we deduce that μ(t^∁) ≥α(1-λ_0).
Denote λ := 1- α(1-λ_0).
We have μ(t)≤λ < 1.
    
    




  For any ϵ,
  there exists n such that for any t∈ T we have
  
    μ(t,> n) ≤ϵ

  



  The proof is similar to the proof of Lemma <ref> and relies on the fact that there are polynomially many convex chain 2d-gons of length n.

  Denote t,>n' the set of configurations where tile t is enclosed in a convex chain 2d-gon of zeros of length more than n (but possibly also in one of length less than n).

  By definition we have t,>n⊂t,>n'.

  Additionally t,>n' is the disjunction over all convex chain 2d-gons of length more than n of the event “being all 0” so, denoting β the constant from Lemma <ref>, we have μ(t,>n') ≤∑_k>n Q(k)β^k.

  As there the series converge, there exists n such that ∑_k>n Q(k)β^k<ϵ.

  We then have μ(t,>n)≤μ(t,>n') ≤ϵ as expected.








  μ() = 0



  We prove that for any m∈ℕ and any ϵ > 0, we have μ(B)≤λ^m + mϵ with λ<1 of Lemma <ref>.

  Take ϵ > 0.
  Take m∈ℕ.
  By Lemma <ref>, there exists n such that for any tile t,
  μ(t,>n) ≤ϵ.

  Take m tiles t_0… t_m-1 sufficiently far away from each other, in such a way that no two chain 2d-gons of length n enclosing two distinct tiles can be at distance k or less, where k is such that μ is k-Markov.
  This means that the events t_i,≤ n are independent and therefore we have μ(⋂_0≤ i <mt_i,≤ n) = ∏_0≤ i <mμ(t_i,≤ n).

  We have
  
    ⊆⋂_0≤ i < mt_i

  due to the fact that for any configuration x in B, for any i ∈{ 0, …, m-1 }, either x_t_i = 1 and thus x belongs to E_t_i due to Lemma <ref>, or x_t_i=0 and t_i is enclosed in the trivial 2d-gon of 0s of itself.
  
  Therefore, we have:
  
    ⊆⋂_0≤ i < mt_i⊆⋂_0≤ i <m( t_i,≤ n∪(t_i∖t_i,≤ n)) ⊆⋂_0≤ i <mt_i, ≤ n∪⋃_0≤ i <mt_i,>n


  From this we get:
  
    μ()    ≤μ(⋂_0≤ i <mt_i,≤ n) + μ( ⋃_0≤ i <mt_i,>n) 
       ≤μ(⋂_0≤ i <mt_i,≤ n) + ∑_0≤ i < mμ(t_i,>n)
       ≤μ(⋂_0≤ i <mt_i,≤ n) + mϵ
       ≤∏_0≤ i <mμ(t_i,≤ n) + mϵ
       ≤∏_0≤ i < mμ(t_i) + mϵ
       ≤λ^m + mϵ



  Since this holds for any m∈ℕ and any ϵ>0, we get μ()=0.


We call the proof technique above the polka dot technique, since the t_i,≤ ns focus on the surroundings of tiles far away from each other and therefore with independant behavior, just as polkka dots on our tiling.




  Let  be a rhombus tilings with finitely many edge directions.
  Let F be the 2-neighbour contamination cellular automaton on configurations {0,1}^.
  Let I be the invasion set, that is I:={ c ∈{0,1}^| F^n(c) → 1^}.
  Let μ be a  measure on {0,1}^.
  We have 
    μ() = 1.


Recall in particular that non trivial Bernoulli measures are  so this theorem holds for non trivial Bernoulli measures.


  Since μ()=0 by Lemma <ref>, we have μ(^∁)=1. Therefore μ(^∁) = μ(^∁∩^∁) = μ().
  By Lemma <ref>, μ()=0 so μ(^∁) = 0 and μ()=1.






§ OPEN QUESTIONS

This work opens more questions than it closes. We classify these open questions into three classes.

As mentioned in Section <ref>, the classical 0-1 laws do not apply for dynamical or bootstrap percolation on rhombus tilings.
In all generality, for any rhombus tilings and any percolation process, the 0-1 law does not hold, see for example Appendix <ref>.
However, we conjecture that if the rhombus tiling is sufficiently regular then the 0-1 law holds for the invasion event of percolation processes.


  Let G=(V,E) be the adjacency graph of an uniformly repetitive (or uniformly recurrent) rhombus tiling.
  Let F be a percolation process (monotone and freezing) on {0,1}^V.
  Let I⊂{0,1}^V be the set of invading configurations for F.
  Let μ be a Bernoulli measure.
  
    μ(I)∈{0,1}.




On ℤ^2, percolation processes have been studied in great generality, and though the exact critical threshold can often not be determined exactly, a trichotomy between trivial percolation threshold (p_c∈{0,1}) and non-trivial percolation threshold (p_c>0) can be determined from the stable directions of the percolation process <cit.>.
We similarly conjecture that the non-triviality of the critical threshold on sufficiently regular rhombus tilings is determined by the stable directions.
We consider here the class of multigrid dual tilings <cit.>, which are the canonical case of cut-and-project rhombus tilings: those are very regular, and in particular chains of rhombuses are almost straight (each chain of rhombuses is included in a tube of direction e⃗^ where e⃗ is the edge direction of the chain). In particular the classical Penrose rhombus tilings and Ammann-Beenker rhombus tilings are multigrid dual tilings.

[Stable directions and critical probability on rhombus tilings]
  Let  be a multigrid dual tiling and F a percolation process on {0,1}^.
  Do the stable directions of F on  determine the trichotomy between trivial percolations thresholds and non-trivial percolation threshold?



The main result of the present article is that 2-neighbour percolation invades almost surely for any  or non-trivial Bernoulli measure on any rhombus tilings, or equivalently on the adjacency graph of any rhombus tiling.
The first key element of the proof is the absence of fortress, the second is a counting argument on the possible finite walls of 0s by bounding the number of wall directions.
It can easily be seen that for arbitrary 4-regular graphs, even planar graph, if the graph has exponential growth (for example the Cayley graph of the free group on 2 generators) then the counting argument fails.
However, if the graph is quasi-isometric to ℤ^2, the counting argument may hold without the strong structure of rhombus tilings.

[Almost sure percolation for 2-neighbour percolation on 4-regular graphs QI to ^2 without fortress]
  Let G=(V,E) be a 4-regular graph that is quasi-isometric to ℤ^2.
  Let I⊂{0,1}^V be the set of invading configurations for 2-neighbour percolation on G.
  Let μ be a non trivial Bernoulli measure on {0,1}^V.
  
  If G contains no fortress (finite obstacle) for 2-neighbour contamination, is it the case that μ(I)=1?


2-neighbour percolation is very classicaly studied on ℤ^2 and has been studied on trees and non-amenable groups <cit.>. We aim to generalise this approach to other 2-generator groups such as Baumslagg Solitar groups.
[Cayley graph]
  Can we classify 2-generators finitely presented groups with regards to the critical probability of 2-neighbour percolation?


An auxiliary question that arose from our first exploration of percolation on Cayley graph is related to mixed degree graphs.
Consider for example G a single sheet of the Cayley graph of BS(1,2).
G is planar and contains vertices of degree 4 and 3, each vertex of degree 3 being adjacent to only vertices of degree 4.
In a 2-neighbour percolation on G, vertices of degree 3 are “hard” to contaminate as they require 2 out of 3 neighbours to be contaminated.
It appears that G has a critical probability of percolation of 1, that is for any non-trivial Bernoulli measure μ, μ(I)=0.
This is due to the uncountable number of vertical chains (each chain branching in two at each tile), linked to the fact that G is not quasi-isometric to ℤ^2.

However we may ask a similar question as above for mixed degree graphs that are quasi-isometric to ^2.

[Mixed degree]
  Let G=(V,E) a mixed 3-4 degree graph quasi isometric to ℤ^2 and such that degree 3 vertices are only adjacent to degree 4 vertices.
  Let I⊂{0,1}^V be the set of invading configurations for 2-neighbour percolation on G.
  Let μ be a non trivial Bernoulli measure on {0,1}^V.
  
  If G contains no fortress (finite obstacle) for 2-neighbour contamination, is it the case that μ(I)=1?



Note also that for the example of G being a single sheet of the Cayley graph of BS(1,2), there exists a second approach which consists in studying percolation not on vertices but on elementary cycles, or equivalently on the dual graph G^*.
In other words, we can consider G either as a graph on which we study percolation, or as a tiling by elementary cycles for which we study the percolation on the adjacency or dual graph. 



§ THE NON 0-1 PERCOLATION ON A QUADRILATER TILING


Let P_f be the fortress consisting of 4 trapezes and a small square forming a big square presented in Fig. <ref>.
Let _f be the square grid where the origin square has been replaced by P_f.

For a configuration c∈{0,1}^_f, we write c|_P_f=0 (resp. c|_P_f=1) when all the tiles of the fortress P_f are in state 0 (resp. 1), c|_P_f∉{0,1} when at least a fortress tile is in state 0 and at least one is in state 1. For other tiles we denote c(i,j) with (i,j)≠ (0,0) for the state of the (i,j) tile in the induced grid.

We write F the cellular automaton of 2-neighbour contamination on both _f and ^2.


  
  Let 𝔉 be the set of configurations in {0,1}^_fwhere at least one tile of the fortress P_f is in state 1.
  Let  be the set of invading configurations.
  Let μ be the Bernoulli measure of parameter p.

  
    μ(I) = μ(𝔉) = 1-(1-p)^5


We give here an outline of the proof which is adapted from the strategy on rhombus tilings detailed in Section <ref>.

Denote G_∘ the square grid with a single hole on the origin, that is G_∘ := ℤ^2∖{(0,0)}.
Denote F the 2-neighbour contamination also on G_∘, and _∘ the set of invading configurations on {0,1}^G_∘.


	
  For any non-trivial Bernoulli measure μ on {0,1}^G_∘, μ(I_∘)=1.


In what follows, we sketch the proof that the behavior of the square grid with a hole can be assimilated to the one of the full square grid ^2, and reuse our results on rhombus tilings to prove the almost-sure invasion.

Given a stable connected subset P of G_∘, we denote P̃ its induced ℤ^2 subset by P̃:= P∪{(0,0)} if P contains at least three of {(1,0), (-1,0),(0,1), (0,-1)}, and P̃:= P otherwise.

We say that P is regular if |P∩{(1,0), (-1,0), (0,1), (0,-1)}| ≠ 2 and singular otherwise.

If P is singular, then exactly two of {(1,0), (-1,0), (0,1), (0,-1)} are in P. Denote H_1 and H_2 the two half-planes among {(i,j)| i>0}, {(i,j) | i<0}, {(i,j) | j>0}, {(i,j) | j<0} containing this two points.
Then denote P̃_̃1̃:= P ∩ H_1 and P̃_̃2̃:= P∩ H_2.  Remark that because outside of position (0,0), P̃ is stable for 2-neighbour contamination in ℤ^2, we obtain that  P̃=P̃_̃1̃∪P̃_̃2̃.



  Let P be a connected subset of G_∘ that is stable for 2-neighbour contamination.

  If P is regular, then P̃ is stable for 2-neighbour contamination in ℤ^2.

  If P is singular, then both P̃_1 and P̃_2 are stable for 2-neighbour contamination in ℤ^2.


  Remark that Lemma <ref> holds in G_∘, though in G_∘ the horizontal line (resp. vertical line) going through 0 is actually two disjoint half-chains.
  The conclusion follows.


From this remark on P̃, we obtain immediatly the following corollary on the shape of stable clusters.

  Let P be a  subset of G_∘ that is stable for 2-neighbour contamination.
  If P is finite, then P̃ is enclosed in either a rectangle or a L-shaped hexagon.
  If P is infinite, then P̃'s boundary contains an infinite half-chain.


Here we call L-shaped hexagon the union of two rectangles of the form ([0,n_1]× [0,m_1]) ∪ ([0,n_2]× [0,m_2]), see Fig. <ref>.





As the number of “sides” of a “wall” around a finite contaminated cluster is bounded, then we obtain a polynomial upper bound on the number of possible walls of a given length as stated below.


  There is a polynomial Q such that the number of possible walls of length n around any given cell t is at most Q(n).


With these intermediate statements, we can now apply the proof strategy from Section <ref> as outlined below


We can now apply the same techniques as for the rhombus case.
The set  of configurations containing at least an infinite half-line or half-column in state 0 is of measure 0.

Define E_t as the set of configurations where the tile t is enclosed in a finite wall.

Denote := ^∁∩^∁.

We have ⊂⋂_t∈ G_∘ E_t.

Now we have a uniform bound λ<1 on the measure of E_t, and a uniform approximation on E_t,>n.

We apply the polka dot technique of Lemma <ref> to obtain μ()=0, which implies μ(_∘^∁)=0 and μ(_∘)=1.



This result implies that, on _f, almost surely all non-fortress cells eventually get contaminated.
As a consequence, full contamination happens almost surely as long as the fortress is initially disarmed (meaning it initially contains at least one contaminated cell), indeed a disarmed fortress gets contaminated if it is surronded.

Note that for a  measure, we similarly have μ()=μ(𝔉) by a very similar proof.

Note that the proof outlined here also works for any single finite rectangular (or sufficiently well behaved)  hole (or fortress) in a square grid.



§ A PERCOLATION PROCESS ON RHOMBUS TILINGS WITHOUT 0-1-LAW


In this appendix we quickly show an example of non uniformly repetitive rhombus tiling  and a specific percolation process F such  that  contains a single fortress for F leading to a non 0-1 probability of percolation for any parameter 0<p<1.

Here we consider rhombus tilings with 5 edge directions ζ_i for i=0...4 (as for Penrose tilings).
In this setting we consider the specific tiling  of Fig. <ref>.

On this tiling, we have ten possible adjacency directions for tiles which are ±ζ_i^ for i=0...4.
We say that t' is adjacent to t in direction a if t∩ t' ≡ a^ and the vector t⃗t⃗'⃗ from the barycenter of t to that of t' has positive scalar product with a.

We call partially directed boostrap percolation F_A the percolation process F where a tile gets contaminated if it has at least two contaminated neighbours in directions A ⊂{±ζ_i^| 0≤ i < 5}.
We consider the specific case where A_3 = {ζ_0^, ζ_1^, ζ_2^,±ζ_3^, ±ζ_4^}
and the percolation process F_3 associated with A_3, that is:


    F_3(c)_t =
      
        1     if c_t=1 or t has at least two neighbours t' and t” in
       directions from A with c_t'=1 ∧ c_t”=1
    
        0     else,


This means a given tiles gets contaminated if two of its neighbours are contaminated in the previous step, but not counting neighbours in directions {-ζ_0^, -ζ_1^, -ζ_2^}.



One can check that the only fortress for F_3 in  is the “cube” at the center of Figure <ref> which is at the crossing of the ζ_0, ζ_1 and ζ_2 lines (any other finite set of tiles S contains a tile with two neighbours outside S in directions from A).

Note that outside this singular band of tiles, in the white zones F_3 behaves as two neighbour percolations on ℤ×ℕ as only directions ζ_3 and ζ_4 are present; and so almost surely the two half planes outside the band get invaded. This means that the right part of the band almost surely gets contaminated.
Indeed, if the outside half planes are fully 1s and the grey chains on the right each contain a contaminated cell (say at positions n_1 and n_2, with position 0 being the closest to the central “cube”) then both grey chains get contaminated from 0 to that contaminated position. Consequently the band gets fully contaminated from the fortress to the position min(n_1,n_2).
Since for every N, there almost surely exist n_1,n_2≥ N such that the grey cell of the top chain at position n_1 and of the top chain at position n_2 are contaminated, it follows that the whole right band almost surely gets contaminated.

So if the fortress has been disabled the entirety of the left part of the band gets contaminated, but if the fortress has not been disabled then the full invasion does not occur.

Overall the probability of invasion is exactly the probability that the fortress initally contains a contaminated tile; this probability is not in {0,1} for non trivial Bernoulli distributions.









