{'fraction_non_alphanumeric': 0.04039253543722697, 'fraction_numerical': 0.007896546215977832, 'mean_word_length': 4.098183620720178, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold

Continuing the program begun by the authors in a previous paper, we develop an exact low-density expansion for the random minimum spanning tree (MST) on a finite graph, and use it to develop a continuum perturbation expansion for the MST on critical percolation clusters in space dimension d. The perturbation expansion is proved to be renormalizable in d=6 dimensions. We consider the fractal dimension D_p of paths on the latter MST; our previous results lead us to predict that D_p=2 for d>d_c=6. Using a renormalization-group approach, we confirm the result for d>6, and calculate D_p to first order in \epsilon=6-d for d\leq 6 using the connection with critical percolation, with the result D_p = 2 - \epsilon/7 + O(\epsilon^2).


I. INTRODUCTION
In this paper, we continue our treatment of the statistics of random minimum spanning trees, which was begun in Ref. [1] (to be referred to as I). We first recall the definitions (see any of Refs. [2,3,4,5]): we consider an undirected, connected graph G with vertex set V , edge set E and a real-valued cost ℓ e assigned to each edge e ∈ E. A spanning tree is then defined as a subset of the edges of G that connects all the vertices and contains no cycles: in other words, it is a tree and it spans V . Such a tree must exist because the graph is assumed connected. A minimum spanning tree T is a spanning tree such that the sum of the costs of its edges, is minimized over the set of all spanning trees on G. (If the costs ℓ e are strictly positive, then any spanning subset of the edges that has minimum cost is automatically a tree.) In this paper, we again consider the random problem, in which the edge costs are assumed to be independent and identically-distributed (iid) random variables, with a continuous probability distribution for the cost of each edge, and we are interested in the statistical geometry of the tree. This random model will be referred to simply as the MST. We also consider a generalization, introduced in Ref. [1], in which the costs are iid, the probability distribution for the cost of any edge is uniform on the interval [0, 1], and one finds the minimum spanning forest (a forest is a collection of vertex-disjoint trees) on the (not necessarily connected) graph formed by the subset of edges that have cost less than p ∈ [0, 1]; this object is called MSF(p). It is connected with the use of Kruskal's greedy algorithm for the MST [2,3,4,5,6]. In Kruskal's algorithm, the edges are tested one by one, in order of increasing cost. Each edge is "accepted" as belonging to the MST unless doing so would form a cycle in combination with edges already accepted. If this algorithm (or "Kruskal process") is stopped when all edges with cost < p have been tested, one obtains the MSF(p). MSF(p) is closely related to bond percolation [7], which is obtained if the process is modified so that it simply accepts every edge, in which case each edge is independently accepted (occupied) with probability p. This relationship plays a central role in the work to be reported here.
The background and motivation for studying this problem were discussed in the previous paper. Of particular interest there was the strongly-disordered spin-glass model of Newman and Stein (NS) [8]. Our results strongly suggested that when the graph is a lattice in Euclidean system of dimension d, the critical dimension for that model and for the MST is 6. This is the dimension above which there are many large connected components of the MST that are visible within a window of size W ; we found that the number is of order W d−6 . The strongly disordered spin glass maps onto the MST, and the logarithm of the number of ground states of the spin glass that can be distinguished within a window is the same as the number of large connected components that are visible. For the MSF(p), the properties such as the number of large connected components are expected to be similar (scale with the same exponents) for all p > p c , where p c is the threshold for bond percolation. These results were strongly motivated by the solution of MSF(p) on the Bethe lattice (Cayley tree) [1].
Other problems related to the MST that have been studied in the physics (and related) literature include the fractal dimension of the paths on the MST in Euclidean space, and the relation with problems of optimal paths and transport in random media [9,10]. In this paper we begin to address some of these issues. On a finite graph, there is a unique self-avoiding path on the MST between any two vertices. Eventually, we aim to study the fractal dimension D ′ p of the paths on the MST. In general, such a dimension can be defined by a box-counting technique, that is counting the number of steps on the path inside a window. One would hope also to obtain the frac-tal dimension of the path from the expectation value of the total number of steps on the path, if this is of order R D ′ p for two vertices separated by a large Euclidean distance R. [In the Kruskal process or MSF(p), this would again be expected to be the same (on large length scales) for any p > p c , for two vertices that are connected on MSF(p).] Several earlier works [11,12,13,14] have provided numerical estimates of D ′ p for the MST at p = 1 in various spatial dimensions. In d = 2 dimensions, the value is around 1.23.
However, in the limit of an infinite system in d > 6, there are many connected components of the MST, and for a large finite system (say, a hypercube of side L) this means that for many pairs of vertices, the path connecting them makes a large excursion (of order the system size). To see this, first note that if one makes the system larger by adding additional edges at the boundary, chosen from the same probability distribution, keeping those in the interior the same, then one can study the behavior of the MST as L increases. Locally, it will converge to a definite limit that has the number of components as described above. This implies that the path connecting two fixed vertices will be deformed until it goes off to infinity as L → ∞, and so have infinite length, unless the two vertices are on the same component in the limit. For finite L, it will make an excursion typically of linear size of order L. These considerations, together with the probability of order 1/R d−6 that the two given vertices are on the same connected component in the limit, suggest heuristically that the expected length of the path scales as where D ′ p is the fractal dimension of the path on the MST, for which the Bethe lattice results in Ref. [1] suggest D ′ p = 2 for d > 6. For L ≫ R, the last term O(L 2 ) dominates, and again the result is similar for MSF(p) for all p > p c . But if we could restrict attention to (or condition on) paths not going to infinity, the conditional expectation for the path length would scale as R D ′ p . For d ≤ 6, this problem does not arise, and we expect that, at least for d < 6, where there is presumably only one connected component in the infinite system limit, the length of the path will indeed scale as R D ′ p , independent of L for large L. (In the numerical work cited above, cases in which d > 6 were apparently not considered.) For this and for other related technical reasons, we will restrict our calculation of exponents in this paper to the Kruskal process with p ≤ p c . In this case the probability that two points are connected by either the percolation or the Kruskal processes decays with increasing distance R. For p = p c , where scaling will again apply, we will denote the fractal dimension of the path on the MSF(p c ) by D p . The naive scaling for the total length of a path R Dp still works in this case.
There are claims (the "superhighways" argument) [10,15] that in the Kruskal process (on various fami-lies of graphs) the properties of the paths are mainly determined by the percolation threshold. Numerically, the fraction of steps on a path on the MST that are already present at p = p c , averaged over all pairs of end vertices for the path, goes to a constant [10,15]. This suggests that D ′ p = D p . For the Bethe lattice and for Euclidean systems with d > 6 we can argue that both dimensions equal 2 [1], so equality holds, however, it is less clear whether it holds for d < 6. Some support for it can be obtained from scaling arguments in percolation. Consider a hypercube of side L, and for bond percolation ask for the probability that two given opposite faces are connected when the occupation probability for each edge is p. The percolation threshold is the value of p above which the connection occurs with probability one as the size L → ∞. For L finite, connection occurs at p = p c with low probability, but it occurs with probability approaching 1 at p − p c of order 1/L 1/ν , where ν is the correlation length exponent in percolation [7]. At this value of p, the correlation length ξ is of order (p c − p) −ν = O(L), and scaling properties at scales less than ξ should be the same as those at threshold p = p c . Hence we expect the fractal dimension D ′ p of the path on the MST connecting the two faces (which is one of the paths on the percolation cluster that do so when the faces are first connected as p increases) to be D p . However, this path does not have the boundary conditions we wanted, as we only asked for the connection of the two faces, not of two given vertices in the interior of a system. When the separation R of the vertices is large, we may surround each by a nested sequence of concentric spheres of radii say 2 −j R/3 for j = 0, 1, . . . and ask the same question for each annulus bounded by two of these spheres. Then the relevant p will be different for each sphere (higher p is required to make the connections to the vertices on smaller scales), but also the scaling holds for each one. In addition, the clusters that connect each pair of spheres must also become connected together to form a single cluster and an MSF path. Similar arguments apply to all of these. This does suggest, heuristically, that D ′ p = D p . On examining this argument, a key part of it can be seen to be the idea that there is a unique candidate superhighway (critical percolation cluster) that is used to make connections over large distances on each scale, and so it is clear which ones must be connected by highercost "roads". This is a property of critical percolation clusters that holds for d < 6, but not for d > 6, where the number of large clusters visible in a window of size W is W d−6 [7,16]. This behavior may itself underlie the result [1] that the number of connected components of the MST (or of MSF(p) for p > p c ) has this same form W d−6 for d ≥ 6 (but order 1 for d < 6).
In this paper we do not assume the equality of D ′ p and D p , but will study D p . We first construct in section II an exact series expansion for any finite graph that gives the probability that the path on MSF(p) from vertex x to vertex y passes through vertex z, by analogy with expansions in percolation. The expansion takes the form of a weighted sum of subgraphs. This expansion may be of general interest within various approaches to MSTs not considered further in this paper, such as hightemperature series.
In section III, we then turn this expansion into an asymptotic or perturbation expansion in the continuum (with cutoff) by neglecting excluded volume requirements that were present in the exact expansion, and taking the graph to be the infinite lattice. (From here on, our results are not fully rigorous mathematically, though they will satisfy most theoretical physicists.) In this way, we obtain a Feynman diagram expansion. It is related to that for percolation, but with modified Feynman rules. In order to avoid dealing with the appearance of the order parameter for percolation (non-zero probability of connection to infinity), from this point forward we consider only p ≤ p c .
The perturbation expansion contains ultraviolet (short-distance) divergences as the wavevector cutoff goes to infinity (or as the lattice spacing goes to zero) with the separation of the vertices held fixed. We prove that the expansion is renormalizable in the field-theoretical sense to all orders in perturbation theory. We then use standard techniques to formulate a renormalization group (RG) approach which gives the scaling behavior of the correlation functions (probabilities) already mentioned. The exponents or fractal dimensions are then calculated for d < 6 as an asymptotic series in powers of ε = 6 − d, with the result as ε → 0. For d > 6, the analysis of the cut-off expansion confirms that D p = 2 to all orders in perturbation theory, and the path behaves as a Brownian random walk on large length scales. Further discussion is contained in the Conclusion. To improve readability of the paper, many detailed derivations have been relegated to the Appendices.
Our calculations can in principle be extended to other exponents, such as those defined in [17], or carried to higher orders in ε. They can also be extended to include statistical properties that involve the cost of the MST. There do not appear to be any scaling relations that relate the geometric exponents for MSTs to those for percolation, unlike those found for the costs in [18], even though the critical dimension d c = 6 is the same.

II. LOW-DENSITY EXPANSION ON A FINITE GRAPH
In this section we describe how to set up an exact lowdensity expansion which enables one to calculate connectedness functions for the (random) MSF on any finite graph G. The expansion takes the form of a low-density expansion, similar to a high-temperature expansion familiar from statistical mechanics, with small p playing the role of high temperature, and is modeled on a corresponding expansion for bond percolation. Although from the point of view of this paper the primary utility of the result is to provide a basis for the RG calculations of the following section (which determine the fractal dimension of paths on the MSF), the expansion is of interest in its own right, and might form the starting point for further mathematically-rigorous calculations, using e.g., lace expansion methods [19]. As the construction is somewhat involved, we concentrate here on describing the structure of the expansion, and relegate most details of its derivation to the Appendices.

A. Graphical expansions for percolation
In view of the correspondence between bond percolation and Kruskal's algorithm discussed in I, and the relation of the MSF(p) process with percolation, we will first briefly review the low-density expansion for bond percolation. Afterwards, we set up a corresponding expansion for MSF(p) by generalizing the arguments using Kruskal's algorithm.
Bond percolation on a finite-dimensional lattice is conventionally treated as the Q → 1 limit of the low-density expansion of the Q-state Potts model [20,21,22,23]. The partition function of the Potts model, which is a polynomial in Q, is also known as the Tutte polynomial [24], and is a generating function for Q-colorings of the vertices of the graph G with weights that depend on whether adjacent vertices are given the same or different colors. Although the Q → 1 limit of this function can be taken, it lacks a mathematical definition in terms of state variables (colors), so in order to establish a correspondence with percolation we instead use a method originally due to Essam [25,26]. This has the advantage of being phrased explicitly in terms of geometric quantities.
The basic object of interest is the two-point connectedness function C x,y (p), the probability that two vertices x and y on the lattice are connected by a percolation cluster (connected component) when the probability that an edge is occupied is p. In Appendix A 1, we review the graphical expansion for this probability, which has the form where the sum is over all graphs G in the set G x,y , defined as graphs on (i.e. subsets of) the lattice containing the endpoints x, y. The factor of Pr[G ≤ p] is the probability that all the edges of G have cost less than p (i.e. are occupied in the percolation process), which in the iid model (Bernouilli model of bond percolation) is simply p |E(G)| (where E(G) is the set of edges of G). The function d(G) can be defined as (II.2) where the sum is over subsets E ′ of the edge set E(G). We use the notation I[X] for the indicator function on events X, which takes the value 1 when X is true and 0 when X is false. d(G) = 0 if x and y are not connected by G.
The preceding graphical expansion may be generalized straightforwardly to n-point connectedness functions: now we must sum over G x1,··· ,xn , the set of subgraphs of the lattice that contain all n vertices, and in Appendix A 2 we show that the correct generalization of (II.2) is [27] The d-weights defined above have several properties worth remarking on. First, in Appendix A 3, we prove that the expansions (II.2), (II.3) assign the same weights to the same diagrams as does the Q → 1 limit of the lowdensity expansion for the Q-state Potts model, so the above expressions are entirely equivalent to the conventional description of bond percolation.
Second, the d-weight clearly only depends on the connectivity of the set E(G) of the edges of G, not on the geometry of G, and further as shown in Appendices A 1, A 2, the d-weight is invariant under replacing edges of G with chains of edges (i.e., inserting vertices of degree two). Thus d(G) is a topological invariant of graphs G with two marked vertices. This means that we can consider the expansion in terms of topological graphs G, which are simply graphs (without any embedding in the lattice), with two distinct vertices labeled x, y (and the others unlabeled), and which may be assumed to contain no vertices of degree two other than possibly x, y. Using this property, we may rewrite the expansion (II.1) as with analogous expressions for the n-point functions.
Here G x,y is the set of all (topological equivalence classes of) topological graphs with two distinct labeled vertices x, y, and the inner sum is over all possible embeddings λ : G → G which map the edges of G into self-avoiding chains of edges on the lattice, producing the set of lattice graphs summed over in (II.1). Note that these chains must not only be self-avoiding walks, but also must avoid intersection with chains arising from different edges of G.
If the topological graph G has any non-trivial automorphisms (leaving the root points x, y fixed), then there is more than one way to produce the same embedded graph G. Consequently, we must divide by the number A(G), which is the number of elements in the automorphism group of G. This number is often called a "symmetry factor", especially in the context of Feynman diagrams, and will play such a role later. This topological property of the d-weights is crucial for extending the lattice expansion (II.4) to a continuum theory, a point to which we will return in Section III A. It also simplifies lattice calculations, since it greatly reduces the number of different graphs for which d(G) must be calculated. The d-weights have further properties that, when the graph G has a connected subgraph, allow them to be factorized into pieces given by the d-weight of the subgraph and that of the "quotient" graph in which the subgraph is replaced by a single vertex. These are discussed in the Appendices.
There is a further function will be useful in making comparisons with the MSF theory. This is the derivative of C x,y (p) with respect to the value p e of p on a particular edge e (the generalization of the formulas to cases in which the occupation probabilities such as p e for edges differ should be obvious). The probability that x and y are connected by a cluster at p changes with p e only if x and y are not connected when p e = 0, and are connected when p e = p. This implies that for p e = p, any path from x to y on the cluster must traverse e. An edge with this property is called a singly-connected edge. So we define which is the probability that at parameter p, x and y are connected, and e is a singly-connected edge on the same cluster. Note that C e x,y (p) is not the same as the 3-point connectedness function that was defined above, and its lattice expansion (which may be obtained directly from the preceding definition) still contains the same d weights as for C x,y (p), and in fact is given by the same expansion (II.4), but with the additional condition that e be an edge of the embedded graph G (note that for the graphs G in the expansion, e does not have to have the singly-connected property). We may choose to view the topological graphs as having the inverse image of e as a marked edge (either of the ends of which may be degree-two vertices), so that the embeddings λ map it to the single edge e; in this case the relevant automorphisms of G must fix this edge as well as x, y, and we denote the number of these by A ′ (G). Clearly A ′ (G) ≤ A(G) (one group of automorphisms is a subgroup of the other). These different ways of writing the function are equivalent.
Although we have formulated the expansion here in terms of the infinite lattice, it proceeds in exactly the same way if the lattice is replaced by any finite graph G. Indeed it is best viewed as derived from some finite graph such as a portion of the lattice, followed by an infinite volume limit. The sums over all embedded graphs make sense for a finite graph because only a finite number of terms contribute. For the infinite lattice, the sum converges for p < p c (like a high-temperature expansion), but not for p > p c . In the latter case, it needs to be re-summed, but we will not discuss this here.
In the next two subsections, we proceed to develop a graphical expansion for MSF connectedness functions, analogous to (II.4) in that it takes the form of a weighted sum over topological graphs and their lattice embeddings. This will be the basis for the continuum theory analyzed in section III.

B. A low-density expansion for MSF paths
We will study the random geometry of paths on the MSF by introducing a connectedness function C z x,y (p), which is the probability that two vertices x, y on the MSF are connected and the connecting path passes through a third vertex z. In the following, a vertex z satisfying this definition will be called a "MSF path vertex" (with respect to two other vertices x, y). (We could equally well define a similar function in terms of the probability that the MSF path passes through an edge e instead of a vertex z, which makes the analogy with the percolation function C e x,y (p) closer; in the continuum formulation developed afterwards, there is no difference between the vertex and edge cases for MSF.) We obtain a diagrammatic expansion for these connectedness functions by relating the Kruskal process defining MSF(p) to the expansion for bond percolation obtained in the previous section. The difference between the percolation and Kruskal processes is that, in the latter, as p increases an edge with cost ℓ = p is not accepted if, together with edges already accepted by ℓ < p, it forms a cycle.
In Appendices B and C, we develop the tools needed to obtain a diagrammatic expansion for the MSF connectedness functions involving the MSF path vertex. Appendix B contains a careful discussion of properties of the MSF paths that are used, while Appendix C uses the method of inclusion and exclusion to obtain the expansion itself. Here we will begin by defining notation. The ordering of the costs of the edges on a subgraph G of the given graph G plays an important role. We know that in fact the MST on a graph depends only on the ordering of the costs [1,12]. We define an ordering on the set of edge costs of G as a permutation π ∈ S |E| on the set of |E| elements. We index the edges of G arbitrarily, and take the ordering of their costs to be defined by π via ℓ π(i) < ℓ π(j) ⇐⇒ i < j, (II. 6) for the edges indexed i, j (writing ℓ i for ℓ ei ). For subsets of E, such as E ′ or E(G), we define the induced ordering by restriction, and denote it by π E ′ or π E(G) . Thus π E ′ is a permutation of the subset E ′ . We can obtain the probability for each possibility ordering from the iid probability distributions on the edge costs in the obvious way, and clearly Pr[π E ′ ] = 1/|E ′ |!, in particular for the special case E ′ = E.
With these definitions, the result we obtain in Appendix C for the path vertex connectedness function can be written which should be compared with the corresponding result (II.1) for percolation, or its analog for C e x,y (p). Here G x,y;z is the set of graphs G that contain the root points x and y, and a (self-avoiding) path from x to y passes through z. The diagrammatic weight d MSF (G|π) implicitly depends on x, y, z, and is ordering-dependent. It can be defined as which should be compared with (II.2). Here G E ′ is the subgraph of G with vertex set V and edges E ′ , and γ MST (G E ′ |π E ′ ) is the path connecting x, y on the MST on the graph G E ′ with costs on E ′ induced by restriction from G. This MST can be assumed to exist because G E ′ can be assumed to be connected, in view of the indicator function I[E ′ connects x, y].
Next we wish to express this connectedness function as a sum over topological graphs G. We consider a given lattice graph G which is the image of some topological graph G under some embedding λ. For clarity in what follows, we denote elements of the edge sets of G, G by different symbols: we have e ∈ E(G) and ǫ ∈ E(G). We find it useful to extend our notation and let λ(ǫ) ⊂ E(G) denote the chain (self-avoiding path on the lattice) of N ǫ edges on the lattice that the topological edge ǫ is mapped to.
For both percolation and MSTs, the only edge cost information relevant for the connectedness functions is the cost of the most expensive edge on λ(ǫ), which we denote by (II.9) Then in bond percolation at occupation probability p, to determine whether λ(ǫ) connects its endpoints, we only need to check whether L ǫ ≤ p. Likewise, λ(ǫ) is a subset of the MST on G only if L ǫ is less than the maximal edge cost encountered on all other paths on G connecting the same vertices. We may think of L ǫ as the cost induced on the edge ǫ of G by the embedding λ. A corresponding order π ′ E(G) is induced on these costs. Given an embedding of G, both Pr[L ǫ ] and Pr[π ′ E(G) ] depend on the embedding. The probabilities can be readily calculated, as we will see shortly.
Because d MSF (G|π) is computed in terms of connectedness properties (whether or not the MST path between the root points of the diluted graph G E ′ goes through the MSF path vertex at z), it may be computed using only the relative ordering π ′ E(G) obtained from the {L ǫ }. Therefore we have (and depends on the marked vertices of G that are the inverse images of x, y, and z under λ). In the expansion (II.7), only the ordering and its probability is required, and it is possible to fix an ordering before choosing an embedding (and finally summing over both). Hence it may be written as Here again A ′ (G) is the relevant symmetry factor as defined in section II A (strictly, it is defined here for automorphisms fixing the inverse image of the vertex z rather than e; the cases relevant to the continuum expansion later are those in which the vertex z has degree two, and should be compared with those in which, when e is shrunk to a single vertex, then it has degree two, and for these the numbers are the same). Eq. (II.11) is the main result of this Section, and should be compared with the percolation result (II.4). It remains to find an expression for Pr[π ′ E(G) ∧ (G ≤ p)]. This is done in the following Subsection.
To put the quantity Pr[π ′ E(G) ∧ (G ≤ p)] in a more tractable form, we return to basic considerations. As the simplest example, we take the case where G consists of two root vertices connected in parallel by two edges ǫ 1 , ǫ 2 . We consider an embedding λ where λ(ǫ 1 ), λ(ǫ 2 ) are chains of N 1 , N 2 lattice edges, the most expensive edges of which have costs L 1 , L 2 , respectively. We can define and evaluate the probability for L 1 < ℓ 1 and L 2 < ℓ 2 : (II.12) The probability density for (L 1 , L 2 ) is found by differentiating on both variables, and then the probability that L 1 < L 2 < p is found by integration: This is clear from the iid behavior of the edge costs: the most costly edge could be any of the N 2 edges among the total number N 1 + N 2 . [The result is more general than the model we have been using, in which costs are uniformly distributed on [0, 1]. For a general iid distribution of costs, the probability that L 1 < L 2 < ℓ 0 is N 2 p N1+N2 /(N 1 + N 2 ), where p is the probability that a given edge is less than ℓ 0 . Similar statements apply to the following generalization.] The result generalizes to any embedded graph G, with edges E(G) = {ǫ 1 , . . . , ǫ n } which have lengths N 1 , . . . , N n and maximum costs L 1 , . . . , L n . We let the ordering be π ′ E(G) = π ′ , such that L π ′ (1) < L π ′ (2) < · · · < L π ′ (n) . The generalization of (II.13) is (II.14) which can be evaluated as .

(II.15)
Although the preceding result is completely explicit, it will be useful in the following to utilize the expression as an integral of multiple derivatives. Accordingly, we will define the integro-differential operator O MSF (π ′ E(G) , p) which depends on the set E(G), the ordering π ′ E(G) , and the limit p, and which acts on a set of variables ℓ ǫ indexed by the elements of E(G). For notational simplicity, we again write it for E(G) = {1, . . . , n} with π ′ E(G) = π ′ ∈ S n : We have for any nonsingular function f of n parameters, because the domain of integration becomes the cube ℓ i < p, all i. Using eq. (II.15) in (II.11), and the definition of O MSF (π ′ E(G) , p), gives the desired expansion in terms of topological graphs, This is the final result of this section, which again should be compared with the percolation result (II.4). The expansion for MSF(p) that we have obtained is naturally organized as a low-density expansion, that is as an expansion in powers of p. For large graphs G, it becomes unwieldy, especially for p greater than around the percolation threshold (to the extent that a threshold can be associated with a finite graph, for example for a portion of a hypercubic lattice we can consider the threshold p c of the infinite lattice). The corresponding expansion for the connectedness function C x,y (p) in percolation must produce the answer 1 when p → 1, but in a very complicated way, as a sum of a large number of terms. For the MST, obtained from MSF(p) as p → 1, the probability that the path on the MST from x to y passes through z remains non-trivial in the limit, and is again given by a complicated set of terms. A general analysis of this sum on a large graph for p > p c would require a resummation of terms to allow for the presence of the "giant cluster" in the corresponding percolation. In the Potts model formulation of percolation, this is done by giving an expectation value to the Potts spin. A formulation of such a resummation suitable for the MSF(p) problem will not be given in the present paper, which is consequently restricted to the region p ≤ p c on large lattices from here on.

III. RENORMALIZED PERTURBATION EXPANSION FOR MSF PATHS
In this section we describe how the exact low-density expansion obtained in the previous section may, for p ≤ p c , be turned into a continuum theory (with a cutoff) to which renormalization-group methods may be applied. This continuum theory is obtained from a naivelooking procedure of replacing the lattice paths representing edges of a topological graph by continuum random walks, and neglecting the excluded volume requirement that the graph be embedded in the lattice without using a vertex or edge more than once. The resulting perturbation expansion is expected to be asymptotic rather than convergent. The expansion is closely related to that for percolation, so that the resulting Feynman diagrams and corresponding integrals can be compared with those of the latter. However, the expansion does not arise from the path integral of an action functional, so we do not technically have a "field theory of MSF paths," although we will show that many of the standard techniques of field theory remain applicable. In particular, we show in Section III E and Appendix D that the perturbation expansion may be renormalized and RG methods applied. This enables us to calculate in Section III F the fractal dimension of paths on MSF(p c ) as an asymptotic expansion in ε = 6 − d, which we perform to leading order.
A. The excluded volume constraint A lattice expansion in terms of topological graphs, such as (II.4), is very close to describing a continuum theory. The only remaining roadblock lies in the sum over embeddings λ, which carries an effective excluded volume constraint: edges of G must be mapped to selfavoiding chains of lattice edges, and which must all be edge-disjoint (and hence also vertex-disjoint): no edge on the lattice may be used more than once. This is technically more difficult to incorporate. If we drop this constraint, we have a sum over "free embeddings"λ, which map edges of G to random walks in the lattice, which are allowed to intersect, and then Fourier transform techniques may be freely used. This is the starting point for a continuum theory: as is well known, the generating function for random walks may be thought of as the propagator of a free scalar field.
For percolation, the excluded volume constraint may be avoided by further modifications to the expansions given above. This is Essam's "ρ expansion", given in Refs. [25,27]. There certainly seems to be no obstacle to extending the ρ expansion to the expansion for MSF paths derived in the following subsection, but we do not pursue this line of inquiry (which may be relevant for a mathematically rigorous reformulation of the results given here). Instead, in what follows, we assume we may drop the excluded volume constraint without difficulty or modification of our lattice expansion. This is because our ultimate aim is an RG calculation around d c = 6. In the diagrammatic perturbation expansion, the important graphs for calculation of the exponents have vertices of degree 3 only. If we attempted to incorporate the excluded-volume constraints, perhaps following Essam's technique, additional diagrams (topological graphs) with vertices of degree four or more would enter, but these will be irrelevant close to six dimensions, as could be demonstrated by extending the techniques given below.

B. Continuum perturbation expansion for MSF paths
We first consider the percolation connectedness functions, defined via (II.4) (and its generalization to n-point functions), which must be reproduced by the MSF(p) process. Because we neglect the excluded volume constraint present in the sum over embeddings, for a given topological graph (which may now be referred to as a Feynman diagram) G, we may take the chains of edges produced by the lattice embedding to be independent random walks. In the sum over such embeddings, it is natural to consider the Fourier transform with respect to the positions x i (i = 1, . . . , n), and to use the Fourier representation for the probability of a walk between two of the vertices; the latter takes the form 1/(q 2 + t 0 ) ≡ G 0 (q, t 0 ), the same as the propagator of a scalar field [28]. Here t 0 ≥ 0 is the "mass-squared" parameter, which depends monotonically on p; naively, t 0 decreases to zero as p increases to p c (however, this statement will be modified by perturbative corrections). Thus we make the substitution λ :G→G Here N is the incidence matrix of G under an arbitrary orientation of the edges: The momentum (i.e. wavevector) integrals are subject to a cutoff: each variable q ǫ must obey |q ǫ | < Λ. This cut off replaces the restriction of the integrals to a single Brillouin zone that is due to working on the lattice (note that in the latter case the propagators would be invariant under addition of a reciprocal lattice vector to any q ǫ ). Thus Λ is initially taken to be of order 1/a, where a is the spacing of the lattice points. Finally, a factor g |V (G)|−n 0 has been inserted, to absorb other numerical factors that are omitted, and because this parameter will be renormalized later. At this stage, g 0 is strictly speaking of order one, but will be viewed as small in the perturbation expansion. At the same time, we will restrict the sum to topological graphs with vertices of degree three, except for the marked points x i , which are of degree one (thus we have g 0 for each cubic vertex). Both of these simplifying assumptions can be justified because other contributions can be shown to be irrelevant (in a RG sense) near six dimensions, using the RG technology to be discussed later. Thus, the continuum expansion for the percolation connectedness functions becomes where the sum is over diagrams with trivalent vertices and n "external" marked points on which d depends, and A(G) is the appropriate symmetry factor. For the function C e x,y (p), there is a similar expansion, in which we sum over graphs with two marked degree one external points at x, y, and with a single degree two vertex marked z (to replace e, as mentioned before); the symmetry factor becomes A ′ (G), and the power of g 0 is |V (G)| − 3. In the same way that this function on the lattice was obtained by differentiating with respect to p, this function in the continuum can be obtained by differentiating the Feynman diagram expression for C x,y (p) with respect to t 0 (and no subsequent integration in the present case). In particular, this produces the correct symmetry factors. This operation gives the additional vertex with zero wavevector, but can be generalized to allow some momentum to enter at z, as given above. In field theory it is referred to as insertion of a mass-or φ 2 /2 operator, where φ would be the field corresponding to the degree one external points [29].
Because of the equivalence of the d weights with those of the Q = 1 Potts model (at least for n = 1, 2), this perturbation expansion reproduces the standard one for the field theory of the Q → 1 Potts model, which is usually obtained via the Hubbard-Stratonovich technique [22,23]. We emphasize that for the purposes of what follows we are prohibited from making any reference to an action functional due to the fact that the MSF path vertex cannot be expressed in terms of any local operator: instead we must phrase our argument entirely in terms of diagrammatic expansions. Now we turn to the path connectedness function C z x,y (p) for MSF(p), which is the probability that at parameter value p there is a path on MSF from x to y passing through z. We treat the continuum version of the expansion in exactly the same way as we did for percolation, with the function C e x,y being the closest analogue. Then compared with percolation, we make the following modifications of the expansion: the diagrams are considered for each ordering π ′ of the costs L ǫ of the edges ǫ of the diagram, the d-weights are modified as they depend on the ordering through the requirement that the path on the MSF passes through z (and depend on marked points x, y, z), and the probability is modified to give the probability for the ordering. Further, for the MSF, when we pass to the continuum perturbation expansion, the probability for a given ordering of costs L ǫ on the edges of the diagram must depend on squared-masses t ǫ in place of ℓ ǫ . These parameters are acted on by the integro-differential operator O MSF (π ′ , p), which finally sets all ℓ ǫ to p. After the change of variable to t 0 , the operator O MSF (π ′ , p) may trivially be rewritten in terms of the {t ǫ } variables: because every derivative is paired with an integral, the Jacobians involved in changing from the {ℓ ǫ } to the {t ǫ } cancel. The only difference is that the ordering π ′ applies to the t ǫ in reverse: small L ǫ corresponds to large t ǫ . Therefore, (II. 16) becomes (III.5) The perturbation expansion for the MSF path vertex functions in the continuum is now The set of graphs involved are the same as those used in the differentiated two-point connectedness function of bond percolation (as described above), so we may compute this by starting with the expansion for C e x,y (t 0 ) and making the substitution, on a diagram-by-diagram basis.
To summarize, the Feynman diagram rules for the MSF path correlation function, as specified in (III.7), are as follows: 1) For each diagram G ∈ G x,y,z contributing to the twopoint correlation function between x and y of a cubic scalar field theory with a mass-insertion at z, we associate a mass-squared t 0 ≤ t ǫ < ∞ to each edge ǫ ∈ E(G). For each ordering π of these mass parameters, we act on the integrand with the operator O MSF (π ′ , t 0 ) defined in (III.5). 2) After integrating over wavevectors, the contribution from each ordering is multiplied by the diagrammatic weight d MSF (G|π ′ )/A ′ (G), with d MSF defined in (II.8), and the sum of these over all mass parameter orderings is the contribution to the MSF path connectedness function.
Note that we must act with O MSF before any momentum integrations are performed, since the latter may produce expressions that diverge at the upper limit of the integrations in O MSF . This situation could be remedied by cutting off the domain of integration in O MSF to {t ǫ } < Λ 2 , at the expense of complicating our RG calculation.

