Holly Hunter | VSO ConvertXtoDVD 7.0.0.36 + Patch | Temporada 10

Combinatorics of hard particles on planar graphs

Combinatorics of hard particles on planar graphs

Nuclear Physics B 655 [FS] (2003) 313–341 www.elsevier.com/locate/npe Combinatorics of hard particles on planar graphs J. Bouttier, P. Di Francesco, ...

415KB Sizes 0 Downloads 5 Views

Nuclear Physics B 655 [FS] (2003) 313–341 www.elsevier.com/locate/npe

Combinatorics of hard particles on planar graphs J. Bouttier, P. Di Francesco, E. Guitter Service de Physique Théorique, CEA/DSM/SPhT, Unité de recherche associée au CNRS, CEA/Saclay, 91191 Gif sur Yvette Cedex, France Received 12 November 2002; accepted 20 January 2003

Abstract We revisit the problem of hard particles on planar random tetravalent graphs in view of recent combinatorial techniques relating planar diagrams to decorated trees. We show how to recover the two-matrix model solution to this problem in this purely combinatorial language.  2003 Elsevier Science B.V. All rights reserved. PACS: 02.10.Eb; 05.50.+q; 04.60.Nc

1. Introduction Recent progress has been made in the enumeration of various types of planar maps, using bijective methods relating maps to decorated trees [1–4]. These techniques are different in nature from the original combinatorial approach of Tutte [5–8] and are much easier to generalize. In particular, it was shown in Ref. [9] how to extend these techniques so as to recover in a purely combinatorial way the general one-matrix model solution for the enumeration of planar maps with arbitrary valencies [10–12]. After these encouraging results, it is natural to turn to more involved problems of decorated map enumeration, and try to recover in a purely combinatorial way the results of more involved matrix models describing statistical “matter” models defined on random graphs1 (two-dimensional quantum gravity). It is worth mentioning that there is an apparent obstruction to this type of generalization, as the local interactions on the graphs become non-local on the corresponding trees. On the other hand, the known matrix model E-mail addresses: [email protected] (J. Bouttier), [email protected] (P. Di Francesco), [email protected] (E. Guitter). 1 We use the denomination “graph” throughout this paper to denote maps, i.e., fatgraphs in the physics language. 0550-3213/03/$ – see front matter  2003 Elsevier Science B.V. All rights reserved. doi:10.1016/S0550-3213(03)00058-0

314

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 1. A sample configuration of hard particles on a planar tetravalent graph. Empty (resp., occupied) vertices are indicated by white (resp., black) circles. The particle exclusion rule imposes that no two occupied vertices are adjacent to the same edge.

solutions strongly suggest by their algebraic form that a simple combinatorial approach to these problems should exist. The scope of this paper is to analyze a particular two-matrix model case, namely, that describing hard particles on tetravalent planar graphs. The configurations of this model are made of arbitrary tetravalent planar maps with empty or occupied vertices, satisfying the hard-particle exclusion rule that no two occupied vertices may be adjacent to the same edge. Such a configuration is represented in Fig. 1 for illustration. This model was solved in Ref. [13] by use of a two-matrix model representation. We show here how to recover the solution of Ref. [13] for the generating function of these objects in a purely combinatorial manner, by establishing suitable bijections between configurations of the model and trees with particles. The techniques used here are directly borrowed from those of Ref. [9], generalizing that of Ref. [1]. The paper is organized as follows: In Section 2, we recall the results of Ref. [13] and introduce various types of objects for which we give closed formulas of the generating functions. Of particular interest are two-leg and four-leg diagrams as defined below, whose enumeration allows in particular to obtain the generating function for all the configurations of hard particles on tetravalent planar maps. In Section 3, we describe in detail the cutting procedure transforming two-leg diagrams into decorated trees which we characterize precisely. The correspondence is proved to be one-to-one by studying the inverse gluing procedure. We finally use this bijection to enumerate the two-leg diagrams at hand. Section 4 is devoted to the more involved case of four-leg diagrams, the enumeration of which is performed through several steps organized in several subsections. Section 5 discusses an interesting duality property between empty and occupied vertices of the model. We gather a few concluding remarks in Section 6. The combinatorial counterpart of the more general two-matrix models describing bipartite graphs is briefly discussed in Appendix A.

2. Results Let us first recall the two-matrix model solution of Ref. [13] to the hard-particle model on random planar tetravalent graphs. The planar free energy F , i.e., the generating function

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

315

••

Fig. 2. Examples of two- and four-leg diagrams contributing to 2•• (a), 2•◦ (b) and 4•• (c). Our convention is to always choose for the external face that containing the external legs.

for configurations of hard particles on connected planar tetravalent (fat)graphs, was derived and expressed in terms of two functions R and V determined by the following system of equations R = 3V 2 + 9zRV 2 ,

V = θ + R + 3zR 2 + 3zV 3 ,

(2.1)

with the condition that V = θ + O(θ 2 ), where θ is the weight per (empty or occupied) vertex and z the fugacity per particle. A more suitable quantity for a combinatorial interpretation is the generating function for the same configurations with a marked oriented edge, E = 4θ dF /dθ , where the prefactor 4 stands for the four possible choices of an edge from a vertex. Indeed, as opposed to the case of the free energy, the marking of an edge suppresses all symmetry factors and leaves us with a plain enumeration problem. Moreover, it proves convenient to also consider generating functions for diagrams with distinguished (empty or occupied) univalent vertices (legs) all adjacent to the same (external) face. More precisely, let us introduce the two- and four-point functions 2•◦ , ••

2•• , 4•• counting, respectively, two- and four-leg diagrams with the following external univalent vertices: two occupied (••), one occupied and one empty (•◦) and four occupied •• ( •• ). Examples of such diagrams are depicted in Fig. 2. For convenience, we attach a √ weight θ to each external univalent vertex as opposed to the weight θ per inner vertex. We also decide not to attach a factor z to the occupied legs as opposed to the inner occupied vertices. The generating function E is expressed through 22•◦ − 2•• − 2θ (2.2) θ by simply considering all possible configurations of the two vertices adjacent to the marked oriented edge (see Fig. 3) The two- and four-leg diagrams are further related via E=

••

2•◦ = θ + 2•• + z4••

(2.3)

according to the configuration of the vertex connected to the empty external vertex in a diagram of 2•◦ (see Fig. 4). The aim of this paper is to provide a combinatorial interpretation for the functions R and V as generating functions for decorated trees and to derive in a purely combinatorial

316

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 3. Schematic representation of diagrams contributing to E, 2•• and 2•◦ according to the empty or occupied nature of the vertices adjacent to the marked edge or external legs. Upon cutting the marked edge in the top line into two external legs, Eq. (2.2) is obtained.

••

Fig. 4. Schematic representation of diagrams contributing to 2•• , 4•• and 2•◦ according to the empty or occupied nature of the vertices adjacent to the external legs. Upon erasing the occupied vertex on the right of the second line, Eq. (2.3) is obtained.

manner the following expressions for two- and four-point functions V 3 + zR 3 + 6zRV 3 , θ zV 6 + RV 3 + zR 4 + 7R 2 V 3 , = V 3 + 2R 2 − 3 θ

2•• = R − ••

4••

(2.4) (2.5)

which immediately lead to compact expressions for 2•◦ via Eq. (2.3) and finally E via Eq. (2.2). These relations may alternatively be derived within the framework of the twomatrix model of Ref. [13] but without any clear combinatorial interpretation yet.

3. Two-leg diagrams In this section we address the simplest case of two-leg diagrams with both legs occupied, generated by 2•• . As in Ref. [9], we will construct a correspondence between these diagrams and suitably decorated trees whose enumeration leads to a combinatorial interpretation of R and V as defined through Eq. (2.1), and to the formula (2.4) for 2•• .

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

