CUBO A Mathematical Journal Vol.10, N o ¯ 03, (93–102). October 2008 Dualities Useful in Bond Percolation Pedro Ferreira de Lima Unversidade Regional do Cariri – URCAC Av. Leão Sampaio S/N, CEP.63.010-970, Crajubar-CE, Brasil email: limapf@yahoo.com.br and André Toom Universidade Federal de Pernambuco – UFPE, CCEN-Departamento de Estat́ıstica, CEP.50.740-540, Recife-PE, Brasil email: toom@de.ufpe.br ABSTRACT We state four facts about dual pairs of graphs drawn in a plane. These facts pertain respectively to finite non-oriented, infinite non-oriented, finite oriented, and infinite oriented graphs. We do not include proofs of the former two facts (although we have them), but show that these facts are “evident” in some naive sense. Then we deduce the latter two facts from the former two ones. All of these facts can be used to obtain upper estimations for critical values of two-dimensional percolation models and we present three references and one example to illustrate this. RESUMEN Nosotros establecemos cuatro hechos acerca de pares duales de grafos en el plano. Estos hechos se relacionan respectivamente con grafos finito no-orientado, infinito no- orientado, finito orientado y infinito orientado. Nosotros no incluimos demostraciones 94 Pedro F. de Lima and André Toom CUBO 10, 3 (2008) de los dos anteriores hechos (aunque tenemos estas) pero demostramos que estos he- chos son “evidentes” en algun sentido ingenuo. Entonces deducimos los dos ultimos hechos desde los dos anteriores. Todos estos hechos pueden ser usados para obtener estimativas por arriba para valores cŕıticos de modelos de infiltración en dimensión dos y presentamos tres referencias y un ejemplo para ilustrar esto. Key words and phrases: Percolation, critical values, oriented planar graphs, duality. Math. Subj. Class.: 05C10, 60K35, 82B43, 94C15. 1 Introduction We state four facts about dual pairs of graphs drawn in a plane. These facts pertain respectively to finite non-oriented, infinite non-oriented, finite oriented, and infinite oriented graphs. All of these facts can be used to obtain upper estimations for critical values of two-dimensional percolation models and we present three references and one example to illustrate this. We call the former two facts the “main lemma” and the latter two facts “theorem”. We do not prove the main lemma although we have a proof in [L.2002]; instead we show that it is “evident” in some naive sense. Then we deduce our theorem from the main lemma. We consider graphs with a finite or countable sets V of vertices and E of edges. Every edge connects two vertices, which are called its ends (and which may coincide). One and the same pair of vertices may be connected by several edges. A finite path is a finite sequence “ vertex- edge-vertex-edge-. . . -edge-vertex” in which every edge connects the vertices between which it is placed in this sequence and in which some vertices and/or edges may coincide. An infinite path is an infinite sequence “vertex-edge-vertex-edge-. . . ” with the same properties.. A path is called self-avoiding if all the vertices in its sequence are different. A contour is a finite path in which the initial and final vertices coincide. A contour is self-avoiding if all its vertices are different except, of course, the first and last vertices, which coincide. We say that a graph G is connected if every two vertices of G are connected by a path in G. All the graphs considered in this paper are assumed to be connected unless stated otherwise. We assume that every vertex is an end of only a finite number of edges. Therefore, if one of the sets V or E is finite, the other is finite also. If V and E are finite, we call G finite, otherwise G is infinite. We consider non-oriented and oriented percolation models on graphs depending on the way in which we attribute certain states to their edges. In the non-oriented model each edge of a graph can be open or closed, independently of all the other edges. In the oriented model we distinguish two directions of each edge, and every edge can be open or closed in each direction independently of the state of the other direction of the same edge and states of all the other edges. Henceforth we shall write simply graphs instead of percolation models on graphs when it does not produce confusion. A path in a non-oriented graph is open if all its edges are open. A path in an oriented graph is open in a certain direction if all its edges are open in this direction. In a non-oriented CUBO 10, 3 (2008) Dualities Useful in Bond Percolation 95 graph a contour is open if all its edges are open. In an oriented graph a contour is open in a certain direction if all its edges are open in this direction. Now let us speak about drawing graphs in a plane IR2. A curve is a continuous function f : [0, 1] → IR2. The points f (0) and f (1) are called the ends of this curve. A curve is called self-avoiding if ∀x, y ∈ [0, 1] : x 6= y ⇒ f (x) 6= f (y). A curve is called polygonal if it is piecewise affine, that is there are 0 = t0 < t1 < . . . tn = 1 such that f (t) is an affine function of t in every segment [tk−1, tk], k = 1, . . . n. The points f (tk), 0 < k < n, are called corners and the sets {f (t) | tk−1 ≤ t ≤ tk}, k = 1, . . . , n are called pieces. Henceforth we consider only polygonal curves. This approach is not unusual. We say that a graph G is drawn in a plane if the following conditions are satisfied:                                          1. Each vertex v of G is represented by a point P (v) in the plane, so that different vertices are represented by different points. We denote the set of points representing all vertices of G by P (V ). 2. Each edge e of G is represented by a polygonal curve fe, where: a) fe(0) and fe(1) represent the ends of this edge. b) The curve fe is self-avoiding, except when e is a loop, in which case fe(0) = fe(1). 3. If ei 6= ej are two differents edges, the corresponding curves have no common points, except common ends, which represent common ends of ei and ej when they have such ones. 4. Each bounded subset of the plane intersects only a finite (or empty) set of curves representing edges. A closed curve is a polygonal function f from a circle S1 to IR2. A Jordan curve is a closed self-avoiding curve, which means that the values of this function are different for different elements of S1. According to the well-known Jordan theorem, any Jordan curve separates the remaining part of the plane into two open regions, one bounded, the other unbounded, so that it intersects any curve whose ends belong to different regions. Notice that every finite path of a graph drawn in a plane is represented by a curve and every contour is represented by a closed curve, which are self-avoiding if and only if the original path, respectively contour is self-avoiding. Given a graph G drawn in a plane, we call P (G) the union of representations of its edges. Since P (G) is closed, its complement is open. Connected components of this complement are called faces of G. 96 Pedro F. de Lima and André Toom CUBO 10, 3 (2008) We say that two connected graphs G and G′ drawn in the same plane are dual if they satisfy the following conditions. (Here and elsewhere we may write simply vertices and edges, while in fact we mean their representations in the plane.)                            1. There is a 1-to-1 correspondence between the faces of G and vertices of G′, called duality, such that each face of G contains its dual vertex of G′. 2. There is a 1-to-1 correspondence between the vertices of G and faces of G′, called duality, such that each vertex of G is in the dual face of G′. 3. There is a 1-to-1 correspondence between the edges of G and edges of G′ called duality, such that representation of each edge of each graph crosses the representation of its dual edge of the dual graph only in one point, which is not a corner or end of any of them. Representations of edges of G and G′, which are not dual, have no common points. This kind of duality is well-known and described in many textbooks. Observe that this kind of duality is a symmetric relationship, that is, if G′ is dual of G, then G is dual of G′. Of course, if a graph is finite, its dual is finite too. Now from duality of graphs drawn in a plane we go to dualities of percolation models on these graphs. The rules (1 ) and (2 ) are the central point of our definitions. Rule for a dual pair of non-oriented graphs (G, G′): Every edge of graph G′ is open if and only if the dual edge of graph G is closed. } (1) Given a non-oriented graph G, we say that:        a) vertices α and β are reachable from each other if there is an open finite self-avoiding path connecting them. b) vertex α and ∞ are reachable from each other if there is an open infinite self-avoiding path which starts at α. Main Lemma. Let (G, G′) be a dual pair of non-oriented graphs, satisfying the rule (1 ). Then:                  a) If G is finite: Two vertices α and β are not reachable from each other in G if and only if there is an open self-avoiding contour in G′, whose representation in the plane leaves P (α) and P (β) in different regions. b) If G is infinite: A vertex α and ∞ are not reachable from each other in G if and only if there is an open self-avoiding contour in G′, whose representation leaves the point P (α) in the bounded region. The main lemma is “evident” in the same sense, in which all the basic topological facts are evident (Jordan’s theorem, for example). We have a proof of it in [L.2002], but do not include it CUBO 10, 3 (2008) Dualities Useful in Bond Percolation 97 here. Let us notice that it is possible to turn the non-oriented percolation model into a graph by eliminating all closed edges. The resulting graph may be disconnected and the main lemma boils down to the following “evident” statements:                  a) Two vertices of a finite graph drawn in a plane are not connected with a path in this graph if and only if there is a face containing a Jordan curve separating the representations of these vertices. b) A vertex of an infinite graph drawn in a plane is not connected with infinity (i.e. there is no infinite self-avoiding path in this graph starting at this vertex) if and only if there is a face containing a Jordan curve surrounding the representation of this vertex. Rule for a dual pair of oriented graphs (G, G′): Given dual edges e and e′, for each direction of e the corresponding direction of e′ is the direction from right to left when we go along e in the given direction. Every edge of the graph G′ is open in a certain direction if and only if the dual edge of the graph G is closed in the corresponding direction.          (2) Observe that in the case of oriented graphs the symmetry of duality becomes more complicated: given a direction of an edge e′ of G′, the corresponding direction of e is from left to right when we go along e′ in this direction. Given an oriented graph G, we say that:          a) vertex β is reachable from vertex α if there is a a self-avoiding path connecting α and β, open in the direction from α to β. b) ∞ is reachable from a vertex α if there is an infinite self-avoiding path which begins at α and is open in the direction away from α. Theorem. Let (G, G′) be a dual pair of oriented graphs, satisfying the rule (2 ). Then:                a) If G is finite: A vertex β is not reachable from another vertex α in G if and only if there is a self-avoiding contour in G′, open in such a direction that its representation in the plane leaves P (α) on the left side and P (β) on the right side. b) If G is infinite: ∞ is not reachable from a vertex α in G if and only if there is an open self-avoiding contour in G′, whose representation in the plane leaves the point P (α) in the finite area and surrounds it in the counter-clock direction. Let us assume that the main lemma is proved and prove the theorem. Proof in case a). Let (G, G′) be a dual pair of oriented finite graphs. Let us call a good path a self-avoiding path in the graph G connecting α and β, open in the direction from α for β. A good contour is a self-avoiding contour in the graph G′, which is open in such a direction that its representation is a closed curve that leaves the point P (α) on the left side and P (β) on the right side. 98 Pedro F. de Lima and André Toom CUBO 10, 3 (2008) In one direction. Let us suppose that there is a good path in G and there is a good contour C in G′ and obtain a contradiction. Let us denote H∗ and C∗ the representations of H and C in the plane respectively. By our assumption, P (α) and P (β) are at different sides of C∗. From Jordan theorem, C∗ and H∗ have at least one common point. Let Q∗ be the first point of intersection between C∗ and H∗ when we move along H∗ starting at P (α). So Q∗ belongs to representations of two dual edges, e of G and e′ of G′. The edge e′ belongs to the contour C and is open in the direction of C. Therefore the ends of e are on the opposite sides of C∗ and the direction of e′ in the direction of C corresponds to the direction of e from the left side to the right side of C. Since P (α) is on the left side when we move along C in the counter-clock direction, the edge e of the path H is open in the direction from left to right of C. So both e and e′ are open in dual directions, which contradicts rule (2 ). In the other direction. Let us assume that there is no good path in the graph G and prove that there is a good contour in the graph G′. Let us classify vertices of G into three types as follows:        1) A vertex v of G is type 1 if there is an open path from α to v. 2) A vertex v is type 2 if there is a path from v to β without vertices type 1. 3) A vertex v is type 3 if it is neither type 1, nor type 2. Notice that every vertex of G has exactly one type. Given a dual pair (G, G′), every face of G′ is given the same type as the type of the corresponding vertex of G. Let us introduce a dual pair (G, G ′ ) of non-oriented graphs, which have the same vertices and edges as G and G′, and their representations in the plane. Let any edge of the graph G be open if and only if both ends of this edge are type 2 in G or both are not type 2 in G. After that, all the edges of G ′ are declared open or closed according to rule (1 ). Since α is type 1 in G and β is type 2 in G, every path in G connecting α and β has a closed edge. Therefore β is not reachable from α in G. Hence, from the finite case of main lemma, there is an open self-avoiding contour C in the graph G ′ , whose representation in the plane separates P (α) and P (β). Let us denote e′ 1 , e′ 2 , . . . , e′n the edges of that contour. All these edges are open, so all of their duals e1, e2, . . . , en, in G are closed. Therefore every edge ei connects a vertex not type 2 with a vertex type 2 of G. Let us denote these vertices u1, u2, . . . , un and v1, v2, . . . , vn respectively. Let us prove that all the vertices u1, u2, . . . , un are type 1. Suppose that a vertex uk is not type 1. We know that uk is connected with a vertex vk by an edge and that vk is type 2. There is a path from vk to β without vertices type 1, so there is a path from uk to β without vertices type 1, so uk is type 2. This is a contradiction. So every ui is type 1, therefore every ei is closed in G in the direction from ui to vi because otherwise vi would be type 1. Therefore all e ′ i should be open in G ′ in such a direction that the faces ui are on the left side and the faces vi are on the right side of them. Notice that no vertex type 2 can be inside the contour C. Therefore ui are inside of our contour C and vi are outside of C because vi are type 2. Thus C is a self-avoiding contour, which separates P (α) from P (β) and is open in such a direction that it leaves P (α) on the left side and P (β) on the right side. CUBO 10, 3 (2008) Dualities Useful in Bond Percolation 99 Proof in case b). Let (G, G′) be a dual pair of infinite oriented graphs. A good path is a self- avoiding infinite path in G, which begins in α and is open in this direction. A good contour is a self-avoiding contour in the graph G′, which is open in that direction, whose representation in the plane goes around P (α) in the counter-clock direction. In one direction. Let us suppose that there is a good path H in G and a good contour C in G′ and obtain a contradiction. Let us denote H∗ and C∗ the representations of H and C in the plane respectively. Due to the condition 4 of definition of graph drawn in a plane, there is only a finite set of vertices of G inside C∗. Hence, since H is self-avoiding and infinite, it contains a vertex β, whose representation is in the exterior of C∗. So P (α) and P (β) are in different regions of IR2 \ C∗. Hence, from Jordan theorem, C∗ and H∗ have at least one common point. Let Q∗ be the first point of intersection of C∗ with H∗ when we go along H∗ starting at P (α). So Q∗ belongs to representations of two dual edges, one of G and the other of G′. By the rule (2 ), these edges cannot be open at the same time in corresponding directions. But they are: the edge of H is open from inside to outside of the contour C∗ and the edge of C is open in the counter-clock direction. This makes a contradiction. In the other direction. Let us assume that there is no good path and prove that there is a good contour. Let us classify vertices of G into three types as follows (this classification is similar to that in the finite case, but not exactly the same):        1) A vertex v of G is type 1 if there is an open path from α to v. 2) A vertex v is type 2 if there is a path from v to ∞ without vertices type 1. 3) A vertex v is type 3 if it is neither type 1, nor type 2. Notice that every vertex of G has exactly one type. Given a dual pair (G, G′), every face of G′ is given the same type as the type of the corresponding vertex of G. As before, let us use a dual pair (G, G ′ ) of non-oriented graphs, which have the same vertices and edges and the same representations in the plane as G and G′. Let any edge of the graph G be open if and only if the ends of that edge are both type 2 or both of another type in G. After that, let the edges of G ′ be open or closed according to the rule (1 ). Since there is no good path in G, the set of vertices type 1 in G is finite. Therefore every self-avoiding path in G beginning at α has a finite number of vertices type 1. So for each infinite self-avoinding path in G, starting at α, there is a last vertex ω type 1, all the subsequent vertices being type 2. According to the definition of G, the edge of G, which connects ω with its successor in this path, is closed. So ∞ is not reachable from α in G. Therefore, due to the infinite case of main lemma, in the dual graph G ′ there is an open self-avoiding contour C, whose representation surrounds P (α). Let us denote e′ 1 , e′ 2 , . . . , e′n the edges of that contour. Since all these edges are open, all their duals e1, e2, . . . , en in G are closed. According to the definition of the graph G, each edge ei of G connects a vertex not type 2 with a vertex type 2 in G. Let us denote these vertices u1, u2, . . . , un and v1, v2, . . . , vn respectively. Like in the finite case, we can prove that each ui is type 1. So ei has to be closed 100 Pedro F. de Lima and André Toom CUBO 10, 3 (2008) in G in the direction from ui to vi, because otherwise vi would have type 1. So all e ′ i should be open in G′ in such a direction that the faces ui are on the left side and the faces vi are on the right side of them. As before, no vertex of type 2 can be inside the contour C∗. Therefore, every ui is inside of C ∗ and vi is outside of it because vi is type 2. So C is a self-avoiding contour in G ′, whose representation surrounds P (α), which is open in a direction, which leaves P (α) on the left side, that is in the counter-clock direction. � Our proofs are over. Let us present examples of use of our main lemma and theorem to obtain upper estimations of critical values in percolation. As usual, we denote IL2 the non-oriented graph in which the set of vertices is ZZ 2 and two vertices are connected with an edge if the Euclidean distance between them is 1. An example of application of an assertion similar to the item b) of main lemma to the case when G = IL2 is on pp. 15-19 of Grimmett’s book [G.1999]. Also there is an example on pp. 6-13 of [T.2001]. An example of application of an assertion similar to the item a) of our theorem to a special class of cellular automata (a discrete analog of contact processes) is in [T.1968]. An example of application of the item b) of our theorem is in [T.2001] on pp. 16-20. It remains to present an example of use of item a) of the main lemma. Let us consider a finite rectangular part of the graph IL2 with the width W and height H. It is shown on the figure 1 with W = 8 and H = 6. α                                O - x ↑y                                β Figure 1. Notice that we are using a rectangular coordinate system Oxy with the origin at the left-lower corner of the picture. Let us suppose that all the leftmost vertices with x = 0 are identified with α (say, one of them is α and the vertical edges connecting them are always open). All the rightmost vertices with x = W are identified with β (say, one of them is β and the vertical edges connecting them are always open). All the other edges are open with probability ǫ and closed with probability 1 − ǫ independently from each other. Let us estimate the probability that α and β are reachable from each other. It is easy to prove that, if H ≤ const ·W and ǫ is small enough, say ǫ < 1/3, this probability tends to zero when W → ∞. To estimate the same probability for large ǫ is not so easy; we shall do it using the item a) of main lemma. According to it, α and β are not reachable from each other if and only if there is a contour in the dual picture, separating α from β. This contour must contain the vertice dual of the unbounded face of the original graph. Cutting this CUBO 10, 3 (2008) Dualities Useful in Bond Percolation 101 contour at this vertex, we obtain a path connecting the upper and lower sides of the dual graph, which is similar to the original one. Let us denote δ = 1 − ǫ. Thus the probability that α and β are not reachable from each other does not exceed W · ∞ ∑ k=H (3δ)k = W · (3δ)H 1 − 3δ . If W ≤ const · H and ǫ > 2/3, this quantity tends to zero when H → ∞. Thus the probability that α and β are reachable from each other behaves differently for small vs. large values of ǫ when W ≍ H → ∞. Now let us discuss some previous publications. Whitney [W.1932, W.1933] proved some state- ments about dual graphs. His theorem 4 on page 77 of [W.1933] is similar to the finite case of our main lemma, but it gives only a criterion whether a graph is connected or not and is not concerned whether two particular vertices are connected. Our main lemma is often believed to be “well-known”, but we cannot refer the reader to a source, where it is proved or even stated beyond a few special cases. We believe that this is not acceptable because mathematics is a general rigorous science and all important mathematical facts should be stated and proved in a general form. Hammersley had some idea of duality when he wrote [H.1959], which provided the first upper estimation of a critical value in percolation. However, no general definition of duality was stated and no rule similar to our rule (1 ) was declared there. The most fundamental book on percolation is Grimmett’s [G.1999]. On pages 16-18 and 283-287 he explains this kind of duality and its application to obtain an upper estimation of a critical value. However, he does all this only for the graph IL2 and without a proof. Instead of going into topological details, [G.1999] refers the reader to the page 386 of [K.1982], the first page of Appendix “Some results for planar graphs”, without specifying, which result of that Appendix is to be used. However, [K.1982] deals mostly with periodic, therefore, infinite case and mostly with site percolation and matching pairs. Finally, about duality of oriented graphs. According to our knowledge, our theorem and the very definition of duality of oriented graphs have never been mentioned in print except [T.1968, T.2001], in both cases without a proof, and [L.2002], unpublished. Although our theorem allows to obtain upper estimations in oriented percolation models, these estimations can be obtained by other means also, albeit not so easily. Let us present some examples. Shnirman [S.1968] proved non-ergodicity of Stavskaya process (a discrete-time contact process) without using duality. He considered the sequence of distributions for all natural t and proved by induction that all of them satisfy a certain infinite system of inequalities. His method was so complicated that it almost never was used again except [T.1972]. Durrett [D.1984] obtained an upper estimation of critical value in a few oriented percolation models, as a corollary of his study of a certain contact process. Liggett [L.1995] obtained upper estimations of critical values in some percolation models as by-products of his study of a certain growth model. For our example Liggett proves that the critical value does not exceed 2/3. Durrett’s and Liggett’s numerical estimations 102 Pedro F. de Lima and André Toom CUBO 10, 3 (2008) are better than that which we obtained in [T.2001], which was an educational text designed just to illustrate some ideas. However, the duality approach seems more general and can be amplified to obtain better estimations. Acknowledgements. P. de Lima did this work at the department of statistics of the Federal University of Pernambuco as a part of his master program supported by CAPES. A. Toom’s research was supported by CNPq, grant 300991/98-3. Received: February 2008. Revised: June 2008. References [D.1984] R. Durrett, Oriented Percolation in Two Dimensions, Annals of Probability, 12 (1984), n. 4, pp. 999–1040. [G.1999] J. Grimmett, Percolation, Springer, 1999. [H.1959] J.M. Hammersley, Bornes supérieures de la probabilité critique das un processus de filtration, Le calcul des probabilités et ses application, Colloques Internationaux du Centre National de la Recherche Scientifique, LXXXVII (1959), Paris, pp. 17–37. (In French.) [K.1982] H. Kesten, Percolation theory for mathematicians, Birkhäuser, 1982. [L.1995] T.M. Liggett, Survival of discrete time growth models, with applications to oriented percolation, Annals of Applied Probability, 5 (1995), pp. 613–636. [L.2002] P.F. de Lima, Teoremas de Dualidade Usados na Percolação, Master’s Thesis, 2002. Unpublished. Deposited at the department of statistics of UFPE, Brazil. (In Portuguese.) [S.1968] M. Shnirman, On the problem of ergodicity of a Markov chain with infinite set of states, Problemy Kibernetiki, 20 (1968), pp. 115–124. (In Russian.) [T.1968] A. Toom, A Family of Uniform Nets of Formal Neurons, Soviet Math. Doklady, 9 (1968), pp. 1338–1341. [T.1972] A. Toom, On Invariant Measures in Non-Ergodic Random Media, Probabilistical Meth- ods of Investigation, issue 41. Ed. by A. Kolmogorov. Moscow University Press, 1972, pp. 43–51. (In Russian.) [T.2001] A. Toom, Contornos, conjuntos convexos e autômatas celulares, Curso ministrado no 23o Colóquio Brasileiro de Matemática. IMPA, Rio de Janeiro, RJ, Brazil, 2001. (In Portugues.) [W.1932] H. Whitney, Non-Separable and Planar Graphs, Trans. Amer. Math. Soc., 34 (1932) Cambridge, USA, pp. 339–362. [W.1933] H. Whitney, Planar Graphs, Fund. Math., 21 (1933), Cambridge, USA, 1933, pp. 73–84. N08