C. Extraction of fractal dimensions and lowest order results
The perturbation expansion that we have now obtained can be organized as a loop expansion: the lowest order contribution to C z x,y is order O(g 0 0 ), and is simply the diagram that takes the form of a path from x to z to y, which possesses no loops (cycles), while higher orders in g 0 contain additional loops, one for each factor of g 2 0 . The lowest order result, in position space and at t 0 = 0, takes the form (in this and the following, all separations like |x − y| are assumed large, ≫ a) (III.8) By contrast, the 2-point connectedness function at criticality, obtained as a single scalar propagator, is proportional in this order to 1/|x − y| d−2 .
[At zero-loop order, these results are the same for MSF(p c ) and for critical percolation.] Dividing the two gives the conditional probability that there is a path from x to y passing through z, given that there is a path from x to y. Integrating over z gives ∝ |x − y| 2 . This is viewed as proportional to the total number of steps on the (lattice) path, even through the events of the path passing through the various z are not disjoint. The exponent 2 indicates that the fractal dimension of the path is 2, which is the correct result for a random walk. Thus we have shown that at zero-loop order. This will be found to be correct for d > 6, and also for d = 6 up to logarithmic corrections. The same dimension is believed to hold for paths on critical percolation clusters for d > 6, by similar fieldtheoretic arguments. Geometrically, it is because on large scales these clusters are trees, with no loops [7], and hence are the same in the MSF(p c ) process. In general, and specifically for d < 6 as we will show, the scaling exponents will be different. At p c , quite generally C z x,y will have the scaling behavior for any x, y, and z, and scalar b, while the 2-point connectedness behaves as Thus these two functions determine two exponents η and D p for MSF(p c ), and η will be the same as for percolation, as we will explain shortly (η = 0 for d > 6). Then in the same way as at zero loops, we infer the fractal dimension D p for the MSF path. From the geometric point of view, d − D p is the co-dimension of the path. The exponent η describes the decay with distance r of the probability that two points are connected by a critical percolation cluster, namely ∼ r −(d−2+η) . In a field-theoretic point of view, (d − 2 + η)/2 = x φ is the dimension of the Potts field operator φ, while d−D p = x p is the scaling dimension for the path-vertex "operator".
x φ is related to the fractal dimension D perc of the critical percolation clusters as the codimension For the percolation function C e x,y , the corresponding φ 2 operator at e has dimension x φ 2 = d − D sc , and D sc is the fractal dimension of the set of singly-connected edges on the path from x to y on the critical percolation cluster [7]. For d < 6 this set does not usually form a connected path. We see that the MSF path must include the singly connected edges, which leads to the inequality (III.12) Because the function C e x,y is connected via differentiation with the change in connectivity with p (or t 0 ), the scaling dimension x φ 2 of the φ 2 insertion controls the length scale produced by taking p < p c ; this length is the correlation length ξ, and we can define the exponent ν by ξ ∼ (p c − p) −ν as p → p c . It follows that D sc = ν −1 [7]. This discussion shows how the fractal dimension D p , and others, can be extracted from the renormalized perturbation calculations.
D. Beyond lowest order: breakdown of perturbation theory for d < 6 The perturbation expansion for the MSF path connectedness functions can be treated in a similar manner as that for standard field theories. A first step is to introduce one-particle irreducible (1PI) functions. A diagram is defined to be 1PI if it does not become disconnected when a single edge is removed. Now for the MSF path connectedness function C z x,y , the (dominant) diagrams that contribute have a single edge emerging from x and y. For terms of order O(g 2 0 ) (as g 0 → 0), the diagram possesses at least one loop (cycle). It can then be decomposed into a chain of one or more disjoint 1PI 2-point graphs, connected by single edges. The vertex labeled z is either inside one of the subdiagrams (subgraphs), or on one of the single edges. The 1PI subdiagrams not containing z will be called self-energy diagrams.
For the d MSF -weight of such a diagram, it is easy to see that the weights associated with each 1PI subdiagram factor. This is because the MSF path must pass through each of the 1PI subdiagrams in turn. For the self-energy diagrams, all paths through the subdiagram (which must be considered when evaluating the d MSFweight) contribute a non-zero amount (all diagrams we consider are connected to x, y, z). Consequently, the factor in the d MSF -weight for the subdiagram is independent of the ordering π ′ E restricted to the subdiagram, and then the weight reduces to the same expression as in percolation. (This is not true, however, for the 1PI subdiagram that contains the path vertex at z.) The application of the O MSF operator and the sum over orderings π ′ E can now be carried out using (II.17). Then the contribution of such a self-energy diagram is the same as in percolation. The self-energy diagrams can be formally summed to all orders in perturbation theory to yield the self-energy Σ(q, t 0 ), and then each of the two series of alternating G 0 (q, t 0 )'s and Σ(q, t 0 )'s can be summed as a geometric series, giving the full Green's function G(q, t 0 ), We pause to point out that the 2point connectedness function for MSF(p), in which we do not require the path on the MSF to pass through any particular point z, is similarly shown in this diagrammatic point of view to be the same as in percolation, and is given by G(q, t 0 ). Consequently, the exponent η defined above for p = p c must be the same as the similarlydefined exponent in percolation. The MSF path connectedness function, with zero momentum entering at the path vertex, can now be written formally as where Γ (2,PV) (q, 0; t 0 ), which we call the path vertex function, is the Fourier transform of the sum of all 1PI diagrams with two external points (connected to x, y), plus the path vertex at z, which has here been assigned zero momentum. (The generalization to Γ 2,PV (q 1 , q 2 ; t 0 ) should be obvious.) Diagrams contributing to Γ (2,PV) are depicted in figure 1. Similarly, we also define, for the N -point connectedness functions G (N ) (q 1 , . . . , q N ) without the path vertex (N = 2, 3; G (2) = G), and the 2-point connectedness function with a mass (or φ 2 ) insertion, which are the Fourier transforms of the percolation functions G (2) = C x,y , G (2,1) = C z x,y : 16) In these functions, a δ-function that sets the total wavevector to zero has been removed, and {q i } stands for the ordered set q 1 , . . . , q N . This causes a minor difference in notation from that for the path vertex function above: in the functions G or Γ containing N or N + 1 wavevector arguments, one of the wavevectors could be eliminated, which is what was done in Γ (2,PV) above, and we occasionally do this for the others also without further comment. The functions Γ (N ) and Γ (N,1) are called the 1PI vertex functions (of the types indicated). We identify Γ (2) The problem of calculating the path exponent D p has now been reduced to the calculation of the 1PI path vertex function Γ (2,PV) . The external lines G are the same as in percolation, because of the factorization and ordering independence of the weights for the self-energy diagrams. (Similar, but more subtle, factorizations play an important role in the later part of the argument also.) The FIG. 1: Perturbation expansion for the path vertex function given in (III.6). We represent the path vertex by the open circle connected to a wavy line. Note that these diagrams do not include any notation corresponding to the operation of OMSF. The lowest non-trivial term is the second one on the right-hand side.
path vertex, on the other hand, is not the same as the mass-insertion vertex in percolation which it resembles.
To illustrate the perturbation expansion, let us now evaluate the first correction, of order g 2 0 , to Γ (2,PV) (see Fig. 1) at zero external momentum. From the rules given above, this correction comes from the graph with three propagators connected to form a triangle, and the contribution is (note that A ′ = 1 for this graph) where the last integral is .