317

Fig. 5. The cutting of a two-leg diagram contributing to 2•• into a tree according to the rules explicated in the text. The edges of the diagram are visited in counterclockwise direction starting from the incoming external leg (top vertex). After one turn, those edges marked in (a) have been cut into bud-leaf pairs. Buds (resp., leaves) are represented by black (resp., white) arrows. The procedure is repeated a second (b) and third (c) time until no edge may be cut anymore. The desired tree is obtained (d) by replacing the external legs by leaves.

3.1. Cutting procedure: from diagrams to trees 3.1.1. Iterative algorithm Starting from a two-leg diagram with both legs occupied, distinguished as in- and out-coming ones, we apply the following edge-cutting algorithm. Starting from the incoming leg, we successively visit all edges and vertices adjacent to the external face in counterclockwise direction. At each step, the visited edge is cut iff (i) the remaining diagram is not disconnected, and (ii) the next visited vertex is empty. Each cut edge is split into a pair of half-edges to which we attach respectively a black and a white label (represented by arrows in Fig. 5), and that we refer to from now on as a bud (half-edge with a black label) and a leaf (half-edge with a white label). Note that the bud is attached to the vertex visited prior to the edge, while the leaf is attached to the next one. This has the effect of merging a number of faces with the external one. The procedure is then iterated on the new (cut) diagram and stops when all faces have been merged. Indeed, the particle exclusion rule ensures that no unmerged face can remain: if such faces existed, among the edges separating the external face from unmerged ones, at least one would point to an empty vertex in counterclockwise direction, clearly contradicting the cutting process. Finally, we replace the two univalent vertices by leaves. An explicit example of this procedure is depicted in Fig. 5. 3.1.2. Equivalent cutting procedure via leftmost minimal paths Alternatively, the above cutting algorithm may be expressed in a dual language by introducing the notion of leftmost minimal paths defined as follows. A path {e} between two faces f and f is a sequence of edges e1 , e2 , . . . , ek , where ei is adjacent to two faces fi−1 and fi , with f0 = f , fk = f (it is also clearly a path drawn on the dual diagram

318

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 6. Equivalent cutting procedure of the diagram of Fig. 5, by use of leftmost minimal paths. These are oriented paths of minimal length connecting the external face to all the other faces. When crossing an edge, the vertex on the right has to be empty. When several minimal paths to a given face exist, we choose the leftmost one with respect to the incoming leg.

between the corresponding dual vertices). We further impose the orientation constraint that, when going from fi−1 to fi across ei , the vertex on the right of ei is empty. Such a path between any two given faces always exists as, by virtue of the exclusion rule, any edge with an occupied vertex to its right may be bypassed to the right, hence crossing only edges with an empty vertex to their right. A minimal path between two given faces f and f is such a path with minimal length k. Let us now fix the external face f0 as origin. Two minimal paths {e} and {e } from f0 to any given face f may be compared by examining the mutual position (left or right) of their first differing edge ei = ei with respect to the previous one ei−1 = ei−1 (with the convention that e0 is the incoming edge): {e} is said to lie on the left (resp., right) of {e } if (ei−1 , ei , ei ) appear in clockwise (resp., counterclockwise) order around fi−1 (with the opposite convention for the external face f0 due to the planar representation with a point at infinity). This total order on minimal paths from f0 to f allows to define the leftmost minimal path from f0 to f . It is easily seen that all the edges belonging to leftmost minimal paths are those to be cut in the above cutting algorithm, as illustrated in Fig. 6. Indeed, any edge ei of a leftmost minimal path {e} is cut during the ith step of the cutting algorithm, thus merging the face fi with the external one (among the edges separating fi from fi−1 , ei is the first edge encountered in counterclockwise order at step i). Note that the leaf is attached to the (empty) vertex on the right of ei when going from fi−1 to fi . Conversely, given in the two-leg diagram a face fi merged at step i by cutting an edge ei , the leftmost minimal path from f0 to fi is inductively given by appending ei to the leftmost minimal path from f0 to fi−1 (the face separated from fi by ei ). 3.2. Characterization of the resulting trees The aim of this section is to show that the trees resulting from the cutting procedure of previous section satisfy the following properties:

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

319

Fig. 7. An example of configuration of buds and leaves around an inner edge e in the tree resulting from the cutting procedure. The edge e separates the tree into two parts T1 and T2 , with T1 containing the former incoming leg (IN). In the original diagram, e separates two faces f and f . The leftmost minimal paths from the external face f0 to these faces are {e} = (e1 , e2 , e3 ) and {e } = (e1 , e2 , e3 , e4 ), respectively (with the former lying on the left of the latter), which are cut edges during the procedure. In the case depicted here, the former outcoming leg (OUT) belongs to T1 , which is necessarily the case when {e} and {e } have some common edges (here e1 = e1 ).

(UR1) These trees are made of tetravalent empty or occupied regular vertices, inner edges satisfying the hard-particle exclusion rule, and two kinds of endpoints (univalent vertices): leaves and buds. (UR2) No leaf is connected to an occupied vertex. (UR3) Attaching a charge +1 to leaves and −1 to buds, the total charge of the trees is +2. (UR4) Cutting any inner edge separates the trees into two pieces such that a piece starting with an empty vertex has a non-negative total charge. Such trees will be called unrooted R-trees. Properties (UR1) and (UR2) follow clearly from the iterative cutting algorithm. Attaching a charge +1 to leaves and −1 to buds, it is also clear that the total charge is +2 (UR3), as leaves and buds appear in pairs, except for the two leaves replacing the former legs. We are left with the task of proving (UR4). As an illustration, the reader may check (UR4) on the tree of Fig. 5(d). Let us consider an inner edge e of a tree obtained by cutting a two-leg diagram  as above. This edge separates the tree into two parts T1 , T2 where say T1 contains the former incoming edge. We denote by f and f the two faces adjacent to e, and by e1 , e2 , . . . , ek and e1 , e2 , . . . , ek their respective leftmost minimal paths from the external face f0 . Without loss of generality, we assume that {e} is on the left of {e }, as defined above by comparing the position of their first differing edges e = e (ei = ei , i = 0, 1, 2, . . . ,  − 1). As apparent from Fig. 7, this amounts to assuming that when going from f to f across e, T1 is on the left. Starting again from the original two-leg diagram , we may equivalently first cut the edges e , e+1 , . . . , ek and e , e+1 , . . . , ek . The edge e now clearly separates the diagram ˜ ˜ into two pieces T1 and T2 , which after completing the cutting algorithm turn into T1 and T2 respectively. The completion of the algorithm consists in only cutting edges within T˜1 or T˜2 (in particular, the cutting of the common edges e1 , e2 , . . . , e−1 only affects T˜1 ), hence the corresponding bud-leaf pairs do not contribute to the total charge of either piece,

320

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 8. A schematic proof of the characterization (UR4) stating that any piece of tree starting with a white vertex has a non-negative charge. The edge e separates the tree into two parts T1 and T2 where T1 contains the former incoming leg. Among T1 and T2 , we can pick one starting with an empty vertex. The different cases correspond to the positions of both the former outcoming leg and the selected empty vertex. The charges of T1 and T2 depend on k and k , namely the lengths of the minimal paths from the external face to the faces adjacent to e, as explained in the text. The condition of leftmost minimal paths yields constraints on the respective values of k and k as indicated in the figure, which in turn translate into the desired constraint on the charge of the selected piece.

