You are an expert at summarizing long articles. Proceed to summarize the following text: 
the octahedron recurrence is the product of three chains of research seeking a common generalization . the first is the study of the algebraic relations between the connected minors of a matrix , and particularly of a recurrence relating them known and dodgson condensation . attempting to understand the combinatorics of dodgson condensation lead to the discovery of alternating sign matrices and aztec diamonds . aztec diamonds are graphs whose perfect matchings have extremely structured combinatorics and soon formed their own , second line of research as other graphs were discovered with the similar regularities . the third is the study of somos - sequences and the laurent phenomenon , which began with an attempt to understand theta functions from a combinatorial perspective . in this section we will sketch both lines of research . in the following section , we will begin to describe the vocabulary and main results of this paper . let @xmath0 be a collection of formal variables indexed by ordered pairs @xmath1 . let @xmath2 , @xmath3 , @xmath4 and @xmath5 be integers with @xmath6 and set @xmath7 charles dodgson  @xcite observed that @xmath8 suggested using this recursion to compute determinants and found generalizations that could be used when the above recursion requires dividing by @xmath9 . ( this formula is not original to dodgson , according to page 7 of @xcite this formula has been variously attributed to sylvester , jacobi , desnanot , dodgson and frobenius . however , the use of this identity iteratively to compute connected minors and the detailed study of this method appears to have begun with dodgson and is known as dodgson condensation . )    before passing on , we should note that the study of algebraic relations between determinants and how they are effected by various vanishing conditions is essentially the study of the flag manifold and schubert varieties . this study lead to the invention of cluster algebras which later returned in the laurentness proofs we will discuss in section [ somos ] . see @xcite for the definitions of cluster algebras . the precise relation between cluster algebras and ( double ) schubert varieties is discussed in @xcite , although the reader may wish to first consult the references in that paper for the history of results that preceeded it . one can visualize this recurrence as taking place on a three dimensional lattice . the values @xmath0 are written on a horizontal two dimensional plane . the values @xmath10 live on a larger three dimensional lattice with @xmath10 written above the center of the matrix of which @xmath10 is the determinant and at a height proportional to @xmath11 . the six entries involved in computing the recurrence lie at the vertices of an octahedron . we make a change of the indexing variables of the lattice so that the lattice consists of those @xmath12 with @xmath13 . then the recurrence above can be rewritten as @xmath14 with @xmath15 and @xmath16 . robbins and rumsey @xcite considered modifying the recurrence to @xmath17 and also generalized by allowing @xmath18 to be arbitrary instead of being forced to be @xmath19 . we write @xmath20 when @xmath21 is even and @xmath22 when @xmath21 is odd . robbins and rumsey discovered and proved that , despite these modifications , the functions @xmath23 were still laurent polynomials in the @xmath24 and in @xmath25 , with all coefficients equal to @xmath19 . robbins and rumsey discovered that the exponents of the @xmath24 in any monomial occuring in a @xmath26 formed pairs of `` compatible alternating sign matrices . '' we will omit the definition of these obects in favor of discussing a simpler combinatorial description , found by elkies , kuperberg , larsen and propp @xcite , in terms of tilings of aztec diamonds . if @xmath27 is a graph then a _ matching _ of @xmath27 is defined to be a collection @xmath28 of edges of @xmath27 such that each vertex of @xmath27 lies on exactly one edge of @xmath28 . matchings are also sometimes known as `` perfect matchings '' , `` dimer covers '' and `` 1-factors '' . fix integers @xmath29 , @xmath30 and @xmath31 with @xmath32 . in this section , we will describe a combinatorial interpretation of the entries of @xmath26 in terms of matchings of certain graphs called aztec diamonds . for simplicity , we take @xmath33 in the recurrence for @xmath34 .    consider the infinite square grid graph : its vertices are at the points of the form @xmath35 with @xmath1 , its edges join those vertices that differ by @xmath36 or @xmath37 and its faces are unit squares centered at each @xmath1 . we will refer to the face centered at @xmath38 as @xmath38 . consider the set @xmath39 of all faces @xmath38 with @xmath40 . let @xmath41 be the induced subgraph of the square grid graph whose vertices are adjacent to some face of @xmath39 . we will call this the aztec diamond of order @xmath29 centered at @xmath42 . we define the _ faces _ of @xmath41 to be the squares @xmath38 for @xmath43 . note that this includes more squares than those in @xmath39 ; in particular , it contains some squares only part of whose boundary lies in @xmath41 . we refer to the faces in @xmath39 as _ closed _ faces and the others as _ open _ faces . let @xmath28 be a matching of @xmath41 . if @xmath38 is a closed face then either @xmath9 , @xmath19 or @xmath44 edges of @xmath38 are used in @xmath28 ; we define @xmath45 to be @xmath46 , @xmath9 or @xmath19 respectively . if @xmath24 is an open face then either @xmath9 or @xmath19 edges will be used and , we define @xmath45 to be @xmath9 or @xmath19 respectively . set @xmath47 , where the product is over all faces @xmath38 of @xmath41 . @xmath48 , where the sum is over all matchings @xmath28 of @xmath41 . it seems to be difficult to find a reference which states this result exactly in this form . @xcite shows that @xmath26 is equal to a sum over `` compatible pairs of alternating sign matrices '' and @xcite shows that such pairs are in bijection with perfect matchings of the aztec diamond . tracing through these bijections easily gives the claimed theorem . another proof can be found by mimicing the method used in @xcite to count the matchings of the aztec diamond . this result will also be a corollary of this paper s main result .    the order @xmath49 aztec diamond has @xmath50 perfect matchings .    clearly , if we plug in @xmath19 for each @xmath24 , then @xmath51 for every matching @xmath28 so the number of matchings of the order @xmath49 aztec diamond will be @xmath52 . we will denote this number by @xmath53 . then the octahedron recurrence gives @xmath54 and the claim follows by induction . many other families of graphs have been discovered for which the number of matchings of the @xmath55 graph is proportional to a constant raised to a quadratic in @xmath49 . they are summarized and unified in @xcite . one of the purposes of this paper is to give proofs of these formulae as simple as the corrolary above . the monomial @xmath56 keeps track of the matching @xmath28 in a rather cryptic manner ; it is not even clear that @xmath56 determines @xmath28 , although this will follow from a later result ( proposition [ facedetermine ] ) . it is natural to add new variables that code directly for the presence or absence of individual edges . let @xmath57 and @xmath58 be integers such that @xmath59 . draw the plane such that @xmath57 increases in the east - ward direction and @xmath58 in the north - ward . let the edges east , north , west and south of @xmath38 be labelled @xmath60 , @xmath61 , @xmath62 and @xmath63 respectively . introduce new free variables with the same names as the edges . we now define an enhanced version of @xmath34 by @xmath64 where the sum is still over all matchings of the order @xmath29 aztec diamond . each matching is now counted by both the monomial @xmath56 and the product of the edges occuring in that matching . the new @xmath34 obeys the recurrence @xmath65      somos has attempted to rebuild the theory of theta functions on a combinatorial basis . theta functions are functions of two variables , traditionally called @xmath66 and @xmath67 . the simplest theta function is @xmath68 . from now on , we will concentrate only on the dependence on @xmath66 and so write @xmath69 . for a general introduction to @xmath70 functions , see for example chapter xxi of @xcite . somos began with a well known result , that , for any @xmath71 and @xmath72 , @xmath69 would obey @xmath73 for @xmath74 and @xmath75 certain constants depending in a complicated manner on @xmath67 . somos proposed using this recurrence to compute @xmath76 in terms of @xmath74 , @xmath75 and @xmath77 , @xmath78 , @xmath79 and @xmath80 . he discovered that @xmath76 was a laurent polynomial in these @xmath81 variables . this is not difficult to prove by elementary means , but suggests a deeper explanation may be lurking . moreover , he discovered that all of the coefficients of this laurent polynomial were positive but was unable to prove this ; this will be proven for the first time as a corollary of the results of this paper . after somos s work , many other recurrence with surprising laurentness properties were discovered ; see @xcite for a summary . the family of most importance for this paper is the three term gale - robinson recurrence : let @xmath82 , @xmath83 and @xmath84 be positive integers with @xmath85 . the three term gale - robinson recurrence ( abbreviated to `` gale - robinson recurrence '' in the remainder of this paper ) is @xmath86 note that the somos recurrence is the case @xmath87 . note that if @xmath88 and @xmath89 , we get the recurrence @xmath90 , the recurrence for the number of perfect matchings of the aztec diamond . the gale - robinson recurrence , for every value of @xmath91 , can be thought of as a special case of the octahedron recurrence . this observation was first made by propp and seems to have first appeared in print in @xcite . the reduction is performed as follows : suppose that @xmath92 obeys the gale - robinson recurrence . define @xmath23 by @xmath93 . then @xmath34 obeys @xmath94    thus , if we choose @xmath60 , @xmath61 , @xmath62 and @xmath63 to be constants @xmath83 , @xmath84 , @xmath95 and @xmath96 with @xmath97 and @xmath98 , @xmath34 obeys the octahedron recurrence . in these circumstances , we must study the octahedron recurrence not with the initial conditions @xmath99 and @xmath18 but with the initial coniditions @xmath23 for @xmath12 such that @xmath100 . it therefore beomes our goal to study the octahedron recurrence with general initial conditions . the main result of this paper will be that , with any inital conditions , @xmath23 is a laurent polynomial in the initial coniditions and in the coefficients @xmath60 , @xmath61 , @xmath62 and @xmath63 . moreover , all of the coefficients of this laurent polynomial are @xmath19 . in particular , they are positive . in the reduction of the gale - robinson recurrence to the octahedron recurrence , we imposed that many of the initial conditions of the octahedron recurrence be equal to each other . thus , many monomials that would be distinct if the octahedron recurrence were run with arbitrary inital conditions become the same in the gale - robinson recurrence . however , we can still deduce that all of the coefficients of the laurent polynomials computed by the gale - robinson recurrence are positive . in this section we will introduce the main objects and results of this paper . the main object of study of this paper is a function @xmath34 defined on a three dimensional lattice by a certain recurrence . we denote the set of initial conditions from which @xmath34 is generated by @xmath101 and consider varying the shape of @xmath101 inside this lattice . it turns out that the values of @xmath34 are laurent polynomials in the initial variables where every term has coefficient 1 . we are able further more to find families of graphs such that @xmath34 gives generating functions for the perfect matchings of these graphs . special cases of this result include being able to choose @xmath101 so that @xmath34 gives us the values of three term gale - robinson sequences or such that the families of graphs are aztec diamonds , fortresses and other common families of graphs with simple formulas for the number of their matchings .    in the next subsection , we introduce the vocabulary necessary to define @xmath34 . in the following subsection , we introduce the vocabulary necessary to define the families of graphs . set @xmath102 and set @xmath103 where @xmath67 denotes one of the four symbols @xmath83 , @xmath84 , @xmath95 and @xmath96 . @xmath104 , @xmath105 and @xmath106 stand for `` lattice '' , `` edges '' and `` faces . '' we call @xmath107 and @xmath108 `` lattice - adjacent '' if @xmath109 . ( another notion of adjacency will arise later . )    for @xmath110 , set @xmath111 ( we will often drop the subscript on @xmath112 when it is clear from context . ) let @xmath113 we call @xmath114 , @xmath115 and @xmath116 the _ cone _ , _ inner cone _ and _ outer cone _ of @xmath117 respectively . @xmath114 is a square pyramid with it s vertex at @xmath117 . let @xmath118 and define @xmath119    assume that    1 . @xmath120 if @xmath121 and @xmath122 are lattice - adjacent . 2 .   @xmath123 3 . @xmath124 . the last condition is equivalent to `` for any @xmath125 , @xmath126 is finite . '' we will call such an @xmath127 a `` height function '' and call a function @xmath127 that obeys the first two conditions a pseudo - height function . note : this definition is not related to the height functions in the theory of aztec diamonds , described in @xcite . let @xmath128 be the field of formal rational functions in the following infinite families of variables : the family @xmath24 , @xmath57 , @xmath129 and the families @xmath60 , @xmath61 , @xmath62 , @xmath63 where @xmath57 , @xmath129 and @xmath130 . ( clearly , @xmath106 indexes the @xmath131 s and @xmath105 indexes the @xmath83 s , @xmath84 s , @xmath95 s and @xmath96 s ) . let @xmath132 be the ring @xmath133.$ ] for reasons to appear later , we call the @xmath131 s the `` face variables '' and the @xmath83 s , @xmath84 s , @xmath95 s and @xmath96 s the `` edge variables . '' we define a function @xmath134 recursively by @xmath135 for @xmath136 and @xmath137 for @xmath138 . our third condition on @xmath127 ensures that this recurrence will terminate . the main result of this paper is    @xmath139 and , when written as a laurent polynomial , each term appears with coefficient 1 . moreover , the exponent of each face variable is between @xmath46 and @xmath140 ( inclusive ) and the exponent of each edge variable is @xmath9 or @xmath19 .    to describe our result more precisely , we need to introduce some graph - theoretic terminology . let @xmath141 be a connected planar graph with a specified embedding in the plane and let @xmath142 , @xmath143 , @xmath144 be the edges of the outer face in cyclic order . we define a `` graph with open faces '' to be such a graph @xmath141 with a given partition of the cycle @xmath142 , @xmath144 into edge disjoint paths @xmath145 , @xmath146 , @xmath147 . denote by @xmath27 the graph with open faces associated to @xmath141 and the partition above . we call a path @xmath145 ,  @xmath147 in the given partition an `` open face '' of @xmath27 . we denote the open faces of @xmath27 by @xmath148 . we refer an interior face of @xmath141 as a `` closed face '' of @xmath27 and denote the set of them by @xmath149 . we set @xmath150 and call a member of @xmath151 a face of @xmath27 . note that the exterior face of @xmath141 is _ not _ usually a face of @xmath27 . the image associated to a is that open disks have had portions of their boundary glued to the outside of @xmath141 along the paths @xmath145 ,  @xmath147 with some additional boundary left hanging off into space . we will at times need to allow @xmath141 to be infinite , in which case @xmath141 might have several outer faces , or none at all . we will not describe the appropriate modifications , as they should be obvious . the infinite graphs which will come up in this paper will have no outer face and the corresponding will have no open faces .    we will refer to an edge or vertex of @xmath141 as an edge or vertex ( respectively ) of @xmath27 . we say that an edge @xmath152 borders an open face @xmath34 of @xmath27 if @xmath152 lies in the associated path @xmath145 , @xmath147 . all other incidence terminology ( endpoint , adjacency of faces , etc . ) should be intuitive by analogy to ordinary planar graphs . we use @xmath153 and @xmath154 to denote the edges and vertices of @xmath27 .    by a map @xmath155 we mean a triple of injections @xmath156 , @xmath157 and @xmath158 compatible with the adjacency relations . we say @xmath159 is a sub - if such a map exists . note that we do not require that open faces be taken to open faces . let @xmath160 be the ring @xmath161 $ ] where @xmath162 are formal variables indexed by @xmath163 and @xmath164 are formal variables indexed by @xmath165 . for the rest of this subsection , assume that @xmath27 is finite . a matching of @xmath27 is a collection of edges @xmath28 such that every vertex lies on exactly one edge of @xmath28 . let @xmath28 be a matching of @xmath27 . for @xmath166 , set @xmath167 if @xmath168 , @xmath9 otherwise . for @xmath163 , let @xmath83 be the number of edges of @xmath34 that lie @xmath28 and @xmath84 the number of edges of @xmath34 not in @xmath28 . if @xmath169 , set @xmath170 if @xmath171 set @xmath172 ( note that @xmath173 . )    for any matching @xmath28 , set @xmath174 for any @xmath27 , set @xmath175 where the sum is over all matchings of @xmath27 . we call @xmath56 the matching monomial of @xmath28 and @xmath176 the matching polynomial of @xmath27 .    it will turn out that the actual graphs to which we will apply this definition are bipartite , so every closed face has an even number of edges and we may omit the @xmath177 in this case . however , it will be convenient to have a definition that is valid for all graphs . we can now give our second statement of the main theorem . for any height function @xmath127 we can find an infinite @xmath178 , a decomposition @xmath179 and injective maps @xmath180 , @xmath181 and a family of sub-@xmath182 indexed by @xmath138 such that    1 . if we define @xmath183 by @xmath184 for @xmath185 , @xmath186 where @xmath187 for @xmath188 and @xmath189 for @xmath190 , then @xmath191 ( we have implicitly used the obvious injection @xmath192 . ) 2 .   if @xmath193 then @xmath194 is a sub - of @xmath182    we refer to the edges in @xmath195 as the `` weighted edges '' and the edges in @xmath196 as the `` unweighted edges '' .    clearly , this will imply the previous statement of the main theorem , except for the bounds on the exponents and the claim that the coefficients are 1 . the first will follow by showing as well that every face of @xmath27 has @xmath197 edges . the second will follow by showing that the edges of @xmath196 are vertex disjoint , so a matching @xmath28 is uniquely determined by @xmath198 .      in section  [ algorithm ] , we will describe an algorithm we refer to as `` the method of crosses and wrenches '' for finding the graph @xmath178 and the subgraphs @xmath199 . we will postpone proving the correctness of the algorithm to present applications of the theory in section  [ examples ] . in particular , we will carry out the examples of somos-4 and somos-5 and show explicitly the families of graphs associated to them . we will also show that , by choosing certain periodic functions for @xmath127 , we can create fortress graphs and families of graphs studied by chris douglass and matt blum . the number of matchings of these graphs are powers of 5 , 2 and 3 respectively , in each case we will give a rapid proof of this by induction from our main theorem . fortresses and douglass graphs are discussed in @xcite and these formulas are also proved there .    in the section  [ urban ] , we will first relate the matchings of the graphs @xmath199 to the matchings of certain infinite graphs subject to `` boundary conditions at infinity '' . this will remove the elegant property that @xmath200 when @xmath201 , but it will create objects better suited to an inductive proof . we will then prove the main theorem by varying @xmath101 and holding @xmath12 fixed . in the process , we will recover variants of the `` urban renewal''operations of @xcite .    in section  [ kuo ] , we will give a second proof , inspired by a proof of @xcite for the aztec diamond case , that works by holding @xmath101 fixed and varying @xmath12 . this proof has some additional consequences that the first proof does not . however , due to the extraordinary number of cases that would otherwise be involved , we will not check that all of the exponents work out .    in section [ final ] we make some final comments . one might wonder whether the introduction of so many families of variables is necessary to the paper . for most parts of the paper , one may think of any family variables one does not want to deal with as simply being set equal to @xmath19 without difficulty . however , there is one place where this does not work : our first proof of the main theorem is inductive and the induction only goes through if the theorem is stated with the entire family of face variables present . most of this research was done while i was working in reach ( research experiences in algebraic combinatorics at harvard ) and was aided by many helpful conversations with the other members of reach , and in particular by daniel abramson , gabriel carroll and seth kleinerman s willingness to work through many special cases with me . above all , i would like to thank jim propp for suggesting this problem and showing me much of his unpublished work on it . in this section we describe how to find the graphs @xmath178 and @xmath199 discussed above . as a running example , we we ll compute @xmath202 with @xmath203 . the goal is to predict the formula : @xmath204    the four terms in the above formula will eventually be shown to correspond to the four matchings of the shown in figure [ example ] . here the dashed edges seperate the various open faces and the graph is drawn twice so that the face and edge labels will not overlap each other . the four matchings are shown in figure [ matchings ] ; the numbers in figure [ matchings ] are the exponents of the corresponding face variables . the octahedron recurrence with these initial conditions appears section 9.4 of @xcite . a `` tropicalized '' version of our running example appears in @xcite . let @xmath205 be a height function . we describe the graph @xmath178 by describing its dual . the faces of @xmath178 ( which are all closed ) are indexed by the elements of @xmath101 and the map @xmath206 sends the face @xmath136 to @xmath207 . picture the face @xmath12 as centered at the point @xmath208 .    if @xmath107 and @xmath122 are lattice - adjacent ( i.e. @xmath209 ) then @xmath210 borders @xmath211 . in addition , if @xmath212 then @xmath213 borders @xmath211 iff @xmath214 . no other pairs of faces border and faces which border border only along a single edge . we refer to this method of finding @xmath178 as the `` method of crosses and wrenches '' because it can be describe geometrically by the following procedure : any quadruple of values @xmath215 must be of one of the following six types :    @xmath216    in the center of these squares , we draw a , or in the first and second , third and fourth , and fifth and sixth cases respectively . the diagram below displays the possible cases . @xmath217    we then connect the four points protruding from these symbols by horizontal and vertical edges . ( we often have to bend the edges slightly to make this work . kinks introduced in this way are not meant to be vertices , all the vertices come from the center of a @xmath218 or from the two vertices at the center of a @xmath219 or @xmath220 . ) we refer to the @xmath218 s as `` crosses '' and the @xmath219 s and @xmath220 s as `` wrenches '' .    in our running example , if @xmath221 then @xmath222 and we place a @xmath218 . otherwise , we get a @xmath219 . the resulting infinite graph , shown in figure [ infiniteexample ] , consists of a diagonal row of quadrilaterals seperating a plane of hexagons . we will now describe the decomposition @xmath223 and the map @xmath180 . the set @xmath195 will consist of the horizontal and vertical edges , i.e. , those separating lattice - adjacent faces . the set @xmath196 will consist of the diagonal edges , i.e. , those which come from the center of a wrench . consider any edge @xmath152 of @xmath195 . such an edge lies between two faces @xmath213 and @xmath211 with @xmath224 . without loss of generality , @xmath225 . ( otherwise , switch the names of @xmath107 and @xmath226 . ) there are four cases :    1 .   if @xmath227 and @xmath228 then @xmath229 . 2 .   if @xmath227 and @xmath230 then @xmath231 . 3 .   if @xmath232 and @xmath228 then @xmath233 . 4 .   if @xmath232 and @xmath230 then @xmath234 .    the reader may wish to refer to figure [ example ] . finally , we must describe the sub-@xmath199 of @xmath178 that corresponds to a particular @xmath12 . we will abbreviate @xmath199 by @xmath27 in this paragraph . the closed faces of @xmath27 will be @xmath235 . the edges of @xmath27 will be the edges of @xmath178 adjacent to some face in @xmath236 . the open faces of @xmath27 will be those members of @xmath101 some but not all of whose edges are edges of @xmath27 . note that every open face of @xmath27 lies in @xmath237 but the converse does not necessarily hold . note also that there are never any edges that separate two open faces ; even if those two open faces are lattice - adjacent . another way to describe the faces of @xmath27 which is more intuitive but harder to write down is that the faces of @xmath27 correspond to those @xmath238 which are used in compuing @xmath23 and the closed faces correspond to those @xmath238 which are divided by in the course of this computation .    in our running example , the closed faces are @xmath239 , @xmath240 and @xmath241 . the open faces are @xmath242 , @xmath243 , @xmath244 , @xmath245 , @xmath246 , @xmath247 and @xmath248 .      we can now give the final statement of our main theorem . for any height function @xmath127 , define @xmath178 , @xmath206 and @xmath199 by the algorithm of the previous sections . then the second statement of the main theorem holds with regard to these choices . it is easy to check that every closed face of @xmath178 has 4 , 6 or 8 sides . ( simply check all possible values for the face s eight neighbors . ) hence all of the @xmath199 are bipartite . moreover , every face has @xmath197 edges , as promised above . it is also easy to fulfill another promise and check that the unweighted edges are vertex disjoint : they lie in the middle of wrenches and do not border each other . it is clear that @xmath249 is injective ( and in fact , bijective ) . we now show :    the map @xmath180 is injective . consider an edge @xmath250 , the cases of @xmath84 , @xmath95 and @xmath96 are extremely similar . any edge with label @xmath152 must be between two faces of the form @xmath251 and @xmath252 . we must show there is at most one value of @xmath49 for which @xmath253 and @xmath252 both lie in @xmath101 . suppose , for contradiction , there are two such values : @xmath49 and @xmath254 . without loss of generality , suppose that @xmath255 . then @xmath256    but @xmath205 must change by @xmath257 when @xmath57 or @xmath58 changes by 1 , so @xmath127 can not change by this much between @xmath258 and @xmath259 , a contradiction . we now describe where the faces of @xmath260 lie in the plane . we make use of the following abbreviations and notations : we shorten @xmath260 to @xmath27 and @xmath261 to @xmath115 . recall the notation @xmath262 . so @xmath263 . let @xmath207 be a closed face of @xmath27 and let @xmath264 be such that @xmath265 is between @xmath57 and @xmath30 and @xmath266 is between @xmath58 and @xmath31 . then @xmath267 is also a closed face of @xmath27 .    without loss of generality , we may assume that @xmath268 and @xmath269 . we have @xmath270 . on the other hand , we have @xmath271 . as @xmath272 , we have @xmath273 . so the faces of @xmath27 form four `` staircases '' , as in figure  [ facelayout ] .    as a corollary , we deduce    @xmath27 is connected .    clearly , if @xmath274 and @xmath275 lie on the same closed face of @xmath27 , then @xmath274 and @xmath275 lie in the same connected component of @xmath27 . but , by the previous proposition , we can travel from any closed face of @xmath27 to @xmath276 along a sequence of lattice - adjacent faces and lattice adjacent faces have a vertex in common . thus , since every vertex of @xmath27 lies on a closed face , every vertex must lie in the same connected component as the vertices of @xmath42 . so @xmath27 is connected . it is also clear from the picture above that @xmath27 is bounded by a single closed loop . call this loop @xmath277 . divide @xmath277 , as in figure  [ facelayout ] , into four arcs by horizontal and vertical lines through @xmath276 . ( in the diagram , @xmath277 is in bold and the lines through @xmath42 are dashed . ) [ boundary ] these lines divide @xmath277 into four paths . each of these paths contains an odd number of vertices . on each of these paths , the vertices alternate between vertices all of whose neighbors in @xmath178 are inside or on @xmath277 ( and thus in @xmath27 ) and vertices all of whose neighbors in @xmath178 are outside or on @xmath277 the ends of each path are of the latter type . we consider the section of @xmath277 on which @xmath278 and @xmath279 , the other four sections are similar . for the faces @xmath38 of @xmath178 within @xmath277 ( that is the closed faces of @xmath27 ) we have @xmath280 where as for the faces which border @xmath277 on the outside ( that is , the open faces of @xmath27 ) we have @xmath281 .    our proof is by induction on the number of faces @xmath38 of @xmath27 for @xmath282 and @xmath279 . in the base case , where there is only one such face , the path in question has one vertex and the result is trivial . when there is more then one such face , we can always find a face @xmath38 such that @xmath283 and @xmath284 are outside @xmath277 . for simplicity , we describe the situation where @xmath285 and @xmath286 and leave the boundary cases to the reader . set @xmath287 . we must have @xmath288 as they are open faces of @xmath27 . we must have @xmath289 ; as @xmath290 we must have @xmath291 . if we then change @xmath205 to @xmath127 , we remove @xmath38 from within @xmath277 . there are four cases , based on whether @xmath292 and @xmath293 or @xmath294 ; figure  [ boundarychange ] shows what happens in each case . the edges of @xmath277 are drawn in bold , the faces of @xmath27 are surrounded by thin boxes and the bipartite coloring of @xmath27 is shown in black and white . we will use this proposition in the proof of proposition [ geomn ] . this proposition is also useful in testing whether it is likely that a graph can be realized through the method of crosses and wrenches . for example , the hexagonal graphs of section 6 of @xcite can not be so realized , because on their boundary there are six different boundary edges connecting vertices of degree two and a crosses and wrenches graph can only have four such edges . examples [ examples ]      we begin with an example we discussed in the introduction : the aztec diamond graphs . in this case , @xmath295 or @xmath46 when @xmath296 is @xmath9 or @xmath19 respectively . in this case , every square of four values is @xmath297 so in every case we get a cross . @xmath298 the infinite graph @xmath178 is just the regular square grid . the edge labeling is exactly as described in section [ aztecintro ] . the graphs @xmath199 are the standard aztec diamond graphs .      in this section we show that crosses and wrenches graphs are capable of reproducing several previously studied families of graphs ; the number of whose matchings are perfect powers or near perfect powers . inside each face @xmath38 , we put the number @xmath205 . most of these families of graphs appear to have first been described in print in @xcite , which we will use as our reference . fortress graphs are discussed in @xcite , section four . to obtain a fortress graph , we take @xmath299    every square of values is of the form @xmath300 so in every case we get a wrench , in the repeating pattern @xmath301    joining up the wrenches , we get the infinite graph in figure  [ fortress ] .    once again , if we set all of the variables equal to 1 , @xmath23 will count the matchings of fortresses . we must have @xmath302 and @xmath34 must obey the defining recurrence . it is easy to check that both conditions are obeyed by @xmath303 a result of @xcite . for example , figure  [ fortexamp ] shows a fortress with 25 matchings , it is of the form @xmath304 where the center square is @xmath38 and @xmath305 , @xmath306 . this fortress has 9 closed and 16 open faces . similarly , to get another family of graphs first studied by chris douglas ( see @xcite , section six ) , we take @xmath307    we now sometimes will have @xmath308 which will produce a cross and sometimes will have @xmath309 which will produce a @xmath220 . overall , we have the repeating pattern @xmath310 which produces the infinite graph in figure  [ douglass ]    again , a quick induction verifies that @xmath311    similarly , to get the graphs considered by matthew blum ( see @xcite , section 8) , take @xmath312 ( ciucu s methods require him to embed @xmath178 into the square grid , and he thus takes @xmath178 to be made of octagons and hexagons . for our purposes , it is more natural to apply lemma  [ split ] of section  [ basiclemmas ] to obtain a grid of quadrilaterals and hexagons with the same number of matchings . ) we get @xmath313    this gives us the infinite graph of figure  [ blum ] . a quick induction then shows that @xmath314      as described in the introduction , a combinatorial formula for the octahedron recurrence will give rise to a combinatorial interpretation of the somos sequences . specifically , if we set @xmath315 then the number of terms of @xmath316 will obey the somos-4 recurrence . similarly , if @xmath317 then the number of terms of @xmath316 will obey the somos-5 recurrence . figures  [ somos4 ] and [ somos4finite ] show the infinite graph and the first several finite graphs corresponding to the somos-4 recurrence . figures  [ somos5 ] and [ somos5finite ] do the same for somos-5 . it may be hard to see the periodicity of the @xmath178 for @xmath318 ; the tiles repeat as one travels five cells to the right , or one cell up and two to the right . in this section , we will prove the correctness of the crosses - and - wrenches algorithm . our basic strategy is to hold the point @xmath117 where we are evaluating @xmath34 fixed , while varying @xmath127 . our proof is by induction on the number of points in @xmath319 .      in this section , we introduce an alternative way of viewing @xmath23 as counting the number of matchings of an infinite graph , subject to a `` condition at infinity '' to be described later . this means that _ a priori _ @xmath23 could contain an infinite number of terms , although in fact it will not , and describing the terms of @xmath23 requires an _ a priori _ infinite amount of information . on the other hand , this new method will no longer require the use of open faces and will remove the need to treat faces in the boundary as a special case in our proof . we will use this interpretation in our first proof of the main theorem . let @xmath127 be a height function . fix a triple @xmath320 , we will be interested in @xmath26 . let @xmath27 be the @xmath260 . set @xmath321    it is easy to check that @xmath322 is a pseudo - height function . we can use the method of crosses and wrenches to associate an infinite graph @xmath323 to @xmath322 . note that if @xmath12 is a face of @xmath27 then @xmath324 . thus , @xmath27 is a subgraph of @xmath323 . upon removing @xmath27 , what remains looks like figure  [ infcomp ] . let @xmath325 .    ] there is a unique matching ( indicated in thick lines ) of @xmath326 given by taking the middle edge of every wrench . call this matching @xmath327 . clearly , matchings of @xmath323 that coincide with @xmath327 on @xmath326 are in bijection with matchings of @xmath27 . moreover , one can easily check that the face exponents associated to a given matching of @xmath27 are the same as for the corresponding matching of @xmath323 , including that the exponent of any face of @xmath323 that does not correspond to a face of @xmath27 is 0 . thus , we could define @xmath26 as the sum over matchings @xmath28 of @xmath323 such that @xmath28 coincides with @xmath327 on @xmath326 of @xmath56 . we claim that the following , less obvious result also holds :    let @xmath28 be a matching of @xmath323 in which all but finitely many vertices are matched to the same vertex as in @xmath327 . ( @xmath327 is a matching of @xmath326 , so for all but finitely many vertices of @xmath323 this makes sense . ) then @xmath28 coincides with @xmath327 everywhere on @xmath326 . suppose the opposite . all the vertices of @xmath328 come from wrenches . each wrench has one of its vertices closer to @xmath42 than the other ; call these the _ near _ and _ far _ vertex of the wrench . now , suppose the theorem is false . of the finite number of vertices of @xmath329 not matched as in @xmath28 , let @xmath274 be the furthest from @xmath42 . we derive a contradiction in the two possible cases . case 1 : @xmath274 is a near vertex . then the far vertex @xmath275 in the same wrench as @xmath274 is matched as in @xmath28 . but @xmath275 is matched with @xmath274 in @xmath28 , so @xmath275 is matched with @xmath274 and @xmath274 is matched as in @xmath327 . case 2 : @xmath275 is a far vertex . but all of @xmath274 s neighbors except the one it is matched to in @xmath327 are farther from @xmath42 than @xmath274 is , so they are matched as in @xmath327 and can not be matched to @xmath274 . so @xmath274 is matched as in @xmath327 .    as result , we can give another statement of the main theorem . call a matching @xmath28 of @xmath323 an acceptable matching if @xmath28 coincides with @xmath327 for all but finitely many edges . then @xmath330      [ split ] consider a @xmath27 . replace a vertex @xmath27 with two unweighted edges as in figure  [ vertsplit ] to form a new @xmath159 .        then @xmath331 . any matching of the old graph can be uniquely transformed to a matching of the new graph by adding one of the two new edges . the additional edge in the matching contributes a factor of 1 in the product of the edge variables . the two faces adjacent to the new edges have one more used edge and one more unused edge than the corresponding faces of the previous matching , so they have the same exponent . the other faces are unaffected . suppose a @xmath27 contains the sub - shown in the left of figure  [ ur ] with the indicated edge weights and face weights . ( the face weights are in uppercase , the edge weights in lower case . ) create a new graph @xmath159 by replacing this with the in the right of figure  [ ur ] where @xmath332 then @xmath333 . this theorem is related to lemma 2.5 of @xcite . however , because he does nt use face weights , ciucu s theorem involves slightly different replacements and yields a relation of the form @xmath334 . write @xmath335 where @xmath336 consists of the terms corresponding to matchings where none of the edges @xmath83 , @xmath84 , @xmath95 or @xmath96 is used , @xmath337 consists of the terms using one such edge and @xmath338 consists of the terms using two . write @xmath339 similarly . we will show that @xmath340 , @xmath341 and @xmath342 . we first give a bijection between the matchings counted by @xmath337 and those counted by @xmath343 as shown in figure  [ biject1 ] . case ]    in each case , it is easy to check that the two matchings paired off have exponent @xmath9 on @xmath344 and @xmath345 and raise all other variables to the same exponent . next , as shown in figure  [ biject0 ] , we give a bijection that associates to each matching counted by @xmath336 two of the type counted by @xmath346 . case ]    the first transformation in figure  [ biject0 ] increases the exponents of @xmath347 and @xmath348 by 1 , adds the edges @xmath83 and @xmath96 and changes the contribution of the center face from @xmath344 to @xmath349 . similarly , the second transformation increases the exponents of @xmath350 and @xmath351 by 1 , adds the edges @xmath84 and @xmath95 and changes the contribution of the center face from @xmath344 to @xmath349 . so we get from @xmath336 to @xmath346 by multiplying by @xmath352 but , as @xmath353 , this is 1 .    finally , we show @xmath342 . this is similar to the preceding paragraph . this time , we pair off every two matchings in @xmath338 with one matching in @xmath354 , as shown in figure  [ biject2 ] . case ]    in the first pairing of figure  [ biject2 ] , we delete edges @xmath83 and @xmath96 , reduce the exponents of @xmath347 and @xmath348 by 1 and replace @xmath355 by @xmath345 . in the second , we delete edges @xmath84 and @xmath95 , reduce the exponents of @xmath350 and @xmath351 by 1 and replace @xmath355 by @xmath345 . thus , we are multiplying by @xmath356 which is 1 as before . let @xmath357 and let @xmath127 and @xmath322 be as in subsection [ infext ] ; let @xmath323 be the associated to @xmath322 . our proof is by induction on @xmath358 .    if @xmath359 then @xmath360 so @xmath323 is the graph shown in figure  [ basecase ] which has only the indicated admissible matching . the matching polynomial of this matching is @xmath361 . we also have in this case that @xmath362 so we have @xmath363 .        if @xmath364 then , among the @xmath38 for which @xmath272 there is ( at least ) one with @xmath365 minimal , let this be @xmath38 . we claim that @xmath366 . we deal with the case of @xmath367 , the other three cases are similar . we have @xmath368 as @xmath322 is a pseudo - height function . if @xmath369 , then @xmath370 contradicting the minimality of @xmath38 . thus , we have shown @xmath366 . so the face associated to @xmath205 is a square . apply the urban renewal theorem to this square to create a new graph with the same matching polynomial . then apply lemma [ split ] to this graph wherever possible . the graph thus created will be the same as replacing any crosses whose vertex lies on the face @xmath38 by a wrench with one vertex on @xmath38 and _ vice versa_. also , the edge weights adjacent to @xmath38 are interchanged with their diametric opposites and the weight @xmath24 is replaced by a certain binomial . the graph thus produced is precisely the graph produced by the function @xmath371 where @xmath372 and @xmath373 everywhere else . by induction , the matching polynomial of this graph is @xmath26 for the initial conditions @xmath371 . the @xmath34 for the initial conditions @xmath127 is given by replacing @xmath24 by the same binomial as before . thus , @xmath26 is precisely given by the matching polynomial of the graph for @xmath371 with @xmath24 replaced by the said binomial , which by the urban renewal theorem is precisely the matching polynomial of the graph for @xmath127 . in this section , we give a second proof of the main theorem , similar to the proof of @xcite . in order to avoid lengthy tedious verifications , we will perform this proof with the face variables set equal to 1 throughout this section . we first give some graph theoretic notations . let @xmath27 be a graph and @xmath374 . let @xmath375 denote the elements of @xmath277 that border vertices of @xmath27 not in @xmath277 . if @xmath27 is bipartite , colored black and white , let @xmath376 denote the number of black vertices of @xmath277 minus the number of white vertices . while @xmath376 is only defined up to sign , we adopt the implicit assumption that , if @xmath377 and @xmath378 are both subsets of @xmath154 , then @xmath379 and @xmath380 are computed from the same coloring of @xmath27 . let @xmath381 be the subgraph of @xmath27 induced by @xmath277 . we abuse notation by writing @xmath382 to mean @xmath383 . ( recall that all face variables have been set equal to 1 , so @xmath382 is a polynomial in the edge variables of @xmath381 . ) the following theorem is essentially due to kuo and proven in @xcite . ( kuo s paper proves this relation for many specific families of graphs but never states the general theorem . the below is my attempt to assimilate all of kuo s cases into a general framework which will also encompass the results of this paper . ) let @xmath27 be a bipartite planar graph and let the vertices of @xmath27 be partitioned into nine sets @xmath384 assume that only vertices in the sets joined in figure  [ condense ] border each other . ( vertices may also border other vertices in the same set . ) assume further that @xmath385 and @xmath386 finally , assume that @xmath387 and @xmath388 are entirely black and @xmath389 and @xmath390 are entirely white . then we have @xmath391    we write @xmath344 to denote the collection of sets @xmath392 . let @xmath27 always denote a graph obeying the above hypotheses . we define a _ northern join _ to be a set @xmath393 of edges of @xmath27 of any of the following types    1 .   a path with one endpoint in @xmath394 , the other endpoint in @xmath395 and the intermediate vertices in @xmath396 . 2 .   a single edge with one endpoint in @xmath394 and the other in @xmath395 . 3 .   a pair of edges , one joining @xmath394 to @xmath397 and the other joining @xmath395 to @xmath397 . we define an eastern , southern or western join analogously . let @xmath28 be a multi - set of edges of @xmath27 such that every member of @xmath396 lies on two edges of @xmath28 and every other vertex lies on a single edge of @xmath28 . then we can write @xmath28 uniquely as a vertex disjoint union @xmath398 where    1 .   either @xmath399 is a northern join and @xmath400 is a southern join , or @xmath399 is a eastern join and @xmath400 is a western join . 2 .   @xmath401 is a disjoint union of cycles , entirely contained in @xmath396 . ( we count a doubled edge as a cycle of length 2 . ) @xmath402 is a vertex disjoint set of edges contained entirely within @xmath403 . since every vertex is adjacent to either one or two elements of @xmath28 , @xmath28 can be written uniquely as a disjoint union of cycles and paths . moreover , the vertices of @xmath396 are on cycles or are inner vertices of paths and the vertices of @xmath404 are the ends of paths . let @xmath401 be the cycles of @xmath28 , @xmath401 is vertex disjoint from the other edges of @xmath28 . after deleting @xmath401 , the remaining graph is a disjoint union of paths , each of whose endpoints lie in one of the @xmath405 and all of whose interior vertices must lie in @xmath396 . let @xmath402 be the isolated edges connecting one point of @xmath403 to another . after deleting all of the @xmath402 , what remains are paths as before which either have at least one interior point or whose endpoints lie in different @xmath405 . call the set of remaining edges @xmath406 . let @xmath405 . we claim @xmath407 . this is because , if @xmath408 , then there is a single edge @xmath409 of @xmath28 containing @xmath274 . we have @xmath410 by the definition of @xmath411 . then @xmath409 is also the only edge containing @xmath275 and thus @xmath409 is an isolated edge of @xmath28 lying entirely in @xmath403 . so @xmath412 and @xmath413 . we know @xmath414 contains equally many black as white vertices as it is a disjoint union of edges . thus @xmath415 has one more black vertex than white , as we assumed @xmath416 . however , we just showed @xmath417 , and @xmath387 is entirely black . so there is a unique vertex @xmath418 in @xmath415 . similarly , there are unique vertices @xmath419 , @xmath420 and @xmath421 , with @xmath418 and @xmath421 black and @xmath419 and @xmath420 white . also by the same logic , @xmath422 is even for @xmath423 . now , the @xmath424 must be endpoints of paths . the _ a priori _ possible paths are the following , and their rotations and reflections :    1 .   a path from @xmath418 to @xmath419 through @xmath396 . ( there are four possibilities in this symmetry class . 2 .   a path from @xmath418 to @xmath421 through @xmath396 . ( there are two possibilities in this symmetry class . ) 3 .   a single edge from @xmath418 to @xmath419 . ( there are four possibilities in this symmetry class . ) 4 .   a single edge from @xmath418 to @xmath425 . ( there are eight possibilities in this symmetry class . )    as @xmath426 is even , there must either be 0 or 2 paths of type ( 4 ) ending in @xmath397 , and similarly for @xmath427 , @xmath428 and @xmath429 . this means we can not have a path joining @xmath418 to @xmath421 . if such a path existed , @xmath419 could not be joined to @xmath425 or @xmath347 , as that would create one path ending in that set . also , @xmath419 could not be joined to @xmath420 , as the paths @xmath430 and @xmath431 would cross . similarly , we may not have a path joining @xmath419 to @xmath420 . so the paths of type 2 do not occur . it is now easy to see that @xmath406 must decompose either as the union of a northern and a southern join or as the union of an eastern and a western join . note that , if @xmath432 ( @xmath433 or @xmath44 ) passes through @xmath396 , it will contain an odd number of edges , as its endpoints are of opposite colors . we now prove the result . each side of the equation is a sum of products of edge variables , and each product corresponds to an @xmath28 meeting the conditions of the lemma ; we will abuse notation and call this product @xmath28 as well . we will show each @xmath28 occurs with the same coefficient on both sides . specifically , let @xmath82 denote the number of cycles in @xmath401 of length greater than 2 . we claim that @xmath28 appears on each side of the equation with coefficient @xmath434 . even more specifically , we claim that @xmath435 contains @xmath28 with coefficient @xmath434 . we also claim that , if @xmath399 is a northern join and @xmath400 a southern join , then @xmath436 contains @xmath28 with a coefficient of @xmath434 and @xmath437 does not contain @xmath28 . if @xmath399 is an eastern and @xmath400 a western join then we claim the reverse holds . consider first the task of determining how many times @xmath28 appears in @xmath435 . this is the same as the number of ways to decompose @xmath28 as @xmath438 with @xmath439 and @xmath440 matchings of @xmath27 and @xmath396 respectively . clearly , the edges with endpoints outside @xmath396 must lie in @xmath439 . this means all the edges of @xmath402 , @xmath405 , the edges of @xmath432 if @xmath432 does not pass through @xmath396 and the final edges of @xmath432 if @xmath432 does pass through @xmath396 . this forces the allocation of all the edges of @xmath432 because , when two edges of @xmath28 share a vertex , one edge must go in @xmath439 and one in @xmath440 . this forcing is consistent because @xmath432 has an odd number of edges and the end edges must both lie in @xmath439 . finally , we must allocate the edges of @xmath401 . all the cycles of @xmath401 are of even length as @xmath27 is bipartite . in a cycle of length greater than 2 , we may arbitrarily choose which half of its edges came from @xmath439 and which from @xmath441 . thus , we make @xmath434 choices . next , consider the coefficient of @xmath28 in @xmath436 . we must similarly write @xmath442 we claim that if @xmath399 is an eastern join and @xmath400 a western , this coefficient is 0 . there are three cases . @xmath399 is a path joining @xmath394 to @xmath443 through @xmath396 . then every edge of @xmath399 must lie in @xmath444 or in @xmath445 and which of these two it lies in must alternate . there are an odd number of edges in @xmath399 , so the final edges must lie in the same one of these two sets . but any edge with an endpoint in @xmath394 must lie in @xmath444 and any edge with an endpoint in @xmath443 must lie in @xmath446 . @xmath399 is a single edge with endpoints in @xmath394 and @xmath443 . but none of the @xmath447 s can contain such an edge . @xmath399 is a union of two disjoint edges , one connecting @xmath394 to @xmath427 and one connecting @xmath443 to @xmath427 . but neither of these edge types can lie in any of the four @xmath447 s . finally , we show that if @xmath399 is a northern join and @xmath400 a southern join that @xmath28 has coefficient @xmath434 in @xmath436 . as before , the edges of @xmath402 , @xmath405 , are uniquely allocated to one of @xmath444 , @xmath445 , @xmath448 and @xmath449 . if @xmath432 does not pass through @xmath396 , its edges are also immediately forced . if @xmath432 does pass through @xmath396 , its final edges are forced , thus forcing the others and again we have consistency as the two final edges are in the same set and @xmath432 has an odd number of edges . finally , each cycle of @xmath401 of length greater than 2 can be allocated in two ways . the case of @xmath437 is exactly analogous . let @xmath27 be a graph arising from the method of crosses and wrenches for some height function @xmath127 and some @xmath450 . the purpose of this section is to describe a decomposition of the vertices of @xmath27 into nine disjoint sets . in the next section , we will show these sets obey the hypotheses of the previous section . for simplicity , we assume that @xmath451 . note that we have @xmath452 and @xmath453 ( recall that @xmath154 denotes the vertices of @xmath27 . ) thus , the four graphs @xmath454 and @xmath455 intersect as shown in the venn diagram in figure [ partition ] , where the unlabelled cells indicate empty intersections . we decompose @xmath456 into the nine sets @xmath396 , @xmath397 , @xmath394 , @xmath427 , @xmath443 , @xmath428 , @xmath457 , @xmath429 and @xmath395 as shown in the figure we now verify that the sets of vertices @xmath396 , @xmath397 , @xmath427 , @xmath429 , @xmath428 , @xmath394 , @xmath395 , @xmath443 and @xmath457 obey the hypotheses of the condensation theorem . we also show that @xmath458 , @xmath459 , @xmath460 , @xmath461 . these clearly establish the main theorem . the following lemma is clear . [ ineq ] abbreviate @xmath462 by @xmath463 . then @xmath464 ( we are using our simplifying assumption that @xmath465 to avoid a messy statement for this face . )    [ geomn ] we have @xmath458 , @xmath459 , @xmath460 and @xmath461 and @xmath466 . also , all of the vertices of @xmath427 that border vertices of @xmath394 are the same color . calling this color white , the vertices of @xmath397 bordering @xmath394 , those of @xmath429 bordering @xmath457 and those of @xmath428 bordering @xmath457 are white . the vertices of @xmath427 bordering @xmath443 , those of @xmath428 bordering @xmath443 , those of @xmath397 bordering @xmath457 and those of @xmath429 bordering @xmath457 are black . we do the case of @xmath427 , the others are similar . let @xmath467 and let @xmath38 be a closed face of @xmath468 bordering @xmath274 ( by the definition of @xmath427 , such a face exists ) ; by lemma  [ ineq ] , @xmath469 . now , @xmath38 is not a closed face of @xmath470 . thus , by lemma  [ ineq ] , @xmath471 . but , similarly , @xmath279 so @xmath472 . moreover , the faces that @xmath274 borders which are not of the form @xmath473 must not lie in @xmath27 at all , so we have @xmath474 .    putting this data into the crosses and wrenches algorithm , we have that @xmath427 looks like figure  [ elayout ] , where the number of hexagons and the length of the dangling path can vary . the highlighted vertices are those that border @xmath394 and @xmath443 .    ] clearly , @xmath427 has a unique matching @xmath28 , shown in bold . let @xmath57 be the largest value for which @xmath473 is a closed face of @xmath27 , the only weighted edge in @xmath28 is the edge separating @xmath473 and @xmath475 . as @xmath476 and @xmath477 ( as otherwise @xmath478 we be a closed face ) we see that this is the edge @xmath479 . as @xmath427 has a matching , @xmath480 . all that is left to show is that the vertices of @xmath397 that border @xmath394 and the vertices of @xmath427 that do are the same color . it is equivalent to show that the vertex of @xmath481 and that of @xmath482 closer to @xmath394 are the same color . but the path joining them is the one we proved in proposition [ boundary ] had an odd number of edges . let @xmath483 . then exactly one of the following is true .    1 . @xmath274 lies in a wrench oriented ne - sw ( i.e. , this orientation : @xmath219 ) , the other end of which is also in @xmath394 . + or 2 . @xmath274 lies on the outer perimeter of @xmath260 . let @xmath38 , @xmath283 , @xmath284 , @xmath484 be the faces surrounding @xmath274 ( @xmath274 may only be adjacent to three of them ) and let @xmath485 be the set of these four faces .. by lemma  [ ineq ] , either @xmath57 or @xmath486 so @xmath282 . similarly , @xmath279 . there are several cases . first , suppose @xmath469 . then @xmath487 for @xmath488 . if @xmath489 for all @xmath488 , then @xmath274 lies on a ne - sw wrench both ends of which are in @xmath394 . if some @xmath490 then @xmath491 is not a closed face of @xmath260 and one can check that in every case @xmath274 is adjacent to @xmath491 , so @xmath274 is on the outer perimeter .    now , suppose that @xmath492 . then @xmath493 . the only way that @xmath274 could be in @xmath427 then is if @xmath274 were at the ne end of a ne - sw wrench so that it did nt border @xmath38 . then @xmath283 does border @xmath274 , so @xmath494 . the only way this is possible is if @xmath495 , @xmath496 and @xmath497 . then @xmath498 and @xmath274 lies on @xmath484 , so again @xmath274 is on the perimeter . finally , suppose that @xmath499 . then @xmath500 for all @xmath488 . but then none of the @xmath267 are closed faces of @xmath260 and @xmath274 is not a vertex of @xmath260 , a contradiction . @xmath394 and @xmath457 have one more black vertex than white , and _ vice versa _ for @xmath443 and @xmath395 . we discuss the case of @xmath394 , the others are similar . pair off all of the vertices of @xmath427 for which the first case of the previous proposition holds with the other end of their wrench . this removes equal numbers of black and white vertices . what remains is a path , which we showed in proposition  [ geomn ] has each end black . @xmath387 and @xmath388 are entirely black and _ vice versa _ for @xmath390 and @xmath389 . moreover , only the adjacencies permitted by the hypotheses of the condensation theorem can occur . besides the endpoints of the path in the previous proposition , @xmath387 must be made up entirely of vertices from the wrenches in the previous proposition . however , in fact , only the south - west vertex of a wrench will be able to lie in @xmath387 , and these are all the same color . this deals with the coloration of the boundaries . this immediately means that @xmath394 can not border @xmath457 . we saw in lemma  [ geomn ] that @xmath394 only borders @xmath397 and @xmath427 . these and the symmetrically equivalent restrictions gives the required restrictions on what may border what . @xmath396 has equally many black and white vertices . @xmath501 . by induction on @xmath29 , we can assume that we already know that @xmath502 . in particular , @xmath396 has at least one perfect matching . we have now checked all of the conditions to apply the kuo condensation theorem . the condensation proof of the main theorem , although it involves more special cases , seems to have at least one consequence which does not follow from the urban renewal proof .    in the relation @xmath503 each monomial appearing on the right hand side appears in exactly one of the two terms on the right , and appears with the coefficient @xmath434 for some @xmath82 . this just says that every combination of edge @xmath28 as in the proof of the kuo condensation theorem occurs either only in @xmath504 or only in @xmath505 and appears with coefficient @xmath434 for some @xmath82 ; this follow from the proof of the kuo condensation theorem . we are being asked to show that we can recover a matching of @xmath182 ( henceforth , @xmath27 ) from knowing which weighted edges were use in the matching . since the unweighted edges of @xmath27 are vertex disjoint , knowing which weighted edges are used determines all the edges used , and hence the matching . we are now being asked to show that we can recover a matching @xmath28 of @xmath27 from just knowing the face exponents . by the previous result , it is enough to show that we can determine whether or not a weighted edge appears in @xmath28 . recall the notation of section  [ gwofs ] : for @xmath34 a face of @xmath178 , @xmath506 is the exponent of @xmath162 and , for @xmath152 an edge of @xmath178 , @xmath507 is the exponent of @xmath152 . we give a formula for @xmath508 in terms of certain @xmath506 s in the case where @xmath152 is of the form @xmath509 , similar formulas for @xmath510 , @xmath511 and @xmath512 can be found and will be stated later in the section . my thanks to gabriel carrol for suggesting this simple formulation and proof of the lemma ( in a somewhat different context . ) now , let us consider the coefficient of @xmath515 in any term of @xmath528 . since @xmath513 appears in @xmath182 , we must have @xmath529 and @xmath530 . thus , @xmath531 and no @xmath515 appears . on the other hand , @xmath516 can also be obtained from @xmath34 by substituting @xmath532 for @xmath24 for every @xmath136 such that @xmath533 and @xmath534 and substituting @xmath535 for @xmath536 . so we see that the exponent of @xmath515 is @xmath537              1 . @xmath510 , if we define @xmath541 , @xmath542 , @xmath543 and @xmath277 by comparing @xmath544 to @xmath545 . @xmath511 , if we define @xmath541 , @xmath542 , @xmath543 and @xmath277 by comparing @xmath546 to @xmath547 . @xmath512 , if we define @xmath541 , @xmath542 , @xmath543 and @xmath277 by comparing @xmath548 to @xmath549 . a geometrical description can be given for these rules . let @xmath152 be a weighted edge of @xmath27 . draw four paths in @xmath27 by starting at @xmath152 and alternately turning left and right . ( there are two ways to leave @xmath152 and two choices for which turn to make first . ) these divide the faces of @xmath27 into four regions @xmath541 , @xmath542 , @xmath543 and @xmath277 . if the edge @xmath152 is present , then the sums @xmath550 , @xmath551 , @xmath552 and @xmath553 will yield a 1 , two -1 s and a 0 . if @xmath152 is absent , one of these sums will be 1 and the other three will be 0 . interestingly , if one follows the operation of the previous where @xmath152 is an unweighted edge , one gets precisely the same conclusions except that the interpretation of the results is changes : getting the sums @xmath554 ( in some order ) now means that @xmath152 is _ present _ and @xmath555 means @xmath152 is _ let @xmath27 be a bipartite connected planar graph with a fixed labeling of its vertices as black and white and let @xmath275 be a function assigning a real number to each edge of @xmath27 . we define a _ propp height _ to be a function @xmath556 from the faces of @xmath27 to the real numbers with the following property : let @xmath34 and @xmath557 be faces of @xmath27 separated by an edge @xmath152 such that , when one stands on @xmath34 and looks toward @xmath557 , the white vertex of @xmath152 is on the left . then @xmath558 . define two propp heights @xmath556 and @xmath559 to be equivalent if @xmath560 for some constant @xmath95 independent of @xmath34 . ( the term propp height is my own , to distinguish them from the heights which occur through out this paper . )      for @xmath27 as above , one can find @xmath275 such that there is a bijection between equivalence classes of propp heights for @xmath275 and matchings of @xmath27 . the bijection is such that , if @xmath556 corresponds to @xmath28 , the edge @xmath152 occurs in @xmath28 iff @xmath561 where @xmath152 separates @xmath34 and @xmath557 . these propp heights have been very useful in studying statistical properties of random matchings , see _ e.g. _ @xcite . for crosses and wrenches graphs , the propp height has an extremely simple description . let @xmath178 be a crosses and wrenches graph . we may take @xmath275 in the previous theorem to be given by @xmath562 , if @xmath152 is a horizontal or vertical edge and @xmath563 , if @xmath152 is a diagonal edge . let @xmath27 be a crosses and wrenches graph . suppose that we want to randomly generate a matching of @xmath27 , with our sample drawn from all matchings of @xmath27 with uniform probability . such sampling has produced intriguing results and conjectures in the cases of aztec diamonds and fortresses . it is possible to do so in time @xmath566 , where @xmath567 can be any of @xmath568 , @xmath569 or @xmath570 as all of these only differ by a constant factor for @xmath27 a crosses and wrenches graph . more specifically , if @xmath571 , one can do so in time @xmath572 . ( in most practical cases , this is closer to @xmath573 . we give only a quick sketch ; the method is a simple adaptation of the methods of @xcite . let @xmath571 arise from a height function @xmath127 and let @xmath574 . throughout our algorithm , @xmath131 will denote a function @xmath575 . our algorithm takes as input @xmath127 and @xmath131 and returns a random matching , where the probability of a matching @xmath28 being returned is proportional to @xmath576 . we describe our output as a list of the weighted edges used in @xmath28 . at the beginning of the algorithm , we take @xmath577 for all @xmath34 .            * step 5 : * for shorthand , set @xmath589 , @xmath590 , @xmath591 and @xmath592 . if @xmath588 contains one of @xmath593 , return m and halt . if @xmath588 contains two of @xmath593 , return @xmath594 and halt . if @xmath588 contains none of @xmath593 , return @xmath595 with probability @xmath596 and return @xmath597 with probability @xmath598 . all other cases are impossible .    in order to not do a time consuming search at step 2 , one can keep a reverse look - up table which , given @xmath127 , record all @xmath38 with @xmath599 and is updated in step 3 when @xmath127 is replaced by @xmath322 . note that @xmath600 will always be integer valued
we study a recurrence defined on a three dimensional lattice and prove that its values are laurent polynomials in the initial conditions with all coefficients equal to one . 
 this recurrence was studied by propp and by fomin and zelivinsky . 
 fomin and zelivinsky were able to prove laurentness and conjectured that the coefficients were 1 . 
 our proof establishes a bijection between the terms of the laurent polynomial and the perfect matchings of certain graphs , generalizing the theory of aztec diamonds . in particular 
 , this shows that the coefficients of this polynomial , and polynomials obtained by specializing its variables , are positive , a conjecture of fomin and zelevinsky .