(III.18)
Here t 3 is the mass-squared on the edge not adjacent to the path vertex. Our momentum-space rules required us to integrate up to radius Λ. Since the diagram is evaluated at zero external momenta, it is symmetric under permutations of the {t ǫ } and (III.19) Applying (II.8), we have d MSF (△|π) = 0 for the two orderings in which t 1 and t 2 > t 3 , and d MSF (△|π) = −1 for the other four orderings. Thus the result is For the corresponding simple mass-insertion vertex in percolation, the result would be instead Dropping g 2 0 and numerical factors, the contribution to the path vertex function behaves like the integral (III.21) At present, we are interested in this for fixed Λ as t 0 → 0, so as to reach p = p c . We see that for d > 6, (III.21) behaves as Λ d−6 as Λ → ∞, and is finite (for any Λ) as t 0 → 0. But for d < 6, the reverse is the case: the integral converges as Λ → ∞, but diverges (for any Λ) as t (d−6)/2 0 as t 0 → 0. In the borderline case d = 6 the integral diverges logarithmically at both ends. For non-zero external wavevectors, the dependence of the integral on Λ is the same in all cases. Note that similar statements apply for percolation; only the numerical prefactor is different.
There are similar results for diagrammatic contributions with more loops. Simply counting the number of propagators and integrations gives the "superficial degree of divergence", which for the path vertex function is always ∼ g 2 0 Λ d−6 or g 2 0 t (d−6)/2 0 for d > 6 and d < 6 respectively, raised to the power of the number of loops (independent cycles) in the diagram, as in the one-loop example above. Note that this is the same as if the O MSF operator were absent, because O MSF leaves the overall degree (in k, at t 0 ≃ 0) of the integrand unchanged. The consequence for perturbation theory at fixed Λ and d > 6 is simple: each term in the perturbation expansion of Γ PV for MSF(p) (p ≃ p c ) is finite as t 0 → 0. This is true for the self-energy diagrams on the external lines also, and the value of Σ(q, t 0 ) at q = 0 determines an effective shift in the value of t 0 that corresponds to p = p c : p c must correspond to the value of t 0 such that t 0 − Σ(0, t 0 ) = 0, and there are also other finite changes in the normalization of G. (In this case one would wish to sum up self-energy insertions in the lines inside of Γ PV also. However we have not shown that these take the same form as on the external lines. This will be addressed below.) But the consequence is that in each order, Γ PV (q, t 0 ) ∼ O(1) as q → 0 at p = p c , while G(q, t 0 ) −1 ∝ q 2 . This in turn implies that there is no change in the exponents from their lowest order values, η = 0 and D p = D sc = 2. Note that here we disregard the possibility that the sum of an infinite number of finite terms might diverge, which might invalidate the conclusion.
For d ≤ 6, this perturbative argument breaks down as the corrections become arbitrarily large as t 0 → 0, in particular in the region t 0 < g 4/(6−d) 0 (the Ginzburg criterion). In order to handle this, the use of RG techniques becomes essential. These techniques effectively re-sum and redefine the expansion. There are several formulations of the RG. These may be divided into two classes. One class of particularly powerful techniques is the field-theorists' RG, in which the aim initially is to take Λ → ∞ (or a → 0) at fixed separations or momenta, in such a way that the limits of the correlation (or connectedness) functions exist, thus recovering a true continuum theory. This is called renormalization of the theory. Subsequently, the renormalized theory is used to set up the RG, and calculate exponents for d ≤ d c . The leading alternative is the Wilsonian RG, in which the cutoff is kept finite. The Wilsonian RG is more difficult to use for higher numbers of loops. Both approaches lead to equivalent results for physical quantities such as exponents for d ≤ d c , where d c = 6 for percolation and MSF(p c ). In this paper we will follow the approach of the field theorists.
For d > 6, we can see from above that the effective expansion parameter is g 2 0 Λ d−6 . As Λ → ∞, it is then necessary to make g 0 → 0 such that g 2 0 Λ d−6 does not diverge. In fact the situation is even worse than this would suggest: there simply is no rational way to define the limit Λ → ∞ so that the connectedness functions at fixed q and (for example) p = p c have finite limits, without introducing an infinite number of parameters. This is referred to as non-renormalizability of the perturbation expansion. But by keeping the cutoff Λ finite, and using the Wilsonian point of view, we can see that the exponents in this region take their simple zero-loop values, as indicated above. Accordingly, we concentrate on d ≤ 6 from here on in this article.