i.e., q(Ti ) = q(T˜i ), i = 1, 2. As the edges e , e+1 , . . . , ek are replaced by buds in T˜1 and leaves in T˜2 , while e , e+1 , . . . , ek are replaced by buds in T˜2 and leaves in T˜1 , the total charges read respectively q(T1 ) = 1 +  + (k −  + 1) − (k −  + 1) = 1 +  + k − k and q(T2 ) = (1 − ) + (k −  + 1) − (k −  + 1) = 1 −  + k − k , where  = 1 if the former outcoming leg lies in T1 and  = 0 if it lies in T2 . We now turn to the inspection of the various possible environments around the edge e. The particle exclusion rule implies that at least one part T1 or T2 starts with an empty vertex. Picking such an empty vertex, we are left with the four possible cases depicted in Fig. 8, where the first two cases (a)–(b) correspond to  = 1 while the last two (c)–(d) correspond to  = 0. For each case, we have also indicated with an arrow a possible way of crossing e which implies restrictions on the values of k and k as e does not belong to a leftmost minimal path. In cases (a) and (c), we have k  k + 1, otherwise the minimality condition would be violated by allowing for a shorter path to f from f0 passing through f and crossing e. In cases (b) and (d), we have k  k + 1 by a similar minimality argument, but moreover, k = k + 1 is forbidden by the leftmost condition. All these restrictions turn into lower bounds for the charge q of the piece attached to the selected empty vertex. In all cases, we find that q is necessarily non-negative, from which (UR4) follows. To conclude this section, note that the condition (UR4) above may be equivalently replaced by the apparently stronger condition: (UR4 ) Cutting any inner edge separates the trees into two pieces of charges (+1, +1) or (−1, +3), the piece of charge −1 always starting with an occupied vertex. To see this equivalence, we first remark that since the pieces at hand are trees with only tetravalent inner vertices, viewing buds, leaves and the half-edge obtained by cutting the inner edge as external legs, their total number of legs #(buds) + #(leaves) + 1 is necessarily even, hence their total charge #(leaves)−#(buds) is odd. As the total charge of the unrooted R-tree is +2, the only possible cases are (+1, +1) or (−(2m − 1), 2m + 1), m = 1, 2, . . . ,

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

321

Fig. 9. Proof of the equivalence of (UR4) and (UR4 ) for tetravalent trees, as explained in the text. If m  2, one of the q’s has to be  3 and the complementary part has negative charge and starts with an empty vertex, in contradiction with (UR4).

the piece of charge −(2m − 1) necessarily starting with an occupied vertex, while that of charge 2m + 1 starts with an empty one. Let us now show that only m = 1 is allowed. By contradiction, assume m  2. As shown in Fig. 9, cutting the empty vertex leaves us with four pieces of odd charges (1 − 2m), q1 , q2 , q3 , such that q1 + q2 + q3 = 2m + 1  5. This implies that at least one of the q’s say qi  3, hence the complementary piece both has negative charge 2 − qi  −1 and starts with an empty vertex, in contradiction with (UR4). 3.3. Inverse gluing procedure: from unrooted R-trees to two-leg diagrams 3.3.1. Gluing procedure We have proved in the previous section that cutting a two-leg diagram with both legs occupied yields an unrooted R-tree. Let us now show that the correspondence is one-to-one between two-leg diagrams with two distinguished occupied legs and unrooted R-trees with a marked leaf at depth 0 as defined below. Starting from an unrooted R-tree, let us iteratively connect each bud to the nearest available leaf in counterclockwise direction around the tree so as to form edges in such a way that the resulting graph is planar (see Fig. 10 for an example). This procedure is clearly unique and leaves us with exactly two unmatched leaves, which are given the depth 0. The edges obtained by bud-leaf connections form two systems of arches separated by the two unmatched leaves, each bud and leaf receives the depth of the corresponding arch, starting with depth 1 for external arches. Replacing the marked unmatched leaf with the incoming occupied leg and the other unmatched one with the outcoming occupied leg, we end up with a planar two-leg diagram with empty and occupied vertices which clearly satisfy the hard-particle exclusion rule. Indeed, the rule is obviously satisfied along inner edges of the original tree, while for the new edges it follows from the property (UR2) above that leaves are only connected to empty vertices. 3.3.2. Proof that gluing is the inverse of cutting It remains to be shown that the gluing procedure is the inverse of the cutting algorithm of the previous section. First let us note that cutting a two-leg diagram into a tree and

322

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 10. Inverse procedure: gluing back the tree of Fig. 5(d) brings back the original two-leg diagram of Fig. 5(a) by identifying the unmatched (depth 0) leaves with the external legs. One of these must be chosen as the incoming leg.

connecting the tree’s bud-leaf pairs according to the gluing prescription clearly brings back the original diagram. We are left with the task of proving that conversely gluing an unrooted R-tree into a two-leg diagram and applying the cutting algorithm brings back the original unrooted R-tree. This boils down to showing that the bud-leaf pairs of any unrooted R-tree form the edges of the leftmost minimal paths from the external face to the inner faces of the diagram obtained by connecting them. More precisely, let us start with an unrooted R-tree T , and its associated two-leg diagram  by bud-leaf connection. Let T further denote the unrooted R-tree obtained by cutting : we want to show that T = T . Noting that T and T have the same number of inner edges (= number of inner vertices − 1), and therefore the same number of bud-leaf pairs (= number of inner edges in  − number of inner edges in T or T ), it is sufficient to show that the inner edges of T cannot belong to leftmost minimal paths of  (which would otherwise be cut into a bud-leaf pair in T ). Assume by contradiction that some leftmost minimal paths of  contain some inner edges of T . We pick such a path {e} to the face f with minimal length k. Obviously e1 , e2 , . . . , ek−1 correspond to bud-leaf pairs of T , while ek is one of its inner edges. Let T1 and T2 denote the pieces of T separated upon cutting ek , and such that the marked (unmatched) leaf belongs to T1 . We introduce as usual the quantity  = 1 or 0 according to whether the other unmatched leaf of T is in T1 or T2 . Let  finally denote the “depth” of f in T , namely, that of the bud-leaf pair whose connection closes the face f when gluing T into . The generic situation is depicted in Fig. 11, according to whether T1 lies on the left (Fig. 11(a)) or right (Fig. 11(b)) when going to f across ek . In the case (a), the edges e1 , e2 , . . . , ek−1 originate from buds of T1 , the first r of which are connected to leaves of T1 (encircling T2 ), while the remaining k − 1 − r are connected to leaves of T2 . Note that r = 0 necessarily when  = 0. In the case (b), these edges terminate at leaves of T1 , the first r of which originate from buds of T1 (encircling T2 ), while the remaining k − 1 − r originate from buds of T2 (with again r = 0 if  = 0). The total charge of T2 in case (a) reads q(T2 ) = (1 − ) + (k − r − 1) − ( − r) = (k − ) − .

(3.1)

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

323

Fig. 11. Justification of the inverse gluing procedure. As explained in the text, we assume by contradiction that some inner edge ek in an unrooted R-tree belongs to a leftmost minimal path {e} in the diagram constructed by the gluing procedure. Assuming that the value of k is minimal, we are in either situation (a) or (b) depending on the position of the former incoming leg. As explained in the text, the leftmost minimal condition implies bounds on the charges of T1 and T2 which, because of (UR4), are in contradiction with the orientation rule for minimal paths.

The minimality of {e} implies that   k, and as   0, the charge (3.1) is negative or zero, therefore, it must be −1 (from the condition (UR4 ) characterizing unrooted R-trees), but this in turn implies that the vertex on the right of ek is occupied, contradicting the orientation constraint of minimal paths. We are left with case (b), in which the total charge of T1 reads q(T1 ) = 1 +  + (k − 1) −  =  + k − .

(3.2)

Again, the minimality condition imposes that   k, but the leftmost condition further eliminates the case  = k, hence  > k and as   1 the charge (3.2) is negative or zero, therefore it must be −1 again, and the vertex on the right of ek is occupied, contradicting the orientation constraint of minimal paths. In all cases, we have found a contradiction, henceforth proving the desired statement that T = T . 3.4. Enumeration via rooted trees By virtue of the bijection established in Sections 3.1, 3.2 and 3.3 above, the computation of 2•• translates into the enumeration of unrooted R-trees. It is a general fact that rooted trees are naturally simpler to enumerate, as they can be generated recursively. Such trees are naturally oriented from the root to their endpoints, with an obvious notion of descending subtrees. 3.4.1. Rooted R-trees In this section, we first consider rooted R-trees, defined as unrooted R-trees with a distinguished leaf replaced by a neutral (charge zero) root. A rooted R-trees is entirely characterized by the following properties:

324

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

(R1) This tree is a ternary rooted tree with empty and occupied inner vertices, inner edges obeying the particle exclusion rule and with two types of endpoints: buds and leaves. (R2) No leaf is connected to an occupied vertex and the root is connected to an empty vertex. (R3) Attaching the charge +1 to leaves and −1 to buds as well as 0 to the root, the total charge of this tree is +1. (R4) Any descending subtree starting with an occupied vertex has total charge +1 or −1, while any descending subtree starting with an empty vertex has total charge +1 or +3, the latter moreover descending necessarily from an occupied ancestor vertex. These properties are clearly implied by the characterization (UR1)–(UR4 ) of unrooted R-trees. Conversely, given a tree satisfying (R1)–(R4), we replace the root by a leaf of charge +1. The resulting tree clearly satisfies the properties (UR1)–(UR3). Moreover, when cutting an inner edge, the formerly descending subtree either starts with an occupied vertex and has charge +1 or −1 (from (R4)), in which case the complementary part starts with an empty vertex and has charge +1 or +3, respectively, or starts with an empty vertex and has charge +1 or +3 (from (R4)), in which case the complementary part has charge +1 or both has charge −1 and starts with an occupied vertex (as ancestor of a descending subtree of charge +3). In all cases, (UR4) is satisfied. 3.4.2. More rooted trees As a first consequence of the characterization (R1)–(R4) of rooted R-trees, we note that their descending subtrees of charge +1 starting with an empty vertex are themselves rooted R-trees. The three other types of subtrees are rooted trees of a different nature, which will be called W-trees (charge +3, starting from an empty vertex), X-trees (charge +1, starting from an occupied vertex) and Y-trees (charge −1, starting from an occupied vertex). As for rooted R-trees, these other trees are all characterized by similar properties, respectively, (W1)–(W4), (X1)–(X4), (Y1)–(Y4), where (W1) = (X1) = (Y1) = (R1), (W4) = (X4) = (Y4) = (R4), with the obvious modifications of (R2) for the nature of the vertex attached to the root, namely, (W2) = (R2) and (X2) = (Y2). No leaf is connected to an occupied vertex and the root is connected to an occupied vertex, and with the obvious modifications of (R3) for the total charge, namely, (X3) = (R3) and (W3) Attaching the charge +1 to leaves and −1 to buds as well as 0 to the root, the total charge of this tree is +3. (Y3) Attaching the charge +1 to leaves and −1 to buds as well as 0 to the root, the total charge of this tree is −1. 3.4.3. Generating functions All descending subtrees of R, W, X, Y-trees not reduced to single buds or leaves are themselves R, W, X, Y-trees. We introduce the generating functions R, W, X, Y for the corresponding objects, with now a weight θ per leaf and z per occupied vertex. Moreover,

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

325

Fig. 12. Pictorial representation of the recursive relations (3.3) and (3.4) obtained by listing all possible environments of the starting vertex in each type of tree. The introduction of V-trees, namely, all rooted trees of charge 1 (i.e., single leaves, R- or X-trees), although redundant, is useful for the compactness of relations (3.4).

it proves convenient to introduce the function V = θ + R + X,

(3.3)

which generates V-trees, namely, all possible subtrees of charge +1 (including single leaves). The generating functions for our trees satisfy the following recursive relations: R = 3V 2 + 3V 2 Y,

W = V 3,

X = 3zR 2 + 3zW,

Y = 3zR,

(3.4)

obtained by listing all possible environments of the starting vertex of each type of tree, as depicted in Fig. 12. Eliminating W, X, Y , we end up with Eq. (2.1) relating R, V , θ and z. This allows, therefore, to interpret the function R of Eq. (2.1) (as obtained from Ref. [13]) as the generating function for the rooted R-trees and V as that of the V-trees defined above. 3.4.4. Local environments within unrooted R-trees To make an even tighter connection between on one hand unrooted R-trees and on the other hand all rooted trees defined above, we note that these rooted trees are precisely the pieces obtained when reading an unrooted R-tree in any direction from one of its inner vertices or inner edges. This property allows to characterize the local environment of any inner edge or vertex within an unrooted R-tree, as depicted in Fig. 13. It is easily seen

326

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 13. A listing of all possible local environments in an unrooted R-tree for (a) an occupied vertex, (b) an empty vertex and (c) an inner edge. In (a), the first three cases differ by the cyclic order of the subtrees around the occupied vertex at hand.

that properties (UR1)–(UR4 ) imply that only the depicted cases are obtained. Conversely, given one of these local environments, the resulting tree clearly obeys (UR1)–(UR3), and (UR4 ) may be checked by considering one of its inner edges, say e. This edge may either belong to the local environment itself (edges depicted in the figure) or be within one of the rooted subtrees. In the first case, (UR4 ) is directly apparent from the figure, while in the second case, one of the pieces originating from e is a subtree of the rooted tree at hand, and we use the characterization (R1)–(R4) (and their modifications) for all rooted trees to check that (UR4 ) is satisfied. 3.4.5. Computation of 2•• So far we have obtained the generating functions for rooted trees. Let us now make the connection with the generating function of unrooted R-trees, and eventually with 2•• . We note first that the weight θ per leaf in a rooted tree of charge q is equivalent to a weight θ per inner vertex times an overall weight θ (q+1)/2 by virtue of Euler’s relation for tetravalent graphs. In the case of rooted R-trees (q = 1), this coincides precisely √ with our previous convention for 2•• with a weight θ per inner vertex, times a weight θ for each of the two external legs. To identify the generating function 2•• , recall that the two leg diagrams with both legs occupied are in one-to-one correspondence with unrooted R-trees with a marked leaf at depth 0. The depth 0 leaves are precisely those not matched with a bud, hence 2•• is equal to the difference between the generating function of unrooted R-trees with a marked leaf (i.e., rooted R-trees) and that of unrooted R-trees with a marked bud. The former generating function is nothing but R. Examining all possible local environments of buds in Fig. 13, the latter generating function reads (V 3 + zR 3 + 6zRW )/θ , where the overall factor 1/θ has been tuned to match the weight prescription for 2•• . Eq. (2.4) follows.

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

327

As a side remark, we note that the relation between unrooted R-trees with a marked leaf at depth 0 and rooted R-trees is 2-to-(n + 1), where n denotes the number of leaves in the rooted R-tree. Indeed, in the unrooted R-tree, each of the (n + 1) leaves may serve as roots for a rooted R-tree, but only two of them have 0 depth.2 This is a manifestation of the notion of conjugacy of trees introduced in Ref. [1], which translates into the relation    2 ••  R  , n  2, 2 θ n = (3.5) n + 1 θn where the subscript θ n refers to the coefficient of θ n in the corresponding functions. This relation can be also verified directly by checking that d(θ 2•• )/dθ = 2R, using Eqs. (2.4) and (2.1).

4. Four-leg diagrams ••