E. Renormalizability of the theory
In this section we outline our proof that the MSF path vertex theory for d ≤ 6 may be consistently renormalized. The full technical details are in Appendix D. In the interests of making this article more accessible to readers without a field theory background, we take a somewhat pedagogical approach in discussing the renormalizability and the RG calculation in the remainder of this paper. Of course, we do not have the space here for a full description; the interested reader is directed towards any of the standard textbooks such as [30,31].
We saw above that the Feynman integrals associated to diagrams for certain vertex functions are superficially divergent as Λ → ∞ in six dimensions. In fact, closer inspection reveals that subintegrals (integrals over a subset of the loop momenta k, holding the others fixed) may also be superficially divergent, and this can occur even when in integrals that are superficially convergent as a whole, showing that they do not converge after all. However, the superficially divergent integrals (or subintegrals) are associated only with (sub-)diagrams that are, topologically at any rate, of the form of the vertex functions Γ (2) , Γ (3) , Γ (2,PV) , or Γ (2,1) . These correspond respectively to the self-energy, cubic coupling, MSF path, and mass-insertion vertex functions. The first two of these suggest a possible way to eliminate the divergences: add the divergent terms to the mass-squared t 0 and the coupling g 0 , respectively, and define renormalized quantities t and g, and then insist that these are the "physical" or measurable parameters at long length scales. There is also a subleading divergence in the self-energy of order q 2 , which perhaps can be removed similarly by rescaling the field, and hence the Green function (this effect also enters the definition of t). The divergences in Γ (2,PV) and Γ (2,1) can be handled similarly.
This procedure works for conventional field theories at their critical dimension; one such case is the theory of percolation at six dimensions. It is important to recognize why it can work. That is because every occurrence of, for example, a self-energy subdiagram within another diagram occurs with a d weight that can be factored as the d weight for the subdiagram, times that for the quotient diagram, in which the subdiagram is contracted to a single vertex. Further the integrations over wavevectors in a Feynman integral have the property that the integral for a subdiagram always has the same form, independent of the larger diagram of which it is a part. Then the subintegral for any self-energy subdiagram has precisely the same divergence wherever it occurs, independent of the larger diagram of which it is a part. Meanwhile the quotient diagram has the form of a lower order diagram. This enables us to write the leading divergence as a correction to the bare mass-squared t 0 that is contextindependent, and therefore meaningful. The same has to be true for the other divergent subdiagrams (or "renormalization parts"). For percolation, the factorization of the d weights can be easily seen in the Q → 1 Potts model formulation, in which the d-weights arise from contracting together tensors, and then the factorization for subdiagrams is automatic (and similarly for other local field theories). It is not immediately obvious that this will hold for our MSF theory, because: (i) The d weights are replaced by d MSF weights, which depend on an ordering π, may not factor in the fashion required, and in fact for some orderings do not factor; (ii) The O MSF operator and summation over orderings raise similar questions.
In Appendix D we undertake a careful study of these questions. We find that the degree of divergence of a subdiagram for a renormalization part is the same as it would be for the corresponding subdiagram in percolation for certain orderings, and for these the d MSF -weight exhibits the desired factorization properties. Indeed, for the self-energy and cubic coupling renormalization parts, the divergent part has exactly the same coefficient as for percolation. This holds also for part of the subleading divergence in the self-energy case, but there is also another subleading part in that case which does not have these properties. That part is problematic, as the program above provides no apparent way to remove these divergences. However, we eventually find that all such terms cancel, not for a single diagram, but in the sum of diagrams of a given order. In the remainder of this discussion, we will take that for granted, and so continue as if there are no such divergences.
These observations then allow us to absorb all the divergences into the quantities mentioned above. More formally, this amounts to subtracting off the superficiallydivergent contribution for each subdiagram of a diagram (including that, if any, for the diagram as a whole). After doing so, we should prove that the remaining integrals are actually finite. Here again, we cannot simply appeal to the usual field theories, as we have modified the Feynman integrands, and so the proofs must be reconsidered. We complete the proof using the Schwinger parametric integral formulation [32,33,34,35,36], and a theorem by Bergère and Lam [37]. This then completes the proof of renormalizability of our perturbation expansion.
The renormalization procedure removes the divergent parts of the original Feynman integrals. It does not uniquely fix a finite part that may also be subtracted. This part may be determined by giving some renormalization conditions obeyed by the renormalized vertex functions. A convenient choice for the following is to define the values (and a first derivative) of these functions at zero renormalized mass-squared, t = 0 (corresponding to p = p c ), and a non-zero wavevector of magnitude κ.
For dimensional reasons, one or other of t and κ must enter. However, we also mention the scheme of dimensional regularization and minimal subtraction, in which such renormalization conditions are not used. We adopt the present scheme in order to keep things relatively transparent.
The RG is now introduced by obtaining an equation, the RG equation, describing how the renormalized vertex functions behave under a change in κ. As κ decreases, the effective coupling g changes, and may reach a non-zero κ-independent fixed point. This is then used to calculate the exponents for scale-covariant behavior of the vertex functions or correlation functions. The fixed point is at g 2 of order ε = 6 − d, and so the expansion in powers of g is traded for one in powers of ε. This expansion is essential to obtain useful finite results for d < d c = 6. In this way we will obtain the exponents to order ε via a one-loop RG calculation.

F. RG analysis at one-loop order
In the preceding sections and appendix D, we have proved that the diagrammatic expansion for the MSF path theory is renormalizable. These proofs were technical, but having established this fact, we are free to make use of standard RG methods such as those discussed in Ref. [31]. We continue to take a rather pedagogical approach in this section.
As we explained in sections III D and D, renormalizability of a theory means that we may absorb the strong Λ-dependence of all correlation functions into a finite number of parameters and the overall scale of the correlations, at the cost of introducing another scale κ. In the scheme we use, in which the renormalization conditions are at zero renormalized mass-squared t = 0 and non-zero wavevector of order κ, the precise statement is that functions g, Z φ , Z φ 2 , Z PV exist such that (here we append subscripts 0 to denote the "bare" vertex functions as constructed above, with cutoff λ) where Γ R are independent of Λ as Λ → ∞ with g, t = 0 fixed, up to corrections vanishing in this limit. (Here L is the number of insertions of φ 2 , and {q j } is the set of corresponding wavevectors.) We will also now introduce dimensionless versions of the bare and renormalized couplings g 0 , g: (III.24) We introduced an angular factor (4π) d/2 in the above definitions for later convenience to simplify expressions. For the vertex functions not containing the path vertex, the functions and their renormalization is exactly as percolation, and this is also true of the following calculations; we include some details anyway to provide checks on the calculation. The RG equations are obtained from the observation that the bare functions Γ 0 are independent of κ when written in terms of g 0 , so κ∂Γ 0 /∂κ = 0 at fixed g 0 , t 0 , Λ. Using the definition of Γ R we obtain In each of these equations the first and second partial derivatives are at fixed u and fixed κ, respectively. The RG β and γ functions appearing in equations (III.25) (III.26) are defined as and are finite as Λ → ∞ [31]. Hence in the limit they are independent of Λ, and so also of κ, because u, β, and all γ's are dimensionless; they are simply power series in u.
We then impose the following renormalization conditions, which are those we reached in Appendix D, but written now with t = 0 and u in place of g. These serve to fix the dependence of the parameters on one another: (III.31) Here SP denotes a symmetry point of the external momenta q 1 , q 2 , q 3 , at which |q i | 2 = κ 2 , as defined in Appendix D (though the precise definition is unimportant). These conditions are now used to determine β and the γ's from the perturbation theory expansion in g 0 of the 1PI vertex functions Γ 0 with a fixed cutoff Λ. The expressions make sense provided g 0 is sufficiently small. We will calculate to one-loop order, which means that only the one-loop diagrams for the renormalization parts need to be calculated. This will give results for exponents to first order in ε = 6 − d > 0. (More generally, computing to O(ε L ) in the ε-expansion requires computing all the renormalization parts with L or fewer loops.) Then the instances of equation (III.23) with which we need to deal are, to O(g 2 0 ), (III.32) Here d 2 , d 3 are the percolation d-weights for these oneloop diagrams, d 2 = −1, d 3 = −2, and d PV will be evaluated in a moment from the weights d(G) and the operator d MSF O MSF ; the values will be substituted only at the end of the calculation. The negative sign in the equation for Γ R arises because of Dyson's equation.
In equation (III.32), I 2 and I 3 are Feynman loop integrals which we now evaluate. To leading non-trivial order, we can evaluate them at six dimensions, retaining only the terms that diverge quadratically or logarithmically as Λ → ∞. These terms may be extracted by any of the standard techniques for evaluating Feynman integrals, including those in Appendix D; we refer the reader to [31,38,39]  by ≃, we find (III.33) The factor of 1/2 appearing in I 2 (q) is a diagrammatic symmetry factor, A = 2 (in the other diagrams, A or A ′ = 1). Note that the bare propagators appearing in these integrals should have mass-squared t 0 = t c determined so that t = 0, but because t c is O(g 2 0 ) we may consistently neglect its presence here. The other integral is (III.34) For the path vertex function, as we saw above, O MSF (π, t c )I 3 | SP is independent of the ordering π. (Unfortunately, this property does not hold to higher orders in perturbation theory for Γ PV .) The result for a single ordering is Then for brevity we define d PV such that Hence d PV = 1 6 π d MSF (△|π) = −2/3, as we saw above. We may now solve by requiring that the renormalized proper vertices defined on the right-hand side of (III.32) satisfy the normalization conditions (III.31) up to terms of O(u 4 0 ). We obtain to this order Finally, to this order Z φ 2 is the same as Z PV except that d 2 replaces d PV . Note that the Z's are functions only of the dimensionless variables u 0 and κ/Λ, and we can set d = 6 (so ε = 0 and g 2 0 = u 2 0 /(4π) 3 )) in the one-loop terms, but not in zero-loop terms.
The RG functions are 43) The fixed points of the RG are the values of u = u * at which β(u) = 0. Clearly, one fixed point is at u = 0, but is unstable to the introduction of the cubic coupling for d < 6, because u grows as κ decreases, corresponding to the behavior at larger length scales. In six dimensions, u approaches zero logarithmically as κ decreases, because the coefficient of u 3 is d 2 /4 − d 3 = 7/4 which is positive. Below six dimensions, there is another zero of β which results from the competition between the two terms in β, at Note that (u * ) 2 is positive for d < 6 (ε > 0). For d > 6, this fixed point is not relevant to percolation or MSTs. The values of the γ's at the fixed point value of u give the "anomalous dimensions" of the various operators (except that in the case of φ, the anomalous dimension is γ φ /2). These are the difference of the total dimensions x of the operators from their canonical or engineering dimensions, which are the zero-loop values discussed earlier [31]. The co-dimension d − x gives the fractal dimension of the associated geometric object (set of points). The most interesting dimension for us is that of the path vertex, which is x PV = d − 2 + γ PV . The codimension yields the fractal dimension D p = 2 − γ PV of the path on the MSF(p c ), as discussed in section III C. We find This is the main quantitative result of this paper. The other γ's produce fractal dimensions related to properties of percolation, which also apply to MSF(p). First, Hence for the fractal dimension D perc of the critical percolation clusters, which is D perc = d − x φ , we find The other γ is γ φ 2 , for which the value at the fixed point can be obtained from the formula for γ PV by replacing d PV by d 2 , that is and so for the fractal dimension of the set of singlyconnected edges (see section III C) we find The values we have obtained for both exponents η and ν agree with those in the literature on percolation, to order ε [29,40,41], which provides a check on our calculation. The comparison of D p with D sc raises some questions of inequalities obeyed by D p . There are also some other fractal dimensions defined for paths on critical percolation clusters which have been studied. These include D min , the fractal dimension of the shortest path on the cluster between the given points, and D max , the fractal dimension of the longest (self-avoiding) path between them [7]. Here the length of the path is the number of edges of the lattice that it traverses. Then the inequalities are fairly obvious: first, because all these paths must pass through the singly-connected edges, D sc is the smallest of all, and the remaining inequalities follow from the definitions. To order ε, one has D min = 2 − ε/6 and D max = 2 − ε/42 [42], and all the inequalities are obeyed strictly by the results to this order. D p is close but not equal to D min .

IV. CONCLUSION
The results of this paper fall into three main parts. First, we constructed an exact expansion for the Kruskal process, or spanning forest MSF(p), in a series in powers of p, which terminates for a finite graph, and is analogous to a low-density expansion for percolation, or a high-temperature expansion in a statistical mechanical model. The expansion is for the probability that the path on the MSF from x to y passes through a vertex z. Second, this expansion was used to obtain a continuum formulation (with cut-off) for p ≤ p c (where p c is the percolation threshold) in terms of Feynman diagrams (the region p > p c presents additional technical problems, and we will not discuss these further here). This expansion was then shown to be renormalizable to all orders in perturbation theory, so that the limit of infinite momentum-space cutoff (or zero lattice spacing) can be taken. Third, the renormalized perturbation expansion was used to calculate the fractal dimension of any path on MSF(p) at p = p c , to first order in ε = 6 − d, for d ≤ 6: D p = 2 − ε/7 + O(ε 2 ). For d > 6, D p = 2. If the "superhighways" idea is correct, then the same D p also applies to the region p > p c , in which we expect the path dimension to be independent of p on large enough length scales.
It is important to realize that it was by no means obvious at the outset that such a field-theoretic renormalization process would be possible. The problem is not obviously given by a local field theory, and our expansion is not based on an action principle (at least, not in any apparent way). Optimization is generally a nonlocal process as it involves making comparisons among (sums of) costs globally; however, this is also true when one wishes to minimize a Hamiltonian, even if its parameters (corresponding to costs) multiply local interaction terms. For minimum spanning trees, the definition of the allowed or "feasible" configurations (i.e. spanning trees) is not local either. It was not obvious that the expansion would be renormalizable like that of a local field theory. Indeed, in the end our procedure worked thanks to unexpected and non-local cancellations of some subleading divergences (see Appendix D 6), for which we are unaware of any analogs in local field theories. Undoubtedly the underlying reasons for this success with MSTs should be found in the applicability of Kruskal's greedy algorithm and its connection with percolation.
The calculations can be extended in various ways. The exponents can be calculated to higher orders in ε, with increasing effort required for each additional order. The path vertex function, and not only its scaling dimension, can in principle also be studied, as can more general correlation functions with path vertices and mass-insertion vertices. In six dimensions, there are logarithmic corrections to the simple scaling with D p = 2 that holds for dimensions bigger than six, and these are calculable.
Independently of these applications of the renormalized perturbation expansion, the exact lattice low-density expansion could be studied in low orders (say, the first thirty terms) in any dimension d, as is conventionally done with high-temperature series. This would provide another way to obtain scaling dimensions for correlation functions. Such techniques are frequently very accurate.
A further question is the Borel summability of the perturbation expansion, or of the ε expansion for the exponents. If an asymptotic expansion of a function is Borel summable, then it uniquely determines that function. If a few terms of the expansion are available, and it is believed to be Borel summable, then an improved estimate for the quantity of interest, such as an exponent, for a non-zero value of the parameter (say ε = 1) can be made, and for critical exponents these values may be very accurate (comparable with high-temperature series methods). For percolation at threshold, the asymptotic high-order behavior of the perturbation expansion has been shown in Ref. [43] to have the form that is a necessary condition for the expansion to be Borel summable. These results also apply to our theory, but again we also need a similar result for the path vertex function. It would be interesting to find a technique to estimate the high order behavior of our expansion.
In conclusion, the introduction of the Kruskal process and geometric object MSF(p), based on an optimization problem, provides a rich area for study not unlike conventional critical phenomena. At p = p c , many techniques can be applied to it. It illuminates numerical work on such problems as optimal paths and transport in random media.