We now turn to the enumeration of four-leg diagrams contributing to 4•• by adapting the cutting procedure defined above. We start with a four-leg diagrams with occupied external legs labeled by, say, 1, 2, 3 and 4 in counterclockwise cyclic order. Note that such a four-leg diagram may be either connected, or made of two (connected) two-leg diagrams. In the latter case, the connected end-points are either (1-2) and (3-4) or (1-4) and (2-3). This translates into the relation   •• •• •• + 2  •• 2 , 4•• = 4c (4.1) 2 ••

•• denotes the generating function for connected four-leg diagrams with occupied where 4c external legs. From now on, we will consider the case of connected diagrams only.

4.1. Cutting procedure To use the cutting procedure of the previous section, we first connect the legs 2 and 3, erasing the associated occupied univalent vertices. The result is a two-leg diagram with external legs 1 and 4 and with a distinguished edge such that (i) it connects two inner white vertices, (ii) it is adjacent on one side only to the external face, (iii) it lies between 1 and 4 in counterclockwise order around the external face. The correspondence is clearly one-to-one. Now we proceed by applying the cutting procedure to the two-leg diagram, choosing 1 for the incoming leg. Two situations may occur: (a) the distinguished edge is cut and replaced by a bud-leaf pair, or (b) it remains uncut. These situations are depicted in Fig. 14. 2 In the case of an accidental half-turn symmetry of the unrooted R-tree (which is the only possible symmetry), the correspondence is rather one-to-(n + 1)/2.

328

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 14. The cutting of the two-leg diagram (with external legs 1 and 4) constructed by gluing the legs 2 and 3 of a connected four-leg diagram into an edge e. This edge is either cut and replaced by a bud-leaf pair (a) or remains uncut (b). In the latter case, it separates the tree resulting from the cutting into two pieces T1 and T2 where: T1 contains both legs 1 and 4, exactly one bud of T1 is connected to a leaf of T2 as shown, and no bud of T2 is connected to a leaf of T1 .

In case (a), we can transfer the marking of the distinguished edge into the marking of the associated bud. We end up with an unrooted R-tree with a distinguished bud connected to a white vertex and of depth 1. We denote by R◦− the generating function for such 1 objects. Conversely, given an unrooted R-tree with such marking, the gluing procedure clearly gives rise to a two-leg diagram with a marked edge with properties (i) as the leaf connected to the marked bud necessarily originates from a white vertex from (UR2), (ii) from the depth 1 criterion, and (iii) by choosing the incoming and outcoming legs 1 and 4 appropriately among the two leaves of depth 0. In the case (b), the distinguished edge separates the resulting unrooted R-tree into two pieces T1 and T2 , with T1 containing the former external leg 1. From condition (i) for the distinguished edge, those pieces are rooted R-trees as shown in Fig. 13(c). Moreover, the condition (ii) ensures that there is exactly one bud in T1 matched to a leaf in T2 , and no bud in T2 is matched to a leaf in T1 . The charge constraint for rooted R-trees shows that the two unmatched leaves both lie in T1 , in the position depicted in Fig. 14(b). Cutting finally the distinguished edge and replacing it by a leaf on each side, we end up we two unrooted R-trees, one with a marked leaf at depth 1 (corresponding to T1 ) and one with a marked leaf at depth 0 (corresponding to T2 ). The generating function of these objects − − is R− denotes the generating function of unrooted R-trees with 0 × R1 , where Rk a marked leaf of depth k. Conversely, given two such marked trees and connecting the marked leaves into an edge, we get an unrooted R-tree with a marked edge which upon the gluing procedure produces a two-leg diagram with a distinguished edge satisfying (i), (ii) and (iii) by choosing the incoming and outcoming legs 1 and 4 appropriately. We end up with the following relation: ••

•• = R◦− + R− × R− . 4c 1 0 1 ••

(4.2)

•• therefore reduces to the enumeration of unrooted R-trees with The computation of 4c suitable markings.

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

329

4.2. Computation of R◦− via rooted trees 1 4.2.1. Unrooted W-trees We now turn to the precise calculation of R◦− 1 . As a preliminary remark, we note that replacing the marked bud by a root in any tree contributing to R◦− yields a rooted W-tree 1 as apparent from Figs. 12 and 13(b), since the marked bud is by definition connected to an empty vertex. Replacing the root by a leaf produces an unrooted W-tree of total charge +4 with a marked leaf. The characterization of unrooted W-trees is somewhat more subtle than that (UR1)–(UR4) of unrooted R-trees. In particular, not all the leaves of the unrooted tree may lead, when replaced by roots, to a rooted W-tree. We call admissible the leaves actually leading to rooted W-trees. The set of admissible leaves will be characterized precisely in the next section. The depth 1 constraint on the formerly marked bud now translates into the fact that the (admissible) marked leaf in the unrooted W-tree has depth 0 when performing the bud-leaf matching directly in the unrooted W-tree. Note that in an unrooted W-tree there are exactly four depth 0 leaves. Unfortunately, in general, not all of them are admissible. We may still write = 0 × W (0) + 1 × W (1) + 2 × W (2) + 3 × W (3) + 4 × W (4), R◦− 1

(4.3)

where W (i) , i = 0, 1, 2, 3, 4, is the generating function for unrooted W-trees with exactly i admissible leaves of depth 0 (necessarily connected to an empty vertex as part of the definition of W-trees). 4.2.2. Admissible leaves and the core of unrooted W-trees As a tool to characterize admissible leaves, we now come to the definition of the core of an unrooted W-tree. Starting from an unrooted W-tree, let us (i) first mark all edges separating the tree into pieces of charge +1 and +3, in which the piece of charge +1 starts with an empty vertex, (ii) then cut all these marked edges and replace them by a leaf (on the charge +3 side) and a bud (on the other side). The resulting object is a set of disconnected pieces, all of which have charge 0 except one, which has charge +4, and which we will call the core of the unrooted W-tree. Indeed, picking an admissible leaf and replacing it by a root, the edges marked at step (i) above are the root edges of descendent R-subtrees, as there are no descendent subtrees of charge +3 with an empty ancestor vertex in a rooted W-tree. At step (ii) above, all these descendent R-subtrees acquire a charge 0 and are amputated from their own R-subtrees, acquiring a charge 0 as well. The only remaining connected component is that containing the selected admissible leaf of the unrooted W-tree and has total charge +4. As the procedure (i)–(ii) was defined independently of a choice of admissible leaf at hand, this shows, moreover, that all admissible leaves lie in the core. It remains to show the converse, namely that all the leaves of the core are admissible. Note first that all trees not reduced to buds or leaves attached to the core are rooted R-trees, which we call maximal R-subtrees. Let us show that all inner edges of the core separate

330

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 15. The core of an unrooted W-tree is obtained by cutting all edges adjacent to a piece of charge +1 starting with an empty vertex (indicated by parallel double-lines). Replacing these cut edges by bud-leaf pairs with a leaf on the charge +3 complementary side, the core is the only connected component with total charge +4. It is indicated here in thick lines. The pieces connected to the core are either leaves, buds or maximal R-subtrees (circled in the figure).

the tree into a piece of charge +3 starting with an empty vertex, and one of charge +1 starting with an occupied one. One of these two pieces is a descendent subtree of the rooted W-tree hence as such is either an X-subtree or a W-subtree as R-trees have been cut out from the core and Y-trees only occur as subtrees of maximal R-subtrees as readily seen in Fig. 12. The other piece has the complementary charge (+3 and +1, respectively) and starts with an empty vertex in the first case according to the particle exclusion rule, or with an occupied vertex in the second case as the ancestor of a W-subtree. We are now ready to show that replacing a leaf in the core by a root produces a rooted tree obeying (W1)–(W4). Properties (W1)–(W3) are obviously satisfied. To show (W4), consider any descendent subtree not made of a single bud or leaf. Two situation may occur. Either it is contained in an R-subtree, in which case we use the property (R4) of the R-subtree to ensure that the subtree at hand meets the criteria of (W4). Or it originates from an edge in the core, in which case we use the above property of the inner edges of the core to again meet the criteria of (W4). To conclude this section, the unrooted W-trees may be viewed as cores to which are attached leaves, buds or maximal R-subtrees (see Fig. 15 for a typical example). When replacing the maximal R-subtrees by a new type of endpoint which we call R-leaves, the cores of unrooted W-trees satisfy the following properties: (C1) These are trees made of tetravalent empty or occupied inner vertices, and three kinds of endpoints: leaves, buds and R-leaves; (C2) No leaf is connected to an occupied vertex;

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

331

(C3) Attaching a charge +1 to leaves and R-leaves and −1 to buds, the total charge is +4; (C4) Cutting any inner edge separates the cores into two pieces: one of charge +3 starting with an empty vertex, and one of charge +1 starting with an occupied vertex. In particular, (C4) is stronger than the hard-particle exclusion as it ensures that empty and occupied vertices alternate (bipartite tree). 4.2.3. Unrooted C-trees The properties (C1)–(C4) of previous section define a new type of unrooted trees obtained by replacing R-leaves by arbitrary rooted R-trees. These objects are called unrooted C-trees. These are more general than unrooted W-trees. Indeed, our construction of unrooted W-trees from rooted ones implicitly assumes the existence of admissible leaves, which in turn implies that the core contains at least one leaf. This constraint is not implied by (C1)–(C4), and an unrooted C-tree may have no leaf in its core. The absence of such a constraint in unrooted C-trees makes them easier to deal with. We may rewrite Eq. (4.3) in terms of C-trees as well upon introducing the generating functions C (i) , i = 0, 1, 2, 3, 4, for unrooted C-trees with exactly i depth 0 leaves in the core, namely = 0 × C (0) + 1 × C (1) + 2 × C (2) + 3 × C (3) + 4 × C (4) R◦− 1

(4.4)

as we clearly have C (i) = W (i) for i = 0. As in the case of unrooted W-trees, the notion of core of an unrooted C-tree is unambiguous as it can be recovered from the whole tree (completed with maximal R-subtrees) by the procedure (i)–(ii) of Subsection 4.2.2. In particular, the enumeration of unrooted C-trees will boil down to that of their cores. 4.2.4. Enumeration of unrooted C-trees The enumeration of unrooted C-trees is performed by noting that in the core there are four more leaves or R-leaves than buds. The generating function C of unrooted C-trees reads  1 − C = C − + C ® − C − , (4.5) 4 where C − , C −® , C − denote the generating function for unrooted C-trees with respectively a marked leaf in the core, a distinguished maximal R-subtree and a marked bud in the core. These are computed by examining the local environment of a vertex in the core of an unrooted C-tree, depicted in Fig. 16(a)–(b). One may easily check that properties (C1)– (C4) imply that only the depicted cases are possible. Conversely, given one of these local vertex environments, we construct the core by applying the procedure (i)–(ii) of Subsection 4.2.2: let us consider an edge e cut in the procedure and show that the piece not containing the vertex at hand is an R-subtree. The edge e may either be connected to the vertex itself (edge depicted in Fig. 16) or be within one of the rooted subtrees depicted. The first case is easily worked out by inspecting Fig. 16(a)–(b), while the second case requires the use of the characterizations (R1)–(R4) for R-trees and their modified versions for W, X, Y-trees to show that an R-subtree not containing the vertex at hand is cut out.

332

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 16. Local environment in the core of an unrooted C-tree for (a) an empty vertex (b) an occupied vertex (c) an inner edge. In case (a) we have decomposed one of the attached V-trees to display a leaf and a maximal R-subtree.

As in Subsection 4.2.2, we end up with cut out pieces of charge 0, and a unique piece of charge +4, containing the vertex at hand, which is the core. The properties (C1)–(C4) follow immediately. By inspection in Fig. 16 of all possible environments of leaves, maximal R-subtrees and buds in the core of an unrooted C-tree, we find C − = V 3 = W, C − =

R(V 3 + 6zRW + zR 3 ) − , C ®= θ

3zW 2 + 3zR 2 W , θ

(4.6)

leading to    3zV 6 + 3zR 2 V 3 1 R 3 3 3 3 V + 6zRV + zR − C= V + . 4 θ θ

(4.7)

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

333

••

•• 4.2.5. Calculation of 4c  (i) In terms of the C , the generating function C is expressed as C = 4i=0 C (i) , hence using Eqs. (4.2) and (4.4), we have  4  •• − − (i) •• . 4c = 4C − (4.8) (4 − i)C − R0 R1 i=0

We will now show that 4 

− (4 − i)C (i) − R− 0 R1 =

i=0

2 2 3 V + 6zRV 3 + zR 3 2 θ

(4.9)

 by identifying 4i=0 (4 − i)C (i) with the generating function of unrooted C-trees with a marked leaf of depth 0 not in the core, i.e., in a maximal R-subtree, and by examining the resulting constraints on this R-subtree. Together with Eqs. (4.7) and (4.8), this finally yields (V 3 + 6zRV 3 + zR 3 )2 RV 3 + 3zR 2 V 3 + zR 4 − 3zV 6 −2 , (4.10) θ θ2 and Eq. (2.5) follows from Eq. (4.1).  To prove Eq. (4.9), we first note that the quantity 4i=0 (4 − i)C (i) enumerates unrooted C-trees with (i) a distinguished maximal R-subtree and (ii) a marked depth 0 leaf within this subtree. Introducing the generating functions C −® i , i = 0, 1, 2, 3, 4, for unrooted C-trees with a distinguished maximal R-subtree containing exactly i depth 0 leaves, we have ••

•• = V 3 + 4c

4  i=0

(4 − i)C (i) =

4 

− i C ®i .

(4.11)

i=0

We will now proceed in two steps. In a first step we characterize unrooted C-trees with a distinguished maximal R-subtree, and in a second step we exhaust all possible cases according to the number of depth 0 leaves in the maximal R-subtree. Starting from an unrooted C-tree with a distinguished maximal R-subtree, we cut the edge connecting it to the core, and replace it by a leaf on the side of the R-subtree and a bud on the side of the core. We have clearly on the first side an unrooted R-tree with a marked leaf, while on the other side we get an unrooted R-tree with a marked bud. This last point is readily seen by replacing in Fig. 16 any R-subtree by a bud and checking that the resulting environment is one of Fig. 13, characterizing unrooted R-trees. Conversely, given any two unrooted R-trees with respectively a marked leaf and a marked bud, connecting them by their marked ends yields an unrooted C-tree whose core contains the vertex attached to the former marked bud: this is again checked by inspecting the possible local environments of this vertex in Figs. 13(a)–(b) and 16(a)–(b). We are now ready to compute the number of depth 0 leaves in the distinguished maximal R-subtree. Given an unrooted C-tree with a distinguished maximal R-subtree, that we split as above into two marked unrooted R-trees, the number i of depth 0 leaves in the distinguished maximal R-subtree is determined by the respective depths of the marked leaf and bud in the two unrooted R-trees. The list of all possible cases is depicted in Fig. 17 and

334

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 17. Schematic representation of unrooted R-trees with, respectively, a marked leaf of depth k (contributing − to R− k ) and a marked bud of depth l (contributing to Rl ). Gluing the marked leaf and bud into an edge leads to an unrooted C-tree with a distinguished maximal R-subtree. The number of depth 0 leaves in this R-subtree (left piece) is (a) 0 if k  l − 2, (b) 1 if k = l − 1 (c) 2 if k = l (d) 3 if k = l + 1 and (e) 4 if k  l + 2.