Acknowledgments
This work was supported by NSF grant no. DMR-0706195.

APPENDIX A: LOW-DENSITY EXPANSION IN PERCOLATION
This Appendix summarizes various results concerning the low-density diagrammatic expansion for percolation. Some of these results have appeared elsewhere in the literature [25,26], but we reproduce them here in order to introduce notation and terminology, and because the derivation in Appendix C below closely follows that given here.
In section A 1 we define the low-density graphical expansion for two-point connectendess functions, which is generalized to the case of n-point functions in section A 2. These sections summarize results given in [25,26]. Finally, in section A 3 we prove that the expansion is the same as that obtained from the conventional description of bond percolation via the low density (high temperature) series for the Q-state Potts model, in the limit Q → 1. The principal results are the graphical expansions (A.9), (A.16) with diagrammatic weights given in simplest form in (A.14), (A.18).

Essam's construction
Essam's expansion for percolation [25,26] is based on the principle of inclusion and exclusion from combinatorics [44]. As this may not be familiar to all readers we summarize it here. We start with a set of events {X i } indexed by i in an index set I. In order to calculate probabilities later we introduce the indicator function The principle of inclusion-exclusion is the expansion where ∨ denotes a logical OR and ∧ denotes a logical AND. An analogous series may be obtained for the conjunction of all the events, by using De Morgan's law ¬(∨ i X i ) = ∧ i (¬X i ), where ¬ denotes logical NOT. This yields Note that in this case I ′ may be the empty set, so the first term of this series is 1.
We apply this to bond percolation at a parameter value p by first investigating the two-point connectedness function, defined as where I c (x, y)| p stands for I c (x, y)| p = I[x, y connected by edges of cost ≤ p] and the angle brackets denote an average with respect to all realizations of the edge costs. Defining Γ x,y to be the set of all self-avoiding walks on the lattice between x and y, we may write where we define the event i.e, we require all edges e on the path γ to be present by the time the parameter is raised to the value p. Using equation (A.2) to expand the right-hand side of (A.6) by inclusion-exclusion yields We obtain an expansion in terms of graphs from (A.8) by grouping together all terms that test the same set of edges on the lattice; the terms in the series are now indexed by graphs G, each obtained as the union of some set of paths Γ ′ ⊆ Γ x,y (possibly from more than one such Γ ′ ). We say that such a set Γ ′ covers (the edges of) G. Because the paths are self-avoiding walks, all the graphs G generated from such unions must be vertex-irreducible: removing any vertex from the graph must leave at least one of the points x, y in each connected component. Let the set of all such graphs with the marked vertices x, y be G x,y .
Letting Γ x,y (G) for G ∈ G x,y denote the set of paths on G connecting the root points x, y, equation (A.8) can be rewritten The average over the costs can be performed immediately. Referring back to the definition (A.5), we obtain the graphical expansion which is independent of the parameter p, and is referred to as the d-weight of the graph G. This expression for the d-weight can be seen to possess the topological invariance property mentioned in section II A: the insertion of any number of vertices of degree two (or, equivalently, replacing edges of G with paths of edges) does not change the set Γ x,y (G) of paths connecting the root points, or the value of I[Γ ′ covers G] for any of the subsets Γ ′ . The definition of d(G) may be extended to cover the case where G is any two-rooted graph as follows: if G consists of more than one connected component, there is no way to cover all its edges with paths connecting the roots, so d(G) = 0. Note that, because the covering criterion is defined in terms of the edge set only, addition of isolated vertices does not change a graph's d-weight. Similarly, if G is not vertex-irreducible, by definition some edgesthe "tadpoles" or "dangling ends" -cannot be covered by a self-avoiding path, since backtracking is forbidden, so again d(G) = 0. Since d(G) vanishes for these additional cases, the sum in (A.10) may be extended to all two-rooted subgraphs of the underlying lattice.
We may make further progress if we remark that the preceding derivation also applies to connectedness functions on an arbitrary graph Λ instead of the whole lattice; the sum in (A.11) is then over appropriate subgraphs of Λ. We denote this connectedness function by C x,y (Λ, p).

Equation (A.10) generalizes to
where G E ′ is the subgraph of Λ consisting of all vertices of Λ and a subset E ′ ⊆ E = E(Λ) of its edges. Evaluating (A.12) at p = 1 yields In the definition of d(G) for G = G E ′ , defined by a subset E ′ of the edges of Λ, we may note that vertices of Λ incident on no edges can be deleted without changing d(G). Now because Λ is an arbitrary graph, and the sum in (A.12) is over over all subsets of E(Λ), we may easily invert this sum by Möbius inversion [44], which for the present case is related to inclusion-exclusion. We obtain (A.14) This form is equivalent to (A.11), but easier to work with as it does not require a sum over the set of paths on G.
We point out that in this argument the sum over paths was only used to arrive at the form (A.10) for arbitrary Λ. Once this is known, the expressions (A.14) for the coefficients were obtained by Möbius inversion with no further reference to paths. This suggests that a shorter derivation may exist.

Extension to n-point connectedness functions
The expansion (A.9) generalizes readily to n-point connectivity functions; the criterion is simply that n root points x 1 , · · · , x n are connected if and only if there exists at least one path from x 1 to each x i , 2 ≥ i ≥ n, where we select x 1 arbitrarily. Note that in enumerating the set of paths from x 1 to x i , we must include those paths that pass through other root points. Using inclusion-exclusion (A.2) and equation (A.6) again, we may write the indicator function for this event as Repeating the previous derivation and grouping together terms that test the same set of edges, we obtain the diagrammatic expansion Again, the fact that d(G) may be computed in terms of sets of paths covering G establishes that it is a topological invariant, unchanged by adding vertices of degree two to G.
The argument following (A.11) also carries though, since the above definition of the d-weight may be extended to arbitrary graphs and we may perform Möbius inversion on the connectedness function evaluated on an arbitrary n-point graph, obtaining Our final results, equation (A.16) with (A.18), constitute a complete low-density expansion for all connectedness properties of percolation clusters.

Equivalence with the Potts model
The development of the field theory for the Potts model is described in detail elsewhere [22,23,29,40] and we will recall only the parts of the derivation that are relevant to our discussion here. The Q-state Potts model on a graph Λ [21] has, associated with each vertex x of Λ, a degree of freedom α(x) which may take on any of Q discrete states ("colors"). The Hamiltonian for this model in the absence is where the sum is over edges indexed by the two incident vertices x, x ′ . The partition function can be expanded in the form [20] where p = 1 − e −βJ and again E = E(Λ). When Q → 1, the partition function becomes Z = 1, and the expansion corresponds to the sum of probabilities for the sets E ′ of occupied edges in bond percolation with independent probabilities p for occupying each edge. The Q-state Potts model partition function, viewed as a function of Q and p, is also (essentially) the Tutte polynomial [24]. The states at each vertex can be represented by an overcomplete set of Q vectors e α , α = 1, . . . , Q, in a Q − 1 dimensional space. These vectors are obtained by projecting the position vectors of a regular Q-simplex in Q-dimensional space onto the subspace orthogonal to the vector (1, 1, . . . , 1). More concretely, if we let the coordinates of these vectors with respect to some basis be e α i , i = 1, . . . , Q−1, the set of vectors may be uniquely defined up to relabeling and change of basis by requiring where we also used (A.24). After removing the factor δ i1,i2 and setting Q = 1, this is equal to C x,y (Λ, p). Now we rewrite (Although this does not explicitly involve the e α i 's, this choice is motivated by the form of eq. (A.25) as Q → 1; note that there are many similar expressions that become equal to this for Q = 1.) We expand the Potts correlation function C i1,i2 (x 1 , x 2 ) using this decomposition for each edge, and then once more for δ α(x),α(x ′ ) − 1 on each edge. This yields Removing δ i1,i2 and setting Q = 1, we recover the expressions eq. (A.12) and (A.14). The derivation can be readily generalized, at least to the 3-point connectedness function. Hence Essam's diagrammatic expansion is identical term-by-term with the low-density expansion of the Potts model in the Q → 1 limit.

APPENDIX B: PROPERTIES OF MST PATHS
In this Appendix we present proofs of properties obeyed by paths on the MST. These properties are used in Appendix C below to construct a diagrammatic expansion for the MSF path vertex.

MST paths as geodesics
We first define a minimax path between two given vertices on the finite graph Λ: a (self-avoiding) path is a minimax path for the pair of (distinct) vertices x, y if among all paths from x to y it has the lowest value of the most costly edge (among all edges on the path). That is, it is a minimum (over the set of paths from x to y) of the maximum (over edges on the path) of the cost of the edge. We note immediately that in general there is more than one minimax path for the given vertices, even though they must all share the same most costly edge (we assume that no two edges have equal cost). We say that a path γ is a geodesic if, for all vertices w, z lying on γ, the subset of γ which connects w, z is a minimax path from w to z. A geodesic passing through x and y is necessarily a minimax path for x and y. Applying the definition of geodesic for the case where w, z are adjacent vertices connected by a single edge, we see that we may equivalently define geodesics as those paths all of whose edges are minimax paths connecting the vertices to which they are incident. We note that a geodesic cannot be a cycle, so it must have endpoints. We may also remark that the geodesic path is the correct strong disorder limit of the optimal path [9], that which minimizes the total cost of all edges on the path with fixed endpoints.
It is not always well-appreciated in the literature that a minimax path is not unique, see for example [10,12,15,45], which frequently refer in the singular to "the" minimax path between two points. These sources really mean the geodesic path, which we will now prove is unique.
We now prove that there is a unique geodesic between any two given vertices, say x, y (provided they are on the same connected component of the underlying graph), provided that all edge costs are distinct. Specifically, we let γ be a geodesic and we will show that no other path γ = γ which shares the same endpoints may also be a geodesic. We noted above that any minimax path from x to y, such as γ, must pass through the same most costly edge e 1 . However, at this stage it is not clear that they all do so in the same direction. But if we consider the endpoint of e 1 that is encountered first on walking along γ from x to y, say w, then any minimax path, such as γ, from x to that endpoint must pass through the same edge e 2 , which is the most costly on the subpath (but clearly less costly than e 1 ). (If w = x, then we can start from y instead, and if e 1 has endpoints x and y then we are done.) Note that this shows that γ traverses the edge e 1 in the same direction as γ, because otherwise the most costly edge on the minimax from x to w would be e 1 . Using induction on the number of steps on γ, we find that γ must be the same as γ.
By elementary properties of MSTs, all paths on the MST are geodesics. Likewise, all geodesics are contained in the MST, because in particular each of their edges is minimax for its two incident vertices, which is a property of the MST. Indeed, the MST of a graph is the union of all of its minimax edges.
It is amusing to realize that the MST has the ultrametric property (the content of this paragraph will not be used elsewhere in the paper). Let us assume that the costs are non-negative (if not, we can add a positive constant to all of them). Then we can obtain a notion of distance, or metric, ∂ between any two vertices on the graph Λ, by defining ∂(x, y) to be the largest (or minimax) cost on a minimax path from x to y, with ∂(x, x) = 0 if x = y. By definition, a metric should be finite and non-negative, symmetric (∂(x, y) = ∂(y, x)), equal to zero if and only if x = y, and obey the triangle inequality. The first three properties are clear, while it is easy to see that ∂ obeys the stronger property that, for any x, y, z, These four properties imply that ∂ is an ultrametric. Note that the ultrametric inequality eq. (B.1) implies the triangle inequality. For ordinary metric spaces, one defines geodesics to be paths of shortest "length" using the metric, and this motivates our terminology above. Further, if x, y, z are three distinct points, the ultrametric property implies that if ∂(x, y) ≤ ∂(x, z) and ∂(y, z), then ∂(x, z) = ∂(y, z). It is well known that an ultrametric space with a finite number of points can be viewed as a tree, which we imagine depicted with the points as the leaves located on a hyperplane, other vertices to one side of the hyperplane, connected by straight lines, and the ultrametric represented by the height above (in the direction orthogonal to the hyperplane) the leaves to which one must go in walking from one leaf to another along the tree. In the present case, this essentially corresponds to the MST. The tree is trivalent (except at the leaves) with probability one. The trivalent vertices represent the edges on the MST, with their height as their cost. In fact, if we consider the subforest of the tree consisting of the vertices at height less than or equal to some bound, then this represents the MSF(p).

Identifying MST paths through binary comparisons
Let γ MST (x, y) be the geodesic from x to y, or equivalently the path on the MST. The geodesic property of γ MST (x, y) allows it to be selected from the set Γ x,y of all paths connecting x, y by means of repeated comparisons using a binary ordering relation ≺, defined as follows. Let γ and γ ′ be two paths in Γ x,y . Let e 1 , e 2 , · · · e n be the first, second, ... n-th most expensive edges on γ, and likewise for e ′ 1 , e ′ 2 , · · · e ′ n on γ ′ . We say γ ≺ γ ′ if and only if there exists some j such that ℓ ej < ℓ e ′ j and ℓ ei = ℓ e ′ i for all i < j: in other words, we compare the most expensive edges whose costs are not identical. We will prove that γ MST (x, y) = min γ∈Γx,y γ; (B.2) in other words, γ MST (x, y) is the minimal element of the set Γ x,y under the ordering defined by ≺.
Again, we assume all edge costs to be distinct, which implies that e i = e ′ i ⇐⇒ ℓ ei = ℓ e ′ i and ¬(γ γ ′ ) ⇐⇒ γ ≻ γ ′ : i.e., the relation ≺ defines a total order on the set of all paths between fixed endpoints. Under this assumption, for any two paths γ, γ ′ ∈ Γ x,y we have Let γ be a path satisfying In particular, γ is less than all paths in Γ(γ; x, y) ⊂ Γ x,y , the set of paths in Γ x,y having no edges in common with γ. By (B.3), this means ≺ compares only the most expensive edges on the paths, so if γ ≺ γ ′ ∈ Γ(γ; x, y) then γ must be a minimax path for x and y.
Similarly, for any subpath γ ⊆ γ with endpoints w, z, we define Γ(γ; w, z) ⊂ Γ x,y as the set of those paths that coincide with γ from x to w and from y to z, and have no edges in common with γ; in other words, the set of those γ ′ such that γ−γ∩γ ′ = γ. Because γ ≺ γ ′ ∈ Γ(γ; w, z), γ is a minimax path from w to z. This holds for all choices of w and z, and hence γ is a geodesic. It is unique and can be identified as a path γ = γ MST (x, y) on the MST by the results above.
We finally note that identifying MST paths through the definition (B.4) is most convenient for the purposes of our diagrammatic expansion (II.18). It would be very inefficient computationally, since we make many unnecessary comparisons with paths that are not in any of the sets Γ(γ; w, z). On the other hand, the geodesic characterization of MST paths is less directly useful for our purposes, since it requires keeping track of the locations of the most expensive edges. The geodesic properties of MST paths are very useful computationally: they are essential in constructions of linear-time algorithms for MST path verification [46] which were used in [47] to give a randomized algorithm which constructs the entire MST in linear time.

APPENDIX C: DERIVATION OF LOW-DENSITY EXPANSION FOR MSF PATHS
In this Appendix we derive the exact low-density expansion for the probability C z x,y (p) that the points x, y are connected by a path on the MSF(p) which passes through z, on a finite graph Λ.
First, we can formally define an indicator function However, for each graph in the expansion of this probability, the relevant event is that the maximal path of the covering Γ ′ passes through z.
We may now take the expectation value of I c (x, y; z)| p over all realizations of the edge costs in order to obtain the analogue of (A.10), We note that the ordering π E(G) and the event that all edges of G be less than p are independent, so the last probability factorizes. Because the edge costs are iid, all orderings of the edge costs are equally probable and Pr[π] = 1/|E(G)|!. We may find an alternative expression for d MSF in terms of a sum over edge subsets instead of sets of covering paths, analogous to our derivation of (A.14) from (A.11). The argument proceeds the same way: we first make explicit the dependence of MSF path connectedness functions on the graph Λ in the set G x,y,z of graphs containing the three root points x, y, and z, writing it C z x,y (Λ, p). Because (C.11) contains a factor of I[Γ ′ covers G] in the summand, we also have d MSF (G|π) = 0 for disconnected or vertex-reducible graphs. The sum in (C.12) may therefore be extended to all subgraphs of G as Because d MSF (G|π E(G) ) is dependent on π, we must work under the sum over edge cost orderings in performing the Möbius inversion step. We therefore work with the conditional quantity (C.14) appearing as a summand in (C. 13). Evaluating this at p = 1 yields where γ MST (G|π) is the path connecting the root points x, y on the minimum spanning tree of G obtained under the edge cost ordering π. Möbius inversion of this sum gives This definition of d MSF is more convenient than (C.11) for the proofs of appendix D 4. It is also, in principle, more convenient for computation, since for large graphs the size of the set Γ x,y (G) of self-avoiding walks grows faster than |E(G)|, hence the sum in (C.16) is more easily performed than that in (C.11).

APPENDIX D: RENORMALIZABILITY OF THE MSF PERTURBATION EXPANSION
In this section we give the proofs outlined in Section III E, which establish that our perturbation expansion for MSF paths is renormalizable. Recall that diagrams of this theory with no path vertex are identical to those of percolation theory and hence pose no problem, while we construct diagrams involving the MSF path vertex by the substitution (III.7): where the integrals I(G) and I(G, {t ǫ }) are identical Feynman integrals with only cubic interaction vertices, containing the factor g 0 for each such interaction, but in the latter integral the mass-squared t 0 is generalized to a distinct parameter t ǫ for each edge ǫ of the graph G. In this Appendix, we will drop the prime from the orderings π ′ throughout; orderings π E(G) are nonetheless the induced orderings on the set of highest costs L ǫ of the set E(G) of edges ǫ ∈ E(G) of a topological graph (Feynman diagram) or subgraph G. d MSF and O MSF were defined in (II.8), (III.5) respectively, and as defined both depend on the structure of the entire graph G. In particular, it is not entirely evident from the definition (II.8) how d MSF (G|π) could be computed from knowledge of its values on subgraphs of G.
The Appendix is structured to give proofs of the following results. We begin in section D 1 by introducing terminology common to all sections of this Appendix and explaining the parametric formulation of Feynman integrals. In section D 2 we obtain the effect of the O MSF operator, which is very simple in the parametric formulation: it introduces a simple product factor F π into the integrand, which depends on the choice of an ordering π for the costs on the graph.
In section D 3, we prove that the superficially-divergent subintegrations (as the cutoff Λ → ∞) associated to a connected subgraph H come only from a subset S ′ ⊂ S |E(G)| of all possible orderings on the edges of G. Specifically, if H is a three-point subgraph or a 2-point subgraph containing the path vertex, then S ′ = π [0] , in which all costs in the subgraph are cheaper than all those outside. Similarly, if H is a two-point subgraph (i.e. a selfenergy), the only superficial divergences are for orderings S ′ = π [0] ∪ π [1] , in which at most one edge in H has cost higher than one or more outside H. Moreover, for these orderings, with one class of exceptions the divergences in self-energy or cubic coupling (3-point) subgraphs are the same as those in the corresponding percolation diagrams, up to the d-weights. These results generalize easily to diagrams with several superficially-divergent subdiagrams, if these are pairwise either disjoint or one inside another.
Having identified the important orderings, we consider in section D 4 the behavior of the d MSF weights for these orderings. We show that the weights obey nice factorization properties for connected subdiagrams with two or three external points for orderings in class π [0] , and also (in a different, more general form) for self-energy subdiagrams H with orderings in which one or more edges in H is more costly than at least one outside H. The factorization has the form if the path vertex is not in H (note the appearance of a d-weight from percolation), and 3) if the path vertex is in H. The precise definitions, in particular for π E(G/H) , will be given in section D 4. Here and below we use notation G/H to denote the diagram obtained by contracting the subgraph H to a single vertex (which may be of degree 2, producing a harmless extension of the class of diagrams to be considered).
In section D 5 we come to the heart of the proof. We use a theorem of Bergère and Lam [37] to show that the Feynman integral for each diagram in our perturbation expansion can be rendered absolutely convergent by a procedure of subtracting all the superficially divergent parts of the integrand. Furthermore, utilizing the results of preceding sections, all the terms that have to be subtracted for divergent subdiagrams (including those containing the path vertex) are the same as those for a corresponding full diagram, with the exception of one class of terms as mentioned above, which is dealt with in section D 6. Subject to the latter result, this means that all divergences are dealt with by renormalizing parameters and the overall scale of the vertex functions, as in a renormalizable field theory.
Finally, in section D 6 we prove that the class of exceptional subleading divergences in the self-energy subdiagrams cancel in the sum over all diagrams of a given order. This completes the proof of renormalizability to all orders in the perturbation expansion.