translates into the following equations:  − − C ®0 = R− k Rl , kl−2

 − − C ®1 = R− k Rl , k=l−1

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

335

 − − C ®2 = R− k Rl , k=l

 − − R− C ®3 = k Rl , k=l+1

 − − C ®4 = R− k Rl ,

(4.12)

kl+2

and R− denote the generating functions for unrooted R-trees with, where R− k l respectively, a marked leaf of depth k and a marked bud of depth l. These two functions are related, as leaves of depth k  1 are matched bijectively with buds of the same depth, hence − − − •• R− k = Rk for k  1. When k = 0, R0 = 0, while R0 = 2 as a consequence of the bijection established in Section 3. This allows for a drastic simplification of Eq. (4.11) 4 

  2 − − R− i C ®i = R− +2 l−1 Rl l

i=0

l1

+3



l1 − R− l+1 Rl

l1

=2

 

R− l

+4



− R− l+m Rl

l1 m2

2

− + R− 0 R1 ,

(4.13)

l1 − comes from the l = 1 term in the first sum. Noting finally where the extra term R− 0 R1   − = R − 2•• = (V 3 + 6zRV 3 + zR 3 )/θ from that k0 Rk = R, we have l1 R− l Eq. (2.4), and Eq. (4.9) follows.

5. Empty-occupied duality ••

So far we have calculated 2•• , 4•• , hence 2•◦ via Eq. (2.3), which is enough to ◦◦

calculate E via Eq. (2.2). Other quantities of interest are 2◦◦ and 4◦◦ counting respectively the two- and four-leg diagrams with now empty external legs. The latter is easily identified with ◦◦

4◦◦ = 2•◦ − θ

(5.1)

◦◦

Fig. 18. Schematic representation of diagrams contributing to 2◦◦ , 4◦◦ and 2•◦ . Upon erasing the empty vertex in the second term contributing to 2•◦ , Eq. (5.1) follows.

336

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

as depicted in Fig. 18. There is, however, no such simple expression for 2◦◦ . To compute it, we note that we can implement a different (dual) iterative cutting algorithm to produce a tree by changing the rule (ii) of Subsection 3.1.1 into (ii ) the previously visited vertex is empty. This creates a new type of trees where no bud is connected to an occupied vertex ˜ called unrooted R-trees. Repeating the analysis of Section 3, we are also naturally led ˜ V, ˜ W, ˜ X, ˜ Y-trees ˜ to consider new types of rooted trees called R, with the same charges as their untilded counterparts, but with the opposite empty/occupied nature of the starting ˜ X, ˜ Y-trees ˜ vertices for W, as opposed to W, X, Y-trees. The generating functions for these new trees satisfy the relations ˜ V˜ = θ + X, W˜ = zV˜ 3 ,

R˜ = V˜ + 3zY˜ V˜ 2 , ˜ Y˜ = 3R,

X˜ = 3R˜ 2 + 3W˜ ,

(5.2) ˜ Y˜ , we corresponding to the recursive constructions depicted in Fig. 19. Eliminating W˜ , X, arrive at R˜ = V˜ + 9zR˜ V˜ 2 ,

V˜ = θ + 3R˜ 2 + 3zV˜ 3 .

(5.3) ˜ ˜ ˜ Eqs. (5.3) are equivalent to Eqs. (2.1) upon writing R = 3V R and V = V , and may also be extracted from the matrix model solution of Ref. [13]. It is quite remarkable that V = V˜

Fig. 19. Pictorial representation of the recursive relations (5.2).

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

337

has two very different combinatorial interpretations according to the choice of cutting ˜ procedure. Indeed, it may now be viewed as the generating function for rooted R-trees starting with an empty vertex or reduced to a leaf. It can be shown that this property actually results from the suitable application of the two different cutting procedures on the same set of two-leg diagrams with one occupied and one empty leg, non necessarily lying in the same face. Finally, repeating the steps of Sections 3 and 4 above, we find 2◦◦ = R˜ −

˜ 3 R˜ 3 + 6zRV θ

(5.4)

and ◦◦

4◦◦ = zV 3 + 2R˜ 2 − 3

z2 V 6 + R˜ 4 + 7zR˜ 2 V 3 θ

(5.5)

in agreement with Eq. (5.1). The existence of two different cutting procedures is a manifestation of the duality induced by the scalar product of the underlying two-matrix model (see Appendix A for more details).

6. Conclusion In this paper, we have shown how to recover the matrix model results of Ref. [13] in a purely combinatorial way, by use of a bijection between configurations of hard particles on tetravalent planar graphs and suitable trees. As a first concluding remark, we note that our construction is very similar to that used in Ref. [9], where arbitrary rooted planar maps were enumerated. Indeed, comparing respectively the one- and two-leg diagrams (respectively, generated by 1 and 2 ) of Ref. [9] to the two- and four-leg diagrams of the present paper, we first note that the unrooted trees in bijection with diagrams contributing to 2•• have a simple notion of conjugacy with all their leaves admissible as was the case for diagrams contributing to 1 . •• On the other hand, the notion of conjugacy for diagrams contributing to 4•• requires the introduction of the notion of the core of the corresponding trees, as was also the case when dealing with diagrams contributing to 2 . Moreover, the various steps used to enumerate the diagrams are exactly parallel in both cases. In particular, the notion of charge introduced in Ref. [9] is a crucial ingredient for characterizing the balance between buds and leaves within the trees. The hard-particle model studied here is a special instance of the more general class of enumeration problems solvable by a two-matrix model. The techniques introduced here are easily transposed to this larger class of problems. We discuss this generalization in Appendix A where we make the connection between the two-matrix model formalism and the (suitably generalized) quantities used throughout this paper. As a last remark, the other models solved in Ref. [13] by matrix techniques, namely, hard particles on bicolourable graphs or multicritical versions thereof (with weaker exclusion rules) should be also amenable to purely combinatorial interpretations as well.

338

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Note While completing the writing of this paper, we noticed the appearance of a paper [14] with a similar combinatorial approach to the solutions of the hard-particle and Ising model on tetravalent planar graphs and with an important overlap with our present work.

Appendix A. Relation between the two-matrix model formalism and the combinatorial approach Let us first comment on the relation between the planar solution of the two-matrix model for hard particles (Section 2.2 of Ref. [13]) and the approach of the present paper. In Ref. [13], the solution goes through the introduction of a family of bi-orthogonal polynomials (Eq. (2.3) of Ref. [13]) whose norms determine the all genus partition function through Eq. (2.4) of Ref. [13]. These norms may be computed via algebraic properties of bi-orthogonal polynomials, introducing in particular the operators Q1 and Q2 describing multiplications by eigenvalues. These have finite expansions (Eqs. (2.10) of Ref. [13]) in terms of the “shift” operators acting on the polynomials, and obey the “master equations” (Eqs. (2.7) of Ref. [13]) which follow from the scalar product at hand. The planar limit corresponds to the asymptotics at large polynomial degree. In this limit, and upon suitable rescalings, the operators Q1 and Q†2 read explicitly Q1 = σ + Rσ −1 + W σ −3 ,

Q†2 = V σ −1 +

W˜ R˜ σ + 3 σ 3, V V

(A.1)