Definitions
We begin by considering an arbitrary Feynman integral associated with a diagram G appearing in the perturbative expansion of a correlation function in, for example, the field theory of percolation.
First, we recall the expression for a Feynman integral associated with G given in eq. (III.2). Let V, E be the ver- tex and edge sets of G, and let N ǫ,v be its incidence matrix under an arbitrary orientation of its internal edges; i.e. Neglecting the cut off for a moment, the integral with which we are concerned is Here (k ext ) v is the net external momentum incident on the vertex v. Since we will replace the percolation dweight with the appropriate d MSF -weight, we neglect the factor d(G) and also g 0 to the power of the number of internal cubic vertices (or other couplings for interactions of different degree that may be present more generally). We make progress by expressing the Feynman integral (D.5) in terms of integrals over the Schwinger parameters α. This makes use of the identity 1/X = ∞ 0 dα e −αX to rewrite part of the integrand as (For brevity, we let A G denote the set of parameters α ǫ introduced above.) The total of d|V | δ-functions can be rewritten using the identity 2π δ(k) = dλ e iλk for each. Integrals over the internal momenta q ǫ are now Gaussian and can be performed, and then the λ-integrations become Gaussian and can be performed, except for one which produces a δ-function expressing conservation of the total momentum, (2π) d δ d ( v∈V (k ext ) v ). Omitting this δ-function, we have Here ∆ is a |V | × |V | matrix, which is a Laplacian on G, defined by and P (A G ) is defined as in which the determinant det ′ is that of ∆ with one row and column removed, so as to remove the zero mode. k ext is viewed as a |V |-component vector, and L = L(G) is the cyclomatic number of G, the number of independent loops (cycles) of G. P (A G ) is a homogeneous polynomial of degree L. These expressions are quite general and may be obtained for the diagrams of any field theory; for a further discussion consult [32,33]. It is interesting that P (A G ) and also ∆ −1 can be related to weighted sums over spanning trees on G [32,33] by the Kirchoff matrixtree theorem [44]; it is not clear to us whether this fact is deeply involved in the renormalizability of the theory of MSF(p). For many diagrams, the integral I(G) as written in (D.5) or (D.7) is ultraviolet divergent and must be regularized, which is done by restricting the momentum integrations in (D.5) to the region |q ǫ | < Λ. We implement this in (D.7) by taking the range of integration of each of the α ǫ to be [Λ −2 , ∞), which exponentially suppresses contributions from |q ǫ | ≫ Λ.
We make use of the parametric representation for Feynman integrals for two reasons. First, it greatly simplifies the study of renormalization of the expansion, as in the field theories in [33,35,36,37].
The second reason we employ the parametric representation is that, as we show in the next Subsection, the action of O MSF takes a particularly simple form. Application of O MSF directly to (D.5) results in intractable integrals over the {t ǫ } for diagrams beyond one-loop order, while we are able to obtain its action on an arbitrary graph in closed form in equation (D.11).

Effect of OMSF operator
The preceding discussion applied to the diagrams from the field theory for percolation. To investigate how things change when we calculate MSF diagrams, we specify a given total ordering π of the masses of G, such that i < j ⇐⇒ t π(i) > t π(j) . (D.10) The diagrammatic contribution to the MST theory is obtained by summing over all total orderings of edge costs consistent with the placement of the path vertex, according to (C. 16). To find the contribution from one ordering π, we apply the operator O MSF (π, t) defined in (III.5) to both sides of (D.6), obtaining (D.11) The integrand on the right-hand side is that appearing on the right-hand side of (D.6), multiplied by a factor , (D.12) (We note that F π (A G ) is of the same form as we obtained on the lattice in equation (II.15). This is another manifestation of the well-known equivalence between scalar field theory and a system of random walkers.) Thus finally our prescription for evaluating the contribution of each diagram is that it is given by the parametric Feynman integral as for percolation, but with the factor inserted inside the α integrals, replacing the d(G) weight for the percolation theory. The factor F π (A G ) obeys 0 ≤ F π (A G ) ≤ 1 for any A G ∈ [0, ∞) |E| , and has the property that it reduces to one as we go towards the limit in which α π(1) ≪ α π(2) ≪ · · · ≪ α π(|E|) . (D.14) It tends to suppress orderings which do not obey the version of these inequalities in which all ≪'s are replaced by <'s. Thus it acts to replace the strict inequalities on the t ǫ 's by corresponding but softer conditions on the α ǫ 's. This result makes intuitive sense: high-momentum (small α) propagators correspond to lattice walks consisting of relatively few edges. In the Kruskal process, we expect the shortest paths to be completed first, at the lowest value of p, corresponding to a larger mass-squared t 0 . It will be useful to simplify the F π factors as much as possible, by performing (or partially performing) the sums of d MSF (G|π)F π over orderings π as much as possible before performing the integrals. We now give some basic formulas that are a step in this direction. First, we obtain another proof of (II.17) from the fact that A more general fact that will be useful is that if we consider a subset of edges E ′ ⊆ E of E and orderings π such that the masses on edges of E ′ are greater than all those in E − E ′ , and sum over all such orderings that fix an ordering on E − E ′ (such orderings can be written as π = σ • π 0 for π 0 any one such ordering and σ a permutation in S E ′ ⊂ S E ), then: , (D. 16) in which the right-hand side is independent of the choice of π 0 . This follows by using eq. (D.15) applied to the restricted sum over orderings. Indeed, as the derivation of this identity only used the sum over a smaller set, this can be used in a proof by induction (on the size |E|) of eq. (D.15) itself. The induction step, of taking |E ′ | = |E| − 1 and summing the right-hand side eq. (D.16) over cosets S |E| /S |E|−1 is simple.

Estimating MSF Feynman integrals
In this Subsection, we describe how the divergent behavior of a given diagram of the MSF path theory differs from that of the diagram from percolation theory from which it was obtained, and obtain some basic statements about the form of the divergences for each ordering.
In the absence of the F π factor, the parametric form of the Feynman integrals may in general suffer from divergences associated with the region α → 0 for some or all α's. These take the place of the possibly more familiar divergences at large k in the original momentum space integrals over q ǫ ; recall that the latter integrals have already been done, after exchanging orders of integration. For a 1PI graph G, the superficial degree of divergence of I(G) is obtained easily from the momentum-space form by counting the total number of powers of all q ǫ 's and integrations d d q ǫ , and is given by This formula holds for any field theory of scalar fields interacting via non-derivative couplings. The same result is easily obtained in the parametric representation also [33,35,36,37]. It may be obtained more formally by rescaling the α ǫ → ρ 2 α ǫ for all edges of G, with ρ → 0 + . The formula may also be applied to the subintegral associated with a connected 1PI subdiagram H of G (strictly, a subdiagram is a subset of the vertices of G, together with all edges that connect these vertices); this will be denoted ω(H). In this case, it is obtained from the behavior as the subset of α ǫ associated with edges of H are scaled to zero by a common factor. Notice that the superficial degree of divergence for a subgraph H might be larger than that for G. A graph or subgraph is said to be superficially divergent if its superficial degree of divergence is positive or zero, and superficially convergent if its superficial degree of divergence is negative. (A graph with ω = 0 may diverge more slowly than any power of Λ, for example logarithmically, or may be convergent.) It is a theorem that if ω is negative for G and for all its subgraphs, then the associated Feynman (parametric) integral is absolutely convergent. For the theory with cubic interactions that we consider here, the only connected 1PI graphs that are superficially divergent at d = 6 dimensions are (a) any self-energy diagram (with two external points), because all have ω = 2, (b) any vertex correction diagram, that is a graph with three external points, because all have ω = 0, and c) a self-energy graph with a φ 2 insertion, which have the same form as the vertex diagrams in b). Here in a) and b) an external point means that a line that "leaves" the graph (joined to it by a cubic vertex like the others) was removed to leave the 1PI part. The graphs containing φ 2 are relevant to the path vertex that we wish to consider in this paper. Other graphs are superficially convergent.
Turning to our theory for MSF(p), the parametric form of the Feynman integral for a given ordering π is simply modified by the insertion of the factor F π (A G ). Because F π (A G ) is bounded, it follows that the superficial divergence of any diagram or subdiagram of the MSF theory is no worse than the corresponding diagram of percolation theory from which it was obtained. More formally, F π is a homogeneous rational function of degree zero, and so the superficial degree of divergence for G is again ω(G).
However, for a subgraph H of G, F π (A G ) may reduce the superficial degree of divergence below ω(H). Recall that for a subdiagram, we consider the limit as α ǫ for ǫ ∈ E(H) go to zero simultaneously, by scaling them with a common factor ρ 2 , leaving α ǫ for ǫ ∈ G − H unchanged. Considering each of the |E(H)| factors in F π (A G ) that have numerator α ǫ for an edge ǫ ∈ E(H) appearing in (D.12) in this limit, we see that in this limit ρ → 0, We may add this result to the superficial degree of divergence to obtain the overall superficial degree of divergence of a connected 1PI subdiagram H of a connected 1PI diagram G under the ordering π: 2n π (H, G).
(D. 20) This implies that it is only for class π [0] that the superficial degree of divergence of the subgraph H is unchanged by F π . For subgraphs with ω(H) = 0 (i.e. the vertex and path vertex diagrams), orderings other than those in π [0] give convergent subintegrals. For the self-energy subgraphs, with ω = 2, orderings in π [1] lower the superficial degree of divergence to 0, and these are additional divergences with which we will have to deal. Moreover, in all cases there are subleading terms in the behavior of F π as ρ → 0 for a subgraph, and while these terms are superficially convergent in most cases, the first subleading term also has zero superficial degree of divergence in the case of the self-energy subdiagrams. For further analysis, it is helpful to consider the sum π d MSF (G|π)F π (A G ) and to attempt to simplify it as much as possible, so that the evaluation of the parametric integrals reduces to those for percolation as much as possible. Indeed, by the "contribution of a diagram" in general we mean the weighted sum over orderings. In order to consider divergent subintegrals for subdiagrams, it is useful to have factorization properties of the weights d MSF . It is to this that we turn next.

Factorization properties of MSF diagrammatic weights
In this section we demonstrate that the diagrammatic weights d MSF possess enough factorization properties for our proof of the renormalizability of the perturbation expansion to go through. Let us first recall that for the d-weights in percolation, the weight for a diagram G containing a 2-or 3-point subdiagram H factors into the weight for H times that for the "quotient graph" G/H in which the subgraph H is shrunk to a single vertex (formally, its vertices are identified, and its edges are deleted): d(G) = d(H)d(G/H). This is immediate in the Potts model formulation in which the d-weights originate from contracting together tensors, due to S Q permutation symmetry (apart from the problem of giving a formal definition of the Q → 1 limit). It can also be derived from the combinatorial definitions described in Section A (this is shown in the case of some 2-point subdiagrams in Ref. [26]). It is important for the proof of renormalizability, as the contributions of such subgraphs in Feynman integrals will be treated as "correcting" or "renormalizing" the parameters attached to 2-and 3-point vertices in the graphical expansion. We require some similar properties in the expansion for MSF(p c ).
Recall that the weights can be defined as in eq. (C.16) This differs from the diagrammatic weight for percolation (A.14) only in the presence of the additional indicator function I . A graph that is not 1PI can be decomposed into (connected) 1PI subdiagrams lying on a chain of single edges and such 1PI parts that form a path from x to y, and possibly other 1PI parts. That is, G may be constructed as a tree G 0 (with x, y, z marked) which is then decorated by replacing its vertices v with subgraphs H v . As the MSF path must pass through a chain of 1PI parts, it follows that for those 1PI subdiagrams that do not contain the vertex at z, the indicator I (z) c is independent of the path through such a 1PI subdiagram, and accordingly the d MSF weight factors into a product of weights for the single edges and for the 1PI parts. Moreover the d MSF factor for each such 1PI subdiagram reduces to d in percolation for that subdiagram (for a single edge, the weight is 1). Likewise, for a vertex-reducible subdiagram or "tadpole", such as a 1PI part connected to the rest by a single edge, the d MSF -weight is the same as in percolation and vanishes. Similarly the d MSF weight for a diagram that contains a disconnected subdiagram vanishes. Hence from here on we need consider only connected, vertex-irreducible 1PI diagrams G that contain the path vertex at z, as well as root points that we can relabel as x, y.
For MSF(p), the weights d MSF depend on the ordering π of the costs of the edges of the topological graph G, as well as on G. In this section, we will denote these costs by the original symbol ℓ ǫ for edge ǫ ∈ G (these costs in fact stand for the maximum, earlier denoted L ǫ , of the chain of edges that are the image of ǫ under an embedding of G in the lattice). In terms of the costs, the ordering π is defined by i < j ⇐⇒ ℓ π(i) < ℓ π(j) .
(D.22) (We use the costs, rather than the mass-squared's for which the inequalities are reversed, because the authors find that this aids their intuition about MSTs.) In seeking a factorization similar to that for the d-weights in percolation, there are two issues. Because the d MSF -weights depend on a choice of ordering, one issue is whether some factorization holds at all for each ordering, and a second is, if there is some factorization, what ordering would be used for the quotient G/H. What we obtain below may not be the most general possible result. Instead we obtain statements for two (overlapping) sets of conditions, and these are sufficient for our purposes. Motivated by the considerations of which orderings produce ultraviolet-divergent Feynman integrals associated with a subgraph, we first show that for orderings π such that all edges in a connected subgraph H have lower cost than all others in G, where H is a 2-or 3-point subgraph, and in the 2-point case the vertex z can also be present, factorization holds: Here the right-hand side involves the ordering π H , which is π restricted to H, and π G−H which is π restricted to G − H. (For graphs G, subgraphs H, and quotients G/H, we will allow abuses of notation like π E(H) = π H .) Further, in the case in which H does not contain z, we already know that d MSF (H|π H ) = d(H). We recall that these orderings are those in class π [0] , which produce the leading divergence for the 2-or 3-point subgraphs. Further, the factorization generalizes to the case in which there are several disjoint such subgraphs, and the costs in the union of the sets of edges of the subgraphs are lower than those in the remainder of G (regardless of the relative orderings among the edges in the subgraphs). In this case, each disjoint subgraph carries a weight as for the single subgraph considered above. Then, because the 2point (or self-energy) subgraph (that does not contain z) also has subleading divergences that occur when its costs do not obey the preceding conditions, we also derive a more general result for such a subgraph for any ordering. These results can be combined to handle a large class of orderings and subgraph structures. , does not connect all the root vertices, then there is at least one root vertex not connected to any of them (this does not hold for a subgraph with more than three root points). Choose one of these, and without loss of generality suppose it is x 1 . In G there is a single edge incident on x 1 that is not in H (call it ǫ x1 ). The minimum spanning tree path γ MST (G E ′ |π E ′ ) from x to y on E ′ clearly cannot pass though x 1 for such an E ′ , whatever the ordering π. We can pair off such subsets E ′ by choosing pairs of E ′ which are the same subsets except that the edge ǫ x1 is in one and not in the other. These subsets differ in size by one, and the indicator function I ; it is here that the form of the ordering enters. The case in which all edges in the subgraph H have costs lower than all those in G−H is quite simple. First, the same property is inherited in the ordering π E ′ restricted to E ′ . As the Kruskal process runs on E ′ , these edges are tested first, and when that is completed the root points of the subgraph are connected (this follows because we have shown that E ′ connects these vertices). For the remainder of the process, from which the path γ MST (G E ′ |π E ′ ) is obtained, the subgraph H [or its diluted version which we denote H E ′ (H) ] can be viewed as collapsed to a single vertex to produce G E ′ /H E ′ (H) . It is useful now to distinguish two cases: either z is in H, or it is not. In the first case, the MSF path must enter H to reach z, and then leave. This implies that a) on G E ′ /H E ′ (H) , the image of H is the point through which the MSF path must pass, and b) once within H the path must pass through z. That is, For graphs with several disjoint subgraphs of the same type as the single connected subgraphs considered above, the same proof goes through if all edges in all the subgraphs are less costly than those outside. That is, the edges in one of the connected subgraphs need not be all more, nor all less, costly than those in another one of the subgraphs. Thus this result is more general than simply iterating the application of the preceding result, though the final factored form of the d MSF -weight is the same as if it were.
We now turn to a more general argument for the case of a connected 1PI 2-point subgraph H and any ordering π. It holds if the path vertex z is within H, however for orderings not in the class π [0] which are already covered by the preceding proof, the corresponding Feynman integrals are convergent, so we will not make of this, and can assume that z is not in H.
Let ǫ H be the most costly edge in H for the ordering π. Now we consider the evaluation of the d MSF -weight. For each diluted edge-set E ′ , this involves comparison of paths from x to y (which exist because the contribution to d MSF vanishes if x and y are not connected). We saw above that we can assume that the root points x 1 , x 2 of H are connected by E ′ (H). Further, there are paths from x to y through H E ′ (H) , because otherwise H E ′ (H) is either disconnected from both x and y, or is part of a tadpole, and in either case the weight vanishes as we saw above. To find the MST path from x to y, the task can be broken into subtasks, and one of these is first to find the MST path through H E ′ (H) between its root points. If the MST path from x to y passes through H E ′ (H) , the portion within H E ′ (H) must be this MST path. We now show that (within the sum defining d MSF ) this path γ MST (H E ′ (H) |π E ′ (H) ) between x 1 and x 2 must pass through the most costly edge ǫ H of H. For suppose that ǫ H ∈ E ′ (H), but the MST path does not traverse it. Then there is another edge set which is the same as E ′ except that ǫ H is omitted, and these terms cancel in pairs (note that the MST paths are the same for these edge sets). But the terms with ǫ H ∈ E ′ (H) and ǫ H on γ MST (H E ′ (H) |π E ′ (H) ) do not cancel in a similar way, as removing ǫ H from this edge set leaves the root vertices x 1 and x 2 disconnected, and we know that those edge sets cancel among themselves. The reason the root vertices become disconnected on removing ǫ H (so H E ′ (H) is not 1PI) is that if not, then a less-costly path (in the sense of the ordering ≺ in section B 2) between the roots would exist.
It follows that in comparing possible MST paths on G E ′ , the subgraph H E ′ (H) can be replaced by a single edge from x 1 to x 2 with cost ℓ ǫH . We use this result to define the induced ordering π G/H for the quotient graph for such a 2-point subgraph H; this ordering gives the ordering for any diluted edge set E ′ (G/H). Note however that here we are forced to view H as replaced by an edge, not a vertex, in the quotient graph. [Further, H is bordered by two other edges, and these three edges form a chain, which by the general elementary arguments given earlier can be replaced by a single edge of cost the maximum of the costs of the three edges, for the purposes of finding the MST path γ MST (H E ′ |π E ′ ) from x to y.] We can summarize this whole argument as showing that the indicator function can be written as  Fig. 5). This agrees with the result for an ordering in class π [0] (because then π G/H = π G−H ), but gives the correct generalization to other orderings, for the case of a 2-point subgraph. For other orderings, the highest cost in H has to be compared with those in the remainder of G; we emphasize again this aspect of the definition of π G/H . In the present case, the argument can simply be used again if G/H contains a 2-point subgraph. For 3-point subgraphs, we expect that a more complicated generalization exists, but we have not looked for it.