where σ is a (commuting) dummy variable inherited from the shift operator, allowing to keep track of the degree of the various operators at hand, and Q†2 is the adjoint of Q2 . In our language, the coefficients of Q1 and Q†2 of the various powers of σ become generating functions for charged trees, the charge being directly given by the corresponding power of σ −1 . The operators Q1 and Q†2 are related algebraically, thus implying graded relations between their coefficients (Eqs. (2.13) of Ref. [13] with S → W and S˜ → W˜ ). In the combinatorial language, this means that the trees obey recursive relations in which the charge is conserved. The above degree properties are generic in matrix models solvable by orthogonal polynomial techniques. Let us discuss in particular the case of two-matrix models with potential U(A, B) = AB − U (A) − U˜ (B), U (A) =

k  i=1

A2i gi , 2i

U˜ (B) =

k  i=1

g˜i

B 2i 2i

(A.2)

describing in the planar limit bipartite graphs with arbitrary even vertex valencies and a weight gi (resp., g˜i ) per black (resp., white) 2i-valent vertex, i = 1, 2, . . . , k. In this case,

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

339

the operators Q1 and Q†2 read in the planar limit Q1 = σ +

k  Ri , σ 2i−1

V  R˜ i + σ 2i−1 . σ V 2i−1 k

Q†2 =

i=1

(A.3)

i=1

In the combinatorial language, using again the cutting procedure of Sections 2 and 3 (with the convention white = empty and black = occupied) for the two-leg diagrams with two black endpoints, we generate bipartite unrooted R1 -trees of charge +2, with leaves (resp., buds) only connected to white (resp., black) vertices, whose leaves are all admissible, and whose rooted versions have charge +1, start with a white vertex, and are generated by R1 . The subtrees of rooted R1 -trees are rooted trees that either start with a white vertex and have charges 1, 3, . . . , 2k − 1, or with a black vertex and have charges 1, −1, −3, . . ., −(2k − 3). The former are generated by R1 , R2 , . . . , Rk respectively, while the latter are generated by V − θ , X1 , X2 , . . . , Xk−1 , where Xi = R˜ i /V 2i−1 and θ is a weight per leaf. These functions are nothing but the coefficients of Q1 (for white starting vertex) and Q†2 (for black starting vertex). Note that the leading coefficients of Q1 and Q†2 are trivial, with in particular Xk = gk standing for the only tree of charge −(2k − 1) starting with a black vertex, made of 2k − 1 descending buds. All these trees obey recursive relations which may immediately be obtained by listing all possible vertex descendents (chosen among buds, leaves and rooted trees in the above list) allowed by charge conservation and bipartite character. In the matrix language, these relations read     θ δm,−1 = Q†1 − U˜ (Q2 )  θ δm,−1 = Q†2 − U (Q1 )  , (A.4) m

m

for m  −1. In the above equations, the notation |k stands for the coefficient of σ k in the corresponding expression. It is important to notice that the charge restrictions on the above rooted trees translate into the characterizing property for unrooted R1 -trees that cutting any edge separates the tree into two pieces of charges (1, 1), (−1, 3), . . . , or (−(2k − 3), 2k − 1), the piece of positive charge starting with a white vertex. We may then obtain the generating functions for 2i-leg diagrams. For instance, the twoi−1 (resp., four- and six-leg diagrams with all-black or all-white legs, with weights √ gi θ i−1 g˜i θ ) per 2i-valent black (resp., white) vertex and an extra weight of θ per leg, are, respectively, generated by: U (Q1 )|−3 , θ U (Q1 )|−5 + 3R1 U (Q1 )|−3 , = R2 + 2R12 − θ

2•• = R1 − ••

4••

•••

6••• = R3 + 6R1 R2 + 5R13 U (Q1 )|−7 + 5R1 U (Q1 )|−5 + (3R2 + 9R12 )U (Q1 )|−3 , θ U˜ (Q1 )|−3 2◦◦ = R˜ 1 − , θ −

340

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

Fig. 20. Correspondence between the generating functions in the general bipartite case and in the tetravalent hard-particle case. Note that wiping out the two-valent black vertices relaxes the bipartite constraint into the hard-particle one. ◦◦ U˜ (Q1 )|−5 + 3R˜ 1 U˜ (Q1 )|−3 4◦◦ = R˜ 2 + 2R˜ 12 − , θ ◦◦◦  ◦◦◦ = R˜ 3 + 6R˜ 1 R˜ 2 + 5R˜ 3 1

6

U˜ (Q1 )|−7 + 5R˜ 1 U˜ (Q1 )|−5 + (3R˜ 2 + 9R˜ 12 )U˜ (Q1 )|−3 . − θ •···•

(A.5)

◦···◦

The collection of generating functions 2i•···• or that of 2i◦···◦ for i = 1, 2, . . . , k is required to get the generating function for the corresponding rooted maps (with no legs), which reads E=

2•◦ − θ , θ

2•◦ = θ +

k  i=1

•···•

gi 2i•···• = θ +

k 

◦···◦

g˜i 2i◦···◦ ,

(A.6)

i=1

where the equations for diagrams with all-white legs result from an alternative cutting procedure using (ii ) the next visited vertex is black. Note finally an obvious black/white duality in which A ↔ B, Q1 ↔ Q2 , gi ↔ g˜ i , and Ri ↔ R˜ i . The case of hard particles on tetravalent graphs is recovered in this language by setting k = 2, g1 = 1, g˜1 = 0 g2 = θ z, g˜ 2 = θ , and by wiping out the bivalent black vertices so as to build direct edges between white tetravalent vertices (in this case the condition (ii ) becomes (ii ) of Section 5). We have in this case the correspondence R1 → R, R3 → W , X1 → 1 + Y and V → V displayed in Fig. 20. References [1] G. Schaeffer, Bijective census and random generation of Eulerian planar maps, Electron. J. Combinatorics 4 (1997) R20; See also: G. Schaeffer, Conjugaison d’arbres et cartes combinatoires aléatoires, PhD Thesis, Université Bordeaux I, 1998.

J. Bouttier et al. / Nuclear Physics B 655 [FS] (2003) 313–341

341

[2] M. Bousquet-Mélou, G. Schaeffer, Enumeration of planar constellations, Adv. Applied Math. 24 (2000) 337–368. [3] D. Poulalhon, G. Schaeffer, A note on bipartite Eulerian planar maps, preprint (2002), available at http://www.loria.fr/~schaeffe/. [4] D. Poulalhon, G. Schaeffer, A bijection for loopless triangulations of a polygon with interior points and multiple edges, in: Proceedings of the Conference FPSAC’02, Melbourne, 2002, Theor. Comput. Sci., in press, available at http://www.loria.fr/~schaeffe/. [5] W. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962) 21–38. [6] W. Tutte, A census of Hamiltonian polygons, Canad. J. Math. 14 (1962) 402–417. [7] W. Tutte, A census of slicings, Canad. J. Math. 14 (1962) 708–722. [8] W. Tutte, A census of planar maps, Canad. J. Math. 15 (1963) 249–271. [9] J. Bouttier, P. Di Francesco, E. Guitter, Census of planar maps: from the one-matrix model solution to a combinatorial proof, Nucl. Phys. B 645 (2002) 477–499. [10] E. Brézin, C. Itzykson, G. Parisi, J.-B. Zuber, Planar diagrams, Commun. Math. Phys. 59 (1978) 35–51. [11] P. Di Francesco, P. Ginsparg, J. Zinn-Justin, 2D gravity and random matrices, Phys. Rep. 254 (1995) 1–131. [12] B. Eynard, Random matrices, in: Saclay Lecture Notes (2000), available at http://www-spht.cea.fr/ lectures_notes.shtml. [13] J. Bouttier, P. Di Francesco, E. Guitter, Critical and tricritical hard objects on bicolourable random lattices: exact solutions, J. Phys. A: Math. Gen. 35 (2002) 3821–3854. [14] M. Bousquet-Mélou, G. Schaeffer, The degree distribution in bipartite planar maps: application to the Ising model, math.CO/0211070.