Proof of renormalizability
In this section, we assemble the preceding results to describe the divergences of the diagrams or subdiagrams in MSF(p) theory, and compare them with the corresponding ones in the perturbation expansion for percolation. Here by a diagram, we mean the corresponding Feynman integral, including the sum over orderings of the d MSF F π factors inside the parametric integral. The initial results provide the direct motivation for the renormalization of the perturbation series. Then we describe the proof of renormalizability.
We saw in section D 3 that for a subdiagram H and an ordering in the class π [0] (or for the whole diagram G, and any ordering), the superficial degree of divergence ω MSF (H, G|π) is the same as ω(H). We consider only 2-or 3-point subdiagrams, including the 2-point subdiagram that contains the path vertex. For any fixed ordering on the edges E(G) − E(H) not in H, we can consider the sum of d MSF (G|π)F π (A G ) over all the orderings π H of edges in E(H) such that the ordering of all edges is in π [0] . For each ordering in the sum, we saw in section D 4 that the d MSF weight reduces to d MSF (H|π H )d MSF (G/H|π G−H ) (for the path vertex case) or d(H)d MSF (G/H|π G−H ) (for the other cases). For the latter cases in which the path vertex is not in H, the weight d MSF (G|π) is independent of the ordering π H , and the sum over the latter can be performed using eq. (D. 16), which shows that the part of the F π associated with the subdiagram has reduced to unity, as in eq. (D.15). The remaining factor on the right hand side of eq. (D.16) depends on the α's for the subdiagram, but of course not on their ordering. To leading order as all those α's are scaled to zero, the resulting subintegration has exactly the same divergence (not only degree of divergence) as the corresponding subdiagram in the field theory of percolation near criticality [including the d(H) weight], and the remaining F π factor is that for the quotient graph, F πG−H (A G/H ). (Note that here we disregarded the possibility that H itself contains a subdiagram that is divergent; this will be handled later.) For the path vertex, the leading divergence of the subintegral is not identical to any in the percolation theory, as the sum of F π over π H does not reduce to a factor unity for the subdiagram; the 2-point vertex function with a mass (φ 2 ) insertion, which it resembles, is different, though it has the same degree of divergence [an example of such an integral was discussed in eq. (III. 20)]. Nonetheless, the weighted sum of F π has similar factorization properties.
Motivated by these observations, we aim to prove that our perturbation expansion for the path vertex function can be renormalized in a manner very similar to that for percolation. Indeed, the mass, field, and coupling renormalizations will be exactly the same as in percolation, even when they occur inside a 1PI diagram for the path vertex function (we saw earlier that this is so for the self energy parts outside the 1PI path vertex function, that is connected to this function by a single line). For the path vertex itself, the renormalization works and takes a similar form as that for a mass insertion in percolation, but the coefficients are different. We will prove this to all orders in perturbation theory. First, we will establish that it is possible to perform subtractions as in ordinary field theory Feynman diagrams (e.g. for percolation), with the result that our subtracted amplitudes are non-diverging for each graph in every order in perturbation theory. Then we will show that, because of a cancellation of some sub-leading pieces involving selfenergy insertions, the subtractions take the same form as in percolation, as indicated above. This then leads almost immediately to the RG equations, and the epsilon expansion for the exponents.
The idea for rendering the Feynman integral associated to a diagram finite is intuitively simple. We identify all the diverging sub-integrations associated to subdiagrams of the types already listed above (called "renormalization parts"), for which the divergence is related to the behavior of the integrand as a corresponding set of α parameters is scaled to zero, and then subtract away these parts of the integrand. One would hope that the resulting integrand is then convergent, and even absolutely convergent. It is necessary to prove this non-obvious result, which we will do using results from the literature.
The procedure is somewhat complex because a given diagram may contain several diverging subdiagrams. The subdiagrams may themselves contain diverging subsubdiagram (these are revealed by considering several dilatation parameters ρ i attached to distinct subdiagrams, which go to zero in some order). These possibilities cause no problems for disjoint subdiagrams (that have no common edges), nor for a nested sub-subdiagram (entirely contained in a subdiagram). The case of subdiagrams that are neither disjoint nor nested, called "overlapping divergences", is more difficult, but turns out not to be a problem. One makes subtractions corresponding only to non-overlapping and nested subdiagrams. The procedure was defined by Bogoliubov and Parasiuk in recursive terms [48], finiteness was proved by Hepp [49], and a non-recursive definition in terms of "forests" was given by Zimmerman [50]. Together, this formulation is called the BPHZ method. These authors worked in terms of momentum-space integrals. For the later formulation and proofs within the parametric formulation, see Refs. [35,36,37] and the review in Ref. [33]. We briefly outline the result due to Bergère and Lam [37] that we will use. First it will be useful to introduce the "generalized Taylor operators" T n [36,37]. For a function f (x) of a positive variable x that behaves as > 0), and for our purposes with ν an integer, (such a function is said to have the Taylor series property) these are defined for any integer n to extract the Laurent-like series of terms: (where a 0 , . . . a ν+n are complex numbers) with properties T n f (x) = 0 if n < ν, and (1 − T n )f (x) ∼ x q with q > n. While the series has the Laurent form, we do not assume f is complex differentiable away from 0, and the coefficients can be calculated from f at positive x only, by ordinary Taylor expansion of x −ν f (x) at x = 0. For a function of several variables x 1 , x 2 , . . . , we may define generalized Taylor operators T ni xi similarly by acting with one of them at a time, but we must be careful as they do not generally commute.
In the following these operations will be applied acting on some subset E ′ of α's for a graph G by a dilatation parameter ρ as ρ → 0, and then setting ρ = 1 in the result: . Thus these extract precisely the leading and subleading terms that we have been discussing, up to order n. Here when f ({ρ 2 α i : i ∈ E ′ }, {α i : i ∈ E ′ }) has the Taylor series property as a function of ρ, we say it has it with respect to the set E ′ , and it is in this case that the operator T n E ′ is defined. We will need some definitions for properties of the functions to which the Theorem applies. We will consider what Bergère and Lam [37] call a "nest" of edge subsets, which is a filtration, that is a set N = {E 1 , . . . , E r } of edge subsets such that 31) in which the inclusions are strict except possibly the last. For a function Z(A G ), we say that it has the "simultaneous Taylor series property" with respect to the filtration N if there is a set of integers ν Er such that ( t r=1 ρ −νE r r )Z(ρ 2 A G ) has simultaneous Taylor series in the set of ρ r near, and does not vanish at, ρ r = 0 for all r; here ρ 2 A G stands for the ordered set A G of α's, but each α i acquires a factor ρ 2 r for each subset E r to which i belongs. For example, the function 1/(α 1 + α 2 ) has the simultaneous Taylor series property for the filtration Now we can state (a special case of) the theorem of Bergère and Lam: if (i) Z(A G ) is infinitely differentiable for 0 < α i < ∞; (ii) Z(A G ) and its α derivatives are polynomially bounded when arbitrary subsets of A G are scaled to ∞; (iii) Z(A G ) has the simultaneous Taylor series property with respect to every filtration N of edge subsets, then the integral with t > 0 is absolutely convergent. Here the R operation is the subtraction operator which can be defined as where the sum is over all filtrations N of the set A G of α's. In its general form, the theorem applies to many integrals that are not related to Feynman diagrams in any obvious way. Now we wish to apply it to the Feynman integrals in our perturbation expansion. First we point out that these integrals do satisfy the hypotheses of the theorem. Indeed, the integrands of our integrals contain factors that occur in the field theory of percolation, which for this purpose is no different from a cubic-interaction scalar field theory, times the factor F π for some ordering π (times d MSF and summed over π, but we need not consider this here; this sum can be exchanged with the integral and then taken under the R operation if desired). The integrand in the cubic theory satisfies the conditions, and it is easy to see that the F π factor does not change this.
To go further, we note that when applied to Feynman integrals based on a graph (the graph made no appearance in the statement of the theorem), R can also be expressed in many other ways, one of which is as the sum over forests of renormalization parts [37]. As we know, a forest is a collection of trees, but here the trees are not spanning trees on our lattice or our graph G. Instead, a forest is any set of renormalization parts in G (which are 1PI connected 2-or 3-point subdiagrams), such that for any two such parts in the set, either one is entirely contained in the other (both for its vertices and its edges), or else they are disjoint. (Often in the literature, a forest is pictured as a set of non-intersecting boxes overlaid on the depiction of the Feynman diagram.) In this form for R, the sum over all filtrations is replaced by a sum over all forests, and each edge set E ′ in the product is that of a single renormalization part belonging to that forest. We note that in the BPHZ formulation, whether in parametric form or not, no divergent integral or cutoff is mentioned. The subtractions are carried out instead on the integrand (which however, before the subtractions are performed, does have the property of diverging more strongly in some limits).
We will apply the Theorem to the integral for a diagram G, in which the sum over orderings, and d MSF factors, are taken into the integrand. That is, Our earlier remarks imply that for each renormalization part, the subtractions (in forest form) remove precisely all the superficially divergent pieces and no more. Thus in this form, the R operation is exactly what one might expect it to be from the discussion preceding the statement of the theorem, and the theorem says that these subtractions result in an absolutely convergent integral.
For subdiagrams H of a diagram G, these subtractions are exactly the same as those for a diagram of the same type (number of external points, and presence or absence of the path vertex), with one exception. This is the subleading superficial divergence in the case of H a self-energy subdiagram. In the subleading generalized Taylor expansion (that is, T −2|E(H)| − T −2−2|E(H)| acting on the dilatation factor for the subdiagram), part of it comes from expanding F π to order α (for some α in the subdiagram) times the leading term from the percolation integrand; the terms from F π arise from orderings in class π [1] and from subleading terms in class π [0] . This does not correspond to the subtraction made to any whole diagram, and would thus be difficult to include in the renormalization scheme. Fortunately, these subtractions cancel, not for the given diagram, but between diagrams of the same order that differ only in the placement of the self-energy insertion in the graph. This cancellation result will be proved in section D 6 below. Hence because we are always interested in the sum of all diagrams in each order anyway, the only subtractions that have to be made correspond to those that would be made to G when it is a renormalization part. It follows that the subtractions correspond to subtracting the Taylor series in k 2 for the subdiagram, where k is the wavevector entering the subdiagram, and replacing the original graph by the quotient by the subdiagram, times these Taylor coefficients in place of the subdiagram. For the vertex and path vertex cases, the subtraction is simply at zero wavevector, while for the self-energy the first order term in k 2 has to be subtracted also. This is easily seen, as the subtractions to G itself are just its Taylor expansion in k 2 to the given order [33,35,36,37]. If we include the zero-loop parts of the vertex functions, this implies that the renormalized vertex functions in this renormalization scheme obey Γ (2) R (0; g, t) = t, d dk 2 Γ (D. 35) In view of the condition on the 2-and 3-point vertex functions at k = 0, the coupling and mass-squared appearing in the propagators in the expansion can be identified with the renormalized values, so there is no subscript zero on these quantities. Now that the renormalized perturbation series defining the Γ R are known to be finite, for example at non-zero wavevectors away from the point 0 at which the above conditions are given, we can modify the renormalization scheme. Namely, we can add a finite part (more accurately, a series of finite terms) to each subtracted piece in the definition of the renormalized integrand. These can be chosen in each order to modify the renormalization conditions, and the combinatorics again works out. This changes the renormalization scheme, and for example we can modify the conditions above to specify values at non-zero wavevectors (except for the mass-squared): Γ (2) R (q = 0; g, t) = t, d dq 2 Γ Here SP = symmetry point denotes a symmetric configuration of external momenta q 1 , q 2 , q 3 , which (by rotational symmetry) we take to be any triple satisfying q 2 i = κ 2 for i = 1, 2, 3, q i · q j = −κ 2 /2 (i = j). Note that g and t now have a different meaning than before. In this form, we can now set t = 0 and work directly at the critical point, as in each order in perturbation theory the non-zero wavevector scale κ prevents the left-hand-sides from diverging in the infrared (the self-energy −Γ (2) (0; g, 0) is not infrared divergent). This renormalization at zero mass-squared is quite convenient technically.
As we mentioned above, the BPHZ subtraction scheme requires no reference to, nor use of, a cutoff. It is possible to develop the RG equations directly from this scheme, working with non-divergent expressions only, and leading for example to the Callan-Symanzik equation when the renormalization scheme at zero wavevector, non-zero t is used [51]. However, for calculational purposes, we prefer to write intermediate quantities in terms of expressions that diverge as Λ → ∞ as in traditional approaches. The bare vertex functions are given by the original, unsubtracted Feynman integrals with cut-off, including as always the d MSF F π factors. For emphasis, we now write these as Γ 0 's. They are viewed as functions of the bare coupling g 0 and mass-squared t 0 , as well as the wavevectors and cutoff λ. Then all the subtractions that define the renormalized amplitudes can be collected into changes of the parameters to g and t = 0, and changes in the scale of the "operators" φ, φ 2 and that described by the path vertex. That is and in the limit Λ → ∞ the dependence of all Γ R on Λ drops out. These equations require five equations to define the dependence of Z φ , Z φ 2 , Z PV , g 0 , and t 0 on g, κ, and Λ, and these are provided by the five conditions (D.36), when these are expanded in perturbation theory in g 0 . At this point the treatment of our theory has come to closely resemble an ordinary field theory, the main difference being the form of the Feynman rules for calculating Γ (2,PV) . The most important conclusion of the analysis is that the path vertex is renormalized multiplicatively by Z PV . We describe in the main text the derivation of the RG equations, and the calculation of exponents to one-loop order.

Cancellation proof for subleading terms
In this section we present the proof that the particular subleading terms in the Laurent expansion as the α's in a self-energy part (not containing z) go to zero, that do not appear for the self-energy in an external line, actually all cancel among graphs with the same self-energy part inserted in different edges.
First we show that the dependence on the α's in a selfenergy of the weighted sum of F π factors simplifies. We suppose throughout this section that we consider a fixed graph G 0 with an ordering π 0 , and we then modify this graph to obtain G i by inserting a given self-energy graph H on an edge i of G 0 . Thus, the edge i is replaced by two edges i ′ , i ′′ , with the self-energy H in between. In the parametric integral for the diagram, the parameter α i in G 0 is replaced by parameters α i ′ , α i ′′ , and there are additional parameters for the edges of H.
We know from Section D 4 that the d MSF weight for G i is determined by the ordering π Gi/H in which the cost replacing the original ℓ i is the largest of ℓ i ′ , ℓ i ′′ and those in H, independent of how these are ordered relative to each other. Moreover, the weight factors as Throughout the argument, we will compare cases in which π Gi/H = π 0 (in an obvious sense), and is fixed. The sum of the F π factors over the orderings of the edges that replace i can be calculated, and this is done most easily by returning to the original calculation of F π from the action of the O MSF operator in section D 2. The desired sum has the effect of simplifying the integro-differential operator to the following form, and acting under the parametric integral gives , (D. 40) where (i) D is the usual (|E(G 0 )|-dimensional) integration domain for G 0 with ordering π 0 , defined by t π0(1) > · · · > t π0(|E(G0)| > t 0 , and in the integrand, t i ′ , t i ′′ , and the t's associated to edges in H are all set equal to t i , and (ii) α ′ j are the same as α j except for α ′ i , which is the sum of α i ′ , α i ′′ and all the α's in H. The product on the right-hand side is simply F π0 for G 0 but with this substitution; we denote it F ′ π0 (i). A second trick that is commonly used for parametric integrals is also useful: if the integrand only depends on the sum of two parameters, say α 1 and α 2 , then these integrations can be combined into a single integral over α which takes the place of α 1 +α 2 , at the cost of introducing a factor α into the integrand: (This can be generalized to any number of variables, but we do not require that.) It can be shown that, like the weighted sum of F π factors, the rest of the parametric integrand only depends on the sum α i ′ + α i ′′ (this can be shown by some further use of the relation, mentioned earlier, of this integrand to combinatorics of weighted spanning trees, which we do not enter into). Then we use this result to recover an integral over a single α i in place of those two. We now consider the generalized Taylor expansion of the integrand with respect to a dilatation parameter ρ applied to the α's in H. The leading behavior is seen to give simply the integrand for H from percolation (with zero external wavevectors), times the integrand and F π0 factor for the quotient graph, as discussed above. We now turn to the subleading terms of a particular form: those that come from expanding the above factor F ′ π0 (i) to first order in ρ 2 (or simply in α's in H), times the leading behavior of the rest of the integrand, as ρ → 0. The rest of the integrand factors into that for the quotient graph times that for the subgraph, and we make use of the technique for replacing the α i ′ , α i ′′ by α i . This factor in the integrand is now independent of which edge i of G 0 was chosen for insertion of H. The d MSF factor is also independent of i because of the choices of ordering made earlier. Let us write α s.e. for the sum of α's associated to H. There are two types of terms in the expansion of F ′ π0 (i) at first order in α s.e. for each i: a) those in which α s.e. appears in the numerator, in which case it replaces α i , so giving the factor α s.e. /α i times F π0 ; b) those in which it comes from expanding a denominator, which must be one of those indexed j ≥ π −1 0 (i). This gives a factor − α s.e. / j k=1 α π0(k) times F π0 . We remember to multiply by α i (because we replaced two α's by this one), and then sum over the positions i of the self-energy insertion. This gives What we have shown is that this type of subleading term actually cancels in the sum of diagrams in each order. Because the superficial degree of divergence of a selfenergy diagram at six dimensions is 2, these subleading parts are also superficially divergent, and are subtracted for each diagram by the R operation defined earlier. We view the present result as showing that the subtracted terms cancel, and because the sum of the subtracted integrals is finite, these subtracted terms can be dropped and the result is still finite. The cancellation is independent of other subtractions associated with renormalization parts, which might appear either inside H or disjoint from it. In particular, this allows the cancellation to be made for any number of self-energy insertions in a graph. The remaining terms subtracted from a self-energy insertion are then exactly those that occur in percolation, for any number of self-energy insertions.
The principle underlying these pleasant cancelations is not entirely clear to us. It seems likely (because they involve the derivative of the self-energy in percolation with respect to t) that they are associated with the notion that the O MSF operator should be renormalized, so that it acts on t rather than t 0 . This operator has the property that it is invariant under any reparameterization of the variables t ǫ → T ǫ = T (t ǫ ) provided that T is a monotonic function and has no explicit dependence on ǫ (this invariance of the geometry of MSTs is related to that emphasized in Ref. [12]). This property of O MSF was not explicitly used anywhere in our construction. We will not attempt to give here a conceptual proof using these ideas.