RECURRENT RANDOM WALKS, LIOUVILLE’S

THEOREM, AND CIRCLE PACKINGS

Tomasz Dubejko

Mathematical Sciences Research Institute

Abstract. It has been shown that univalent circle packings filling in the complex plane C are unique up to similarities of C. Here we prove that bounded degree branched circle packings properly covering C are uniquely determined, up to similarities of C, by their branch sets. In particular, when branch sets of the packings considered are empty we obtain the earlier result.

We also establish a circle packing analogue of Liouville’s theorem: if f is a circle packing map whose domain packing is infinite, univalent, and has recurrent tangency graph, then the ratio map associated with f is either unbounded or constant.

1 Introduction

Over the period of last several years various results linking circle packing with other, classical, fields of mathematics have been established ([Bo],[D1],[HSc],[RS], [St1],[Th2]). The most prominent connection is the one with analytic function theory, which was originally suggested by Thurston in [Th1]. However, recent developments ([BeSc],[HSc],[Mc]) point to an equally interesting relation between the theory of circle packing and graph theory. This relationship was first observed by Stephenson ([St1],[St2]) who used Markov processes and electric network-type arguments to prove Thurston’s conjecture (cf. [RS],[Th1]). The “analytical” side of circle packing theory has predominantly contained, until very recently, results about univalent circle packings. These include the existence and uniqueness statements, and the finite Riemann mapping theorem. On the other hand, the “graphtheoretical” side gives, for example, an answer to the type problem for graphs in the language of circle packing.

In [D1] and [D2] the author expanded “analytic” circle packing theory to the non-univalent case by proving results that have well-known parallels in the classical setting. Specifically, notions of discrete Blaschke products and discrete complex polynomials, and associated with them branched circle packings, have been introduced. As the new concepts have arrived, new questions have been posed. In particular, since it has been shown ([RS],[Sc],[St3]) that univalent circle packings which cover the complex plane C are unique up to similarities of C, it is natural to ask whether the analogous fact holds for branched circle packings. More precisely,

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 52C15, 30C62, 30G25, 60J15.

Key words and phrases. circle packing, discrete analytic maps, random walks.

Research at MSRI is supported in part by grant no.DMS-9022140.

is it true that circle packings which are proper branched coverings of C are uniquely determined, up to similarities of C, by their branch sets? This paper gives the positive answer to the above question in the case of circle packings of bounded degree; the exact statement is contained in Theorem 4.2. The proof of Theorem 4.2 uses both analytical developments of [D2] and graph-theoretical developments of [HSc] and [Mc]. With the help of [D2] we show that two proper branched circle packing coverings of C with identical branch sets must have comparable radius functions; using [HSc]/[Mc] and random walk techniques we prove that there are no nontrivial bounded perturbations of a circle packing whose combinatorial pattern of tangencies is a recurrent planar graph (see Corollary 3.2). These two results yield the uniqueness of branched circle packings. Particularly, we obtain the uniqueness of univalent packings.

Although this paper was motivated by studies of circle packings, it is worth mentioning that Corollary 3.2 is actually a special case of Theorem 3.1 when labelled complexes of the theorem are replaced by circle packings. Roughly speaking, Theorem 3.1 says that if two labels ρ_{1} and ρ_{2}, of a 2-complex 𝕂 with recurrent 1-skeleton, are such that the curvature of the labelled complex 𝕂(ρ_{1}) is no larger then that of 𝕂(ρ_{2}) then either ρ_{1} ≡ cρ_{2} for some constant c > 0 or ρ_{1} is not comparable with ρ_{2}. To prove the theorem we use variational methods (cf. [CdV]) and results about random walks. Also, as a special case of Theorem 3.1 we obtain a circle packing version of Liouville’s theorem (Corollary 3.3).

We finish our introduction with the following remark. As graphs can be divided into two types of classes, recurrent and transient, similarly circle packings can be divided into two types of classes, parabolic and hyperbolic (see [BSt1]); in the case of packings of bounded degree, a circle packing is of parabolic/hyperbolic-type if and only if its combinatorial pattern of tangencies is a recurrent/transient graph, respectively. Thus, this paper deals with circle packings of parabolic-type. We would like to mention that the existence and uniqueness questions for hyperbolic-type branched circle packings are addressed in [D4]. Techniques used in [D4] are quite different from the ones used here as they reflect the distinction between hyperbolictype packings and parabolic-type packings.

2 Vital Facts

In this section we will introduce essential terminology and definitions. We will also recall several facts regarding labelled complexes, circle packings, and random walks.

We begin with labelled complexes and circle packings; the interested reader should see [Bo], [BSt2], [D1], and [D2] for more details. Let 𝕂 be a simplicial 2-complex given by a triangulation of a domain in C. We will assume, throughout this paper, that 𝕂 is either infinite without boundary or finite, and has an orientation induced from C. Denote by 𝕂^{(0)}, int 𝕂^{(0)}, bd 𝕂^{(0)}, 𝕂^{(1)}, and 𝕂^{(2)} the sets of vertices, interior vertices, boundary vertices, edges, and faces of 𝕂, respectively.

A function ρ : 𝕂^{(0)} → (0, ∞) will be called a label for 𝕂, and 𝕂(ρ) a labelled complex with label ρ (cf. [Bo],[BSt2],[Th2]). If 𝕃 is a subcomplex of 𝕂 and ρ is a label for 𝕂 then 𝕃(ρ) will denote 𝕃 with the label ρ|_{𝕃^{(0)}}. For a face △ = ⟨u, v, w⟩ in 𝕂 let α_{ρ}(v, △) be given by

(2.1) α_{ρ}(v, △) := arccos [\frac{(ρ(v) + ρ(u))^{2} + (ρ(v) + ρ(w))^{2} − (ρ(u) + ρ(w))^{2}}{2(ρ(v) + ρ(u))(ρ(v) + ρ(w))} ] .

Figure 1 shows the geometric interpretation of (2.1).

Figure 1. The angle α_{ρ}(v, △).

If v ∈ int 𝕂^{(0)}, the quantity Θ_{ρ}(v) := ∑_{△∈𝕂^{(2)}} α_{ρ}(v, △) will be termed the angle sum of 𝕂(ρ) at v, and Θ_{ρ} : int 𝕂^{(0)} → (0, ∞) the angle sum function.

Labelled complexes can be regarded as generalizations of more rigid structures called circle packings. We say that a collection P of circles in C is a circle packing for 𝕂 if there exists 1-to-1 relationship between 𝕂^{(0)} and P (𝕂^{(0)} ∋ v ↔ C_{P}(v) ∈ P) such that ⟨C_{P}(u), C_{P}(v), C_{P}(w)⟩ is a positively oriented triple of mutually externally tangent circles whenever ⟨u, v, w⟩ ∈ 𝕂^{(2)} is a positively oriented triple.

Figure 2*. Different circle packings (and their carriers) for the same 2-complex.

*This figure was created with the help of CirclePack by the kind permission of Ken Stephenson

Suppose P is a circle packing for 𝕂. A function r_{P} : 𝕂^{(0)} → (0, ∞) with its value at v ∈ 𝕂^{(0)} equal to the radius of C_{P}(v) will be called the radius function of P. The carrier of P, carr(P), is the underlying geometric complex of P which is isomorphic to 𝕂 (Figure 2). The isomorphism is defined as the function S_{P} : 𝕂 → C which maps each v ∈ 𝕂^{(0)} to the center of C_{P}(v) and then extends affinely to 𝕂^{(1)} and 𝕂^{(2)}. Hence, carr(P) := S_{P}(𝕂).

If △ ∈ 𝕂^{(2)} and v is a vertex of △ then we define α_{P}(v, △) := α_{r_{P}} (v, △). From the earlier geometric interpretation it follows that α_{P}(v, △) is the angle at the vertex S_{P}(v) in the euclidean triangle S_{P}(△). For v ∈ 𝕂^{(0)}, Θ_{P}(v) := ∑_{△∈𝕂^{(2)}} α_{P}(v, △) is said to be the angle sum of P at v. It follows from our definition of the circle packing that for each v ∈ int 𝕂^{(0)} there exists a non-negative integer n_{P}(v) such that Θ_{P}(v) = 2(n_{P}(v) + 1)π. If n_{P}(v) > 0 then v will be called a branch point of P of order n_{P}(v); equivalently we can say that the chain of circles in P associated with the adjacent vertices of v in 𝕂^{(0)} winds (n_{P}(v) + 1)-times around C_{P}(v). The set br(P) ⊂ int 𝕂^{(0)} × N will denote the branch set of P, i.e. br(P) = {(v_{1}, n_{P}(v_{1})), …, (v_{m}, n_{P}(v_{m}))}, where the v_{i}’s, i = 1, …, m, are all the branch points of P.

It is important to realize (see [BSt2]) that if all values of the angle function Θ_{ρ} of a labelled complex 𝕂(ρ) are positive integer multiples of 2π, then ρ ≡ r_{P} and Θ_{ρ} ≡ Θ_{P} for some circle packing P for 𝕂.

When working with labelled complexes it is very helpful to have the notion of subpackings (see [BSt2]). Given a function Θ : int 𝕂^{(0)} → (0, ∞) we say that a labelled complex 𝕂(ρ) is a subpacking or packing for Θ if Θ_{ρ} ≥ Θ or Θ_{ρ} ≡ Θ, respectively. In particular, a circle packing P for 𝕂 is a subpacking or packing for Θ if the labelled complex 𝕂(r_{P}) is a subpacking or packing for Θ, respectively. It turns out that subpackings have a nice monotonicity property: if 𝕂(ρ_{1}) and 𝕂(ρ_{2}) are subpackings for Θ then 𝕂(ρ̂) is also a subpacking for Θ, where ρ̂(v) := max{ρ_{1}(v), ρ_{2}(v)}. The following simple observation is known as Maximum Principle (cf. [D1]).

Fact 2.1(Maximum Principle). Let 𝕂(ρ_{1}) and 𝕂(ρ_{2}) be labelled complexes for 𝕂. If 𝕂(ρ_{2}) is a subpacking for Θ_{ρ_{1}} then either \frac{ρ_{2}(v)}{ρ_{1}(v)} < sup_{v∈𝕂^{(0)}} \frac{ρ_{2}(v)}{ρ_{1}(v)} for all v ∈ int 𝕂^{(0)} or there exists c > 0 such that ρ_{2} ≡ cρ_{1}. In particular, if Θ_{ρ_{1}} ≡ Θ_{ρ_{2}} and 𝕂 is finite then min_{v∈bd 𝕂^{(0)}} \frac{ρ_{2}(v)}{ρ_{1}(v)} ≤ \frac{ρ_{2}(v)}{ρ_{1}(v)} ≤ max_{v∈bd 𝕂^{(0)}} \frac{ρ_{2}(v)}{ρ_{1}(v)} for all v ∈ 𝕂^{(0)}.

The next result deals with a boundary value problem for labelled complexes. Its first part can be easily verified using Maximum Principle and Perron’s methods introduced in [BSt2] (cf. [Bo],[D1],[G]); the second part can be found in [D1] (cf. [Bo]).

Theorem 2.2. Let Θ : int 𝕂^{(0)} → (0, ∞) be a function. Suppose a labelled complex 𝕂(ρ) is a packing for Θ. Then

(i) For any function λ : bd 𝕂^{(0)} → (0, ∞) there exists a unique label ρ_{λ} : 𝕂^{(0)} → (0, ∞) such that 𝕂(ρ_{λ}) is a packing for Θ and ρ_{λ}|_{bd 𝕂^{(0)}} ≡ λ.

(ii) If 𝕂 is a finite triangulation of a disc and Θ(int 𝕂^{(0)}) ⊂ {2nπ}_{n>0} then there exists a circle packing P for 𝕂 contained in the unit disc such that Θ_{P} ≡ Θ and all boundary circles of P are internally tangent to the unit circle. Moreover, P, called Bl-type packing for 𝕂, is unique up to Möbius transformations preserving the unit disc.

Let P and Q be circle packings for 𝕂. A function f : carr(P) → C is said to be the circle packing map (shortly, cp-map) from P to Q if f maps the center of C_{P}(v) to the center of C_{Q}(v) and extends affinely to faces of carr(P). In such a case we call P (Q) the domain (range) packing of f. If P is univalent, i.e. all circles in P have mutually disjoint interiors (in particular, br(P) = ∅), then carr(P) can naturally be regarded as a subset of C and the map f as a function defined in such a subset. If P is not univalent then f should be thought of as a function from the underlying surface of P (=carr(P)).

With the pair of packings P and Q we associate another map f^{#} : carr(P) → (0, ∞) called the ratio map from P to Q. It is defined on 𝕂^{(0)} by f^{#}(S_{P}(v)) := \frac{r_{Q}(v)}{r_{P} (v)} and then extended affinely to 𝕂^{(1)} and 𝕂^{(2)}. As before, depending on whether P is univalent or not, f^{#} can be regarded as a function from a subset of C or from the underlying surface of P. Due to various approximation results (see [D1],[D2],[RS],[St1]), f^{#} should be thought of as a discrete analogue of the absolute value of the complex derivative of the cp-map f.

Before we state the next result we need the following three definitions. We will say that a complex 𝕂 is of bounded degree d if every vertex in 𝕂 has at most d neighboring vertices. A function f : Ω → C, Ω ⊂ C, is of valence M if M is the least upper bound on the number of elements in f^{−1}(z) for every point z ∈ C. Finally, the valence of a circle packing P is defined as the valence of the cp-map from a univalent circle packing to the packing P.

Theorem 2.3. Let P be a univalent circle packing for 𝕂 such that carr(P) = C and 𝕂 is of bounded degree d. Let M be a positive integer. There exists a constant κ = κ(M, d), depending only on M and d, with the following property: if Q is a finite valence circle packing for 𝕂 with finite (possible empty) branch set, say {(v_{1}, n_{1}), …, (v_{m}, n_{m})}, satisfying ∑_{i=1}^{m} n_{i} ≤ M then:

(1) \frac{r_{Q}(v)}{r_{Q}(w)} ∈ (1/κ, κ) for all pairs of adjacent vertices v, w ∈ 𝕂^{(0)},

(2) the cp-map f from P to Q is κ-quasiregular with a decomposition f = ψ ∘h, where h : C → C is κ-quasiconformal and ψ is a complex polynomial with the branch set {(h(S_{P}(v_{1})), n_{1}), …, (h(S_{P}(v_{m})), n_{m})}.

The above fact is a result of Corollary 4.9 and Lemma 5.2 of [D2]. Notice that if br(Q) = ∅ then Q is univalent and f is κ-quasiconformal.

We now shift our attention to the subject of random walks. We will establish basic terminology and notation; the reader should refer to [So] and [W] for more information. If 𝕂 is an infinite simplicial 2-complex given by a triangulation of a domain in C then its 1-skeleton, 𝕂^{(1)}, is a graph. If 𝕂 is of bounded degree then so is the graph 𝕂^{(1)}. A function p : 𝕂^{(0)} × 𝕂^{(0)} → [0, ∞) such that ∑_{w} p(v, w) = 1 for each v ∈ 𝕂^{(0)} will be called the transition probability function and p(v, w) the transition probability from v to w. A stochastic process on 𝕂^{(1)} given by p will be called the random walk on 𝕂^{(1)} with the transition probability p, and denoted (𝕂^{(1)}, p). For the purposes of this paper we assume that

(1) p(v, v) = 0 for all v ∈ 𝕂^{(0)},

(2) p(v, w) = 0 if v and w are not neighbors,

(3) p(v, w) > 0 whenever v and w are adjacent.

An example of a random walk on 𝕂^{(1)} is the simple random walk on 𝕂^{(1)} given by

p(v, w) = \{ \begin{matrix}\frac{1}{δ(v)} & if w is a neighbor of v \\ 0 & otherwise, \end{matrix}

where δ(v) denotes the number of adjacent vertices of v in 𝕂^{(1)}.

A random walk (𝕂^{(1)}, p) is called reversible if there exists a function c : 𝕂^{(0)} → (0, ∞) such that c(v)p(v, w) = c(w)p(w, v) for all v, w ∈ 𝕂^{(0)}. Notice that c(v, w), called the conductence between v and w, given by c(v, w) := c(v)p(v, w) is symetric. Conversely, a symetric function c : 𝕂^{(0)} × 𝕂^{(0)} → (0, ∞) such that ∑_{w} c(v, w) ∈ (0, ∞) for all v ∈ 𝕂^{(0)} defines the reversible random walk (𝕂^{(1)}, p) by p(v, w) = c(v, w)/c(v). Note that in the case of the simple random walk, c(v, w) = 1 for all neighboring vertices v, w. If f : 𝕂^{(0)} → R is a function and (𝕂^{(1)}, p) is a random walk then f is said to be superharmonic with respect to p if for every v ∈ 𝕂^{(0)}

∑_{w} p(v, w)f(w) ≤ f(v).

A random walk is called recurrent if the probability of visiting every vertex infinitely many times is equal to 1. If a random walk is not recurrent then it is called transient. If the simple random walk on a graph is recurrent (transient) then the graph is called recurrent (transient). The following fact is a consequence of Theorem 4.1 and Corollary 4.14 of [W].

Theorem 2.4.

(1) A random walk (𝕂^{(1)}, p) is recurrent if and only if there are no non-constant, non-negative superharmonic functions for p.

(2) Let (𝕂^{(1)}, p) and (𝕂^{(1)}, p̃) be reversible random walks with conductances c and c̃, respectively. If c̃(v, w) ≤ c(v, w) for all v, w ∈ 𝕂^{(0)} then the recurrence of (𝕂^{(1)}, p) implies the recurrence of (𝕂^{(1)}, p̃).

We finish this section with a result that determines a connection between the type of a graph and the type of a univalent circle packing associated with it (see [Mc], [HSc]).

Theorem 2.5. Let 𝕂 be a triangulation of an open disc. If 𝕂^{(1)} is recurrent then there exists an infinite univalent circle packing for 𝕂 whose carrier is C. Conversely, if there exists a circle packing for 𝕂 whose carrier is C and 𝕂 is of bounded degree then 𝕂^{(1)} is recurrent.

3 Variations of labelled complexes

Our goal in this section is to show that there are no non-trivial, angle-sum-preserving, bounded perturbations of a circle packing for an infinite 2-complex with recurrent 1-skeleton. The precise statement is Corollary 3.2 to the following theorem.

Theorem 3.1. Let 𝕂 be a triangulation of an open domain in C with recurrent 𝕂^{(1)}. Let 𝕂(ρ) and 𝕂(ρ̃) be labelled complexes for 𝕂. Suppose 𝕂(ρ̃) is a subpacking for Θ_{ρ}. Then the function A : 𝕂^{(0)} → (0, ∞), A(v) := \frac{ρ̃(v)}{ρ(v)}, is bounded if and only if it is constant.

A proof of the above result will be given shortly, first we draw some corollaries.

Corollary 3.2. Let 𝕂 be as in Theorem 3.1. If P and Q are circle packings for 𝕂 with Θ_{P} ≡ Θ_{Q} then either both ratio functions from P to Q and from Q to P are unbounded or are constant.

The next result is a discrete analogue of Liouville’s theorem for ratio functions.

Corollary 3.3 (Liouville’s Theorem). Let P be a univalent circle packing with carr(P) = C. Suppose f is a cp-map with the domain packing P, and f^{#} is the associated ratio function. If the 1-skeleton of the complex of P is recurrent then either f^{#} is unbounded or is constant.

From Theorem 2.5 we get

Corollary 3.4. Let P be a univalent circle packing whose complex is of bounded degree and carr(P) = C. Then a bounded ratio function with the domain packing P is constant.

To prove Theorem 3.1 we will need the following definition and lemma. We use C^{l} to denote the class of functions with continuous l-th derivative.

Definition 3.5. A collection {ρ(t)}_{t∈I}, I = [0, 1], is called a C^{l}-family of labels for 𝕂 if the following are satisfied:

(i) for each t ∈ I, ρ(t) is a label for 𝕂, (ii) for every v ∈ 𝕂^{(0)}, the map ρ_{v} : I → (0, ∞) given by ρ_{v}(t) := ρ(t)(v) is C^{l}.

Lemma 3.6. Let 𝕃 be a star with m boundary vertices, i.e. a triangulation of a closed disc as in Figure 3. Let {ρ(t)}_{t∈I} be a C^{l}-family of labels for 𝕃. Denote by Θ(t) the angle sum at v_{0} given by ρ(t). If Θ : I → (0, ∞) is non-decreasing then for each t ∈ I

0 ≤ ∑_{i=1}^{m} \frac{1}{ρ_{0}(t)+ρ_{i}(t)} [\begin{matrix}√ & \overline{ρ_{0}(t)ρ_{i}(t)ρ_{i−1}(t)} \\ √ & \overline{ρ_{0}(t)+ρ_{i}(t)+ρ_{i−1}(t)} \end{matrix} + \begin{matrix}√ & \overline{ρ_{0}(t)ρ_{i}(t)ρ_{i+1}(t)} \\ √ & \overline{ρ_{0}(t)+ρ_{i}(t)+ρ_{i+1}(t)} \end{matrix}] (\frac{ρ′_{i}(t)}{ρ_{i}(t)} − \frac{ρ′_{0}(t)}{ρ_{0}(t)}) ,

(ρ_{m+1} ≡ ρ_{1}),

where ρ_{i} : I → (0, ∞) and ρ_{i}(t) = ρ(t)(v_{i}), i = 0, 1, …, m.

Figure 3. A star with m boundary vertices.

Proof. By the hypothesis, 0 ≤ Θ′(t) for all t ∈ I. Notice that

Θ(t) = ∑_{i=1}^{m} arccos [1 − \frac{2ρ_{i}(t)ρ_{i+1}(t)}{(ρ_{0}(t) + ρ_{i}(t))(ρ_{0}(t) + ρ_{i+1}(t))}] .

Therefore

Θ′ = ∑_{i=1}^{m} \frac{1}{\sqrt{1 − (1 − \frac{2ρ_{i}ρ_{i+1}}{(ρ_{0}+ρ_{i})(ρ_{0}+ρ_{i+1})})^{2}}} (\frac{2ρ_{i}ρ_{i+1}}{(ρ_{0} + ρ_{i})(ρ_{0} + ρ_{i+1})})′

= ∑_{i=1}^{m} _{\frac{1}{\sqrt{\frac{(ρ_{0}+ρ_{i})(ρ_{0}+ρ_{i+1})}{ρ_{i}ρ_{i+1}} −1}}} \frac{ρ′_{i}ρ_{0}ρ_{i+1}(ρ_{0}+ρ_{i+1})+ρ′_{i+1}ρ_{0}ρ_{i}(ρ_{0}+ρ_{i})−ρ′_{0}ρ_{i}ρ_{i+1}(2ρ_{0}+ρ_{i}+ρ_{i+1})}{ρ_{i}ρ_{i+1}(ρ_{0}+ρ_{i})(ρ_{0}+ρ_{i+1})}

= ∑_{i=1}^{m} _{\frac{ρ_{0}}{\sqrt{\frac{(ρ_{0}+ρ_{i})(ρ_{0}+ρ_{i+1})}{ρ_{i}ρ_{i+1}} −1}}} [\frac{ρ′_{i}}{ρ_{i}} \frac{1}{ρ_{0}+ρ_{i}} + \frac{ρ′_{i+1}}{ρ_{i+1}} \frac{1}{ρ_{0}+ρ_{i+1}} − \frac{ρ′_{0}}{ρ_{0}} (\frac{1}{ρ_{0}+ρ_{i}} + \frac{1}{ρ_{0}+ρ_{i+1}} )]

= ∑_{i=1}^{m} [\frac{1}{\sqrt{\frac{(ρ_{0}+ρ_{i})(ρ_{0}+ρ_{i−1})}{ρ_{i}ρ_{i−1}} − 1}} + \frac{1}{\sqrt{\frac{(ρ_{0}+ρ_{i})(ρ_{0}+ρ_{i+1})}{ρ_{i}ρ_{i+1}} − 1}}] \frac{ρ_{0}}{ρ_{0} + ρ_{i}} (\frac{ρ′_{i}}{ρ_{i}} − \frac{ρ′_{0}}{ρ_{0}} )

= ∑_{i=1}^{m} \frac{1}{ρ_{0} + ρ_{i}} [\begin{matrix}√ & \overline{ρ_{0}ρ_{i}ρ_{i−1}} \\ √ & \overline{ρ_{0} + ρ_{i} + ρ_{i−1}} \end{matrix} + \begin{matrix}√ & \overline{ρ_{0}ρ_{i}ρ_{i+1}} \\ √ & \overline{ρ_{0} + ρ_{i} + ρ_{i+1}} \end{matrix} ] (\frac{ρ′_{i}}{ρ_{i}} − \frac{ρ′_{0}}{ρ_{0}} ) ≥ 0

□

We can now establish Theorem 3.1. The proof will proceed by contradiction; using variational methods we will generate a random walk which, by the hypothesis of the theorem, cannot exist. The reader might be interested to learn that Colin de Verdière have also applied variational techniques in [CdV] to show the existence of circle packings.

Proof of Theorem 3.1. Suppose that the assertion is false. Then there exist two vertices w_{0}, w_{1} ∈ 𝕂^{(0)} such that \frac{ρ̃(w_{0})}{ρ(w_{0})} ≠ \frac{ρ̃(w_{1})}{ρ(w_{1})} and M := sup_{v∈𝕂^{(0)}} A(v) < ∞. We may assume without loss of generality that ρ̃(w_{0}) = ρ(w_{0}) and ρ̃(w_{1}) > ρ(w_{1}). Define a family F of labels for 𝕂 by

\{ϱ: 𝕂(ϱ) is a subpacking for Θρ, ϱ(w_{0}) = ρ(w_{0}), and \frac{ϱ(v)}{ρ(v)} ≤ M for all v ∈ 𝕂^{(0)}\}.

Notice that F is not empty as ρ̃, ρ ∈ F. It follows from a monotonicity property of subpackings that the label ρ̂ given by ρ̂(v) := sup_{ϱ∈F}{ϱ(v)} is a subpacking for Θρ. From definitions of F and ρ̂ we obtain that ρ̂ ∈ F, and ρ̂ ≥ ρ with ρ̂(w_{1}) > ρ(w_{1}). Hence ρ̂ is not a constant multiple of ρ. Moreover, sup_{v∈𝕂^{(0)}} \frac{ρ̂(v)}{ρ(v)} = M. From

Maximum Principle, \frac{ρ̂(v)}{ρ(v)} < M for all v ∈ 𝕂^{(0)}. This implies that Θρ̂(v) = Θ_{ρ}(v) for all v ≠ w_{0}, and Θρ̂(w_{0}) > Θ_{ρ}(w_{0}) (for if Θρ̂(v_{0}) > Θ_{ρ}(v_{0}) for some v_{0} ≠ w_{0} then there is ϵ > 0 such that ρ̄: 𝕂^{(0)} → (0, ∞), defined by ρ̄|_{𝕂^{(0)}\{v_{0}}} ≡ ρ̂|_{𝕂^{(0)}\{v_{0}}} and ρ̄(v_{0}) = ρ̂(v_{0}) + ϵ, belongs to F).

Let {𝕂_{n}} be a sequence of finite, connected 2-subcomplexes of 𝕂 such that 𝕂_{n} ⊂ 𝕂_{n+1}, ⋃_{n=1}^{∞} 𝕂_{n} = 𝕂 , and w_{0}, w_{1} ∈ int 𝕂_{1}^{(0)}. It follows from Theorem 2.2(i) (and Implicite Function Theorem) that for each n there is a unique C^{1}-family of labels {ρ_{n}(t)}_{t∈I} for 𝕂_{n} such that

(1) ρ_{n}(t)(v) = (1 − t)ρ(v) + tρ̂(v) for every v ∈ bd 𝕂_{n}^{(0)},

(2) ρ_{n}(t)(w_{0}) = ρ(w_{0}) for all t,

(3) Θ_{ρ_{n}(t)}(v) = Θ_{ρ}(v) for every v ∈ int 𝕂_{n}^{(0)} \ {w_{0}} and all t. Observe that the uniqueness in Theorem 2.2(i) gives ρ_{n}(0)(v) = ρ(v) and ρ_{n}(1)(v) = ρ̂(v) for all v ∈ 𝕂_{n}^{(0)}. Since for each v ∈ bd 𝕂_{n}^{(0)} the function ρ_{v,n} : I → (0, ∞), ρ_{v,n}(t) := ρ_{n}(t)(v), is non-decreasing, Maximum Principle implies that for every v ∈ 𝕂_{n}^{(0)} the function ρ_{v,n} is non-decreasing. Thus the function Θ_{w_{0},n} : I → (0, ∞), Θ_{v,n}(t) := Θ_{ρ_{n}(t)}(v), is non-decreasing. Moreover, from Maximum Principle we get for all t ∈ I

1 = min_{v∈\{w_{0}\}∪bd 𝕂_{n}^{(0)}} \frac{ρ_{v,n}(t)}{ρ(v)} = min_{v∈𝕂_{n}^{(0)}} \frac{ρ_{v,n}(t)}{ρ(v)} ≤

max_{v∈𝕂_{n}^{(0)}} \frac{ρ_{v,n}(t)}{ρ(v)} = max_{v∈bd 𝕂_{n}^{(0)}} \frac{ρ_{v,n}(t)}{ρ(v)} ≤ max_{v∈bd 𝕂_{n}^{(0)}} \frac{ρ̂(v)}{ρ(v)} < M.

Hence

(3.1)  ρ_{v,n}(t) ∈ [ρ(v), Mρ(v)]  for every n and all t ∈ I.

Notice that using Maximum Principle we also obtain the following inequalities for small h > 0

0 ≤ ρ_{v,n}(t + h) − ρ_{v,n}(t) = ρ_{v,n}(t) (\frac{ρ_{v,n}(t+h)}{ρ_{v,n}(t)} − 1) ≤

ρ_{v,n}(t) max_{v∈bd 𝕂_{n}^{(0)}} (\frac{ρ_{v,n}(t+h)}{ρ_{v,n}(t)} − 1) = ρ_{v,n}(t) max_{v∈bd 𝕂_{n}^{(0)}} (\frac{ρ_{v,n}(t+h)−ρ_{v,n}(t)}{ρ_{v,n}(t)}) .

Thus, by dividing both sides in the above inequalities by h and then taking the limit as h → 0 we get

0 ≤ \frac{ρ′_{v,n}(t)}{ρ_{v,n}(t)} ≤ max_{v∈bd 𝕂_{n}^{(0)}} \frac{ρ′_{v,n}(t)}{ρ_{v,n}(t)} for all v ∈ 𝕂_{n}^{(0)}, t ∈ I, and every n.

In particular,

(3.2)  0 ≤ \frac{ρ′_{v,n}(t)}{ρ_{v,n}(t)} ≤ M  for all v ∈ 𝕂_{n}^{(0)}, t ∈ I, and every n.

Denote by μ := log \frac{ρ̂(w_{1})}{ρ(w_{1})}. Since μ > 0 and

μ = ∫_{0}^{1} (log ρ_{w_{1},n}(t))′ dt = ∫_{0}^{1} \frac{ρ′_{w_{1},n}(t)}{ρ_{w_{1},n}(t)}dt,

for each n there exists t_{n} ∈ I such that

(3.3)  0 < μ ≤ \frac{ρ′_{w_{1},n}(t_{n})}{ρ_{w_{1},n}(t_{n})}.

Suppose v is an interior vertex in 𝕂_{n}^{(0)} and w ∈ 𝕂_{n}^{(0)} is a neighbor of v. Let w′ and w′′ be the other two vertices in 𝕂_{n}^{(0)} adjacent to both v and w. We define (3.4)

c_{n}(v, w; t) := \frac{1}{ρ_{v,n}(t)+ρ_{w,n}(t)} [\sqrt{\frac{ρ_{v,n}(t)ρ_{w,n}(t)ρ_{w′,n}(t)}{ρ_{v,n}(t)+ρ_{w,n}(t)+ρ_{w′,n}(t)}} + \sqrt{\frac{ρ_{v,n}(t)ρ_{w,n}(t)ρ_{w′′,n}(t)}{ρ_{v,n}(t)+ρ_{w,n}(t)+ρ_{w′′,n}(t)}}] .

Notice that if w is also an interior vertex in 𝕂_{n}^{(0)} then

(3.5)  c_{n}(v, w; t) = c_{n}(w, v; t).

Moreover

(3.6)  c_{n}(v, w; t) ≤ 2\frac{\sqrt{ρ_{v,n}(t)ρ_{w,n}(t)}}{ρ_{v,n}(t) + ρ_{w,n}(t)} ≤ 1.

From Lemma 3.6 we get for every n and t

(3.7)

0 ≤ ∑_{w} c_{n}(w_{0}, w; t) (\frac{ρ′_{w,n}(t)}{ρ_{w,n}(t)} − \frac{ρ′_{w_{0},n}(t)}{ρ_{w_{0},n}(t)})  and

0 = ∑_{w} c_{n}(v, w; t) (\frac{ρ′_{w,n}(t)}{ρ_{w,n}(t)} − \frac{ρ′_{v,n}(t)}{ρ_{v,n}(t)})  for v ∈ int 𝕂_{n}^{(0)} \ \{w_{0}\}.

We now make the following observation. Suppose {s_{n}} is a sequence of functions s_{n} : 𝕂^{(0)} × I → R such that for each v ∈ 𝕂^{(0)}, the s_{n}(v, ·) : I → R, n = 1, 2, …, have uniformly bounded ranges. Then for any sequence {a_{n}} of points in I there are subsequences {s_{n(k)}} and {a_{n(k)}} such that lim_{k→∞} s_{n(k)}(v, a_{n(k)}) exists for every v ∈ 𝕂^{(0)}. This is due to the following diagonalization argument:

We begin by enumerating all vertices in 𝕂^{(0)} so that {v_{i}}_{i=1}^{∞} = 𝕂^{(0)}. Since the maps s_{n}(v_{1}, ·) have uniformly bounded ranges there exist subsequences {s_{n_{1}(k)}} and {a_{n_{1}(k)}} of {s_{n}} and {a_{n}}, respectively, such that {s_{n_{1}(k)}(v_{1}, a_{n_{1}(k)})}_{k=1}^{∞} is convergent. Next, we repeat the above construction for v_{2} with {s_{n_{1}(k)}} and {a_{n_{1}(k)}} instead of {s_{n}} and {a_{n}}, respectively. This yields two subsequences {s_{n_{2}(k)}} and {a_{n_{2}(k)}} of {s_{n_{1}(k)}} and {a_{n_{1}(k)}}, respectively, such that {s_{n_{2}(k)}(v_{2}, a_{n_{2}(k)})}_{k=1}^{∞} is convergent and, of course, lim_{k→∞} s_{n_{2}(k)}(v_{1}, a_{n_{2}(k)}) = lim_{k→∞} s_{n_{1}(k)}(v_{1}, a_{n_{1}(k)}). We continue this process for all v_{i}’s. Then by setting n(k) := n_{k}(k) we obtain desired sequences {s_{n(k)}} and {a_{n(k)}}.

We finish our observation by noting that analogous diagonalization argument is valid when 𝕂^{(0)} in the domains of the functions s_{n} is replaced by 𝕂^{(0)} × 𝕂^{(0)}.

We now return to our sequence {t_{n}} satisfying (3.3). We can assume, by using the inequalities (3.2) and (3.6) and by applying diagonalization argument if necessary, that

f(v) := lim_{n→∞} \frac{ρ′_{v,n}(t_{n})}{ρ_{v,n}(t_{n})} and c(v, w) := lim_{n→∞} c_{n}(v, w; t_{n}) exist for all v, w ∈ 𝕂^{(0)}.

From (3.1), (3.4), (3.5), and (3.6) it follows that

(3.8)  0 < c(v, w) = c(w, v) ≤ 1 for all adjacent vertices v and w in 𝕂^{(0)}.

Also, (3.2) and (3.3) imply

(3.9)  0 ≤ f(v) ≤ M for all v ∈ 𝕂^{(0)}, and 0 = f(w_{0}) < μ ≤ f(w_{1}).

Moreover, from (3.7) we get

0 ≤ ∑_{w} p(v, w) (f(w) − f(v)) for every v ∈ 𝕂^{(0)},

where p(v, w) = c(v, w)/ ∑_{w} c(v, w). Thus the function f̃: 𝕂^{(0)} → R, f̃(v) := M − f(v), is superharmonic for the reversible random walk (𝕂^{(1)}, p) with conductance between v and w equal to c(v, w). From Theorem 2.4(1) and (3.9) we conclude that (𝕂^{(1)}, p) is transient. On the other hand, since by the hypothesis 𝕂^{(1)} is recurrent, Theorem 2.4(2) and (3.8) (recall that the conductances for a simple random walk are all equal to 1) imply that (𝕂^{(1)}, p) is recurrent. This is a contradiction. Hence \frac{ρ̃(w)}{ρ(w)} = \frac{ρ̃(v)}{ρ(v)} for all v, w ∈ 𝕂^{(0)}, and the proof is complete. □

4 Uniqueness of branched packings

We begin this section with the following definition which was originally introduced in [D2].

Definition 4.1. Let 𝕂 be a triangulation of an open disc. A cp-map f is said to be a discrete complex polynomial for 𝕂 if the carrier of the domain packing of f is equal to C and the range packing is a proper, finite, branched covering of C, i.e. f has a decomposition f = ψ ∘ h, where h is a self-homeomorphism of C and ψ is a complex polynomial.

It was shown in [D2] that discrete complex polynomials exist. The range packings of such maps form a natural expansion of the class of univalent circle packings that cover C. However, the uniqueness result for branched packings similar to the one for univalent packings (see [RS],[Sc],[St3]) was proved so far only in the case of packings for regular hexagonal lattice ([D2]). Here we will show the uniqueness of branched circle packings of bounded valence for bounded degree triangulations whose 1-skeletons are recurrent; the case when 1-skeletons are transient is treated in [D4]. In particular, we obtain that range packings of discrete complex polynomials are unique, and furthermore, when branch sets of such packings are empty we get the earlier results of [RS], [Sc], and [St3], which are crucial for approximation schemes (cf. [D1],[D2],[H],[RS],[St1]).

Theorem 4.2. Let 𝕂 be a bounded degree triangulation of an open disc with recurrent 𝕂^{(1)}. Let F_{𝔅} denote the set of all bounded valence circle packings for 𝕂 with identical finite branch sets equal to 𝔅. If F_{𝔅} ≠ ∅ then there exists P ∈ F_{𝔅} such that P is the range packing of a discrete complex polynomial and F_{𝔅} = {zP}_{z∈C}, i.e. all packings in F_{𝔅} are copies of P under similarities of C.

Proof. From Theorem 2.5 we have that there exists a univalent circle packing O for 𝕂 such that carr(O) = C. Since F_{𝔅} ≠ ∅ there is P ∈ F_{𝔅} of finite valence with branch set 𝔅. From Theorem 2.3 it follows that the cp-map from O to P is a discrete complex polynomial. As P was arbitrary we get that all packings in F_{𝔅} are range packings of discrete complex polynomials. We also see that {zP}_{z∈C} ⊂ F_{𝔅}. To finish the proof it is sufficient to show that for each Q ∈ F_{𝔅} there exists a constant c_{Q} such that r_{Q}(v) = c_{Q}r_{P}(v) for all v ∈ 𝕂^{(0)}. However, by Corollary 3.2 it is enough to show that for each Q ∈ F_{𝔅} there is M_{Q} such that

(*)  \frac{1}{M_{Q}} ≤ \frac{r_{Q}(v)}{r_{P}(v)} ≤ M_{Q}  for all v ∈ 𝕂^{(0)}.

The remainder of our proof is devoted entirely to verification of (*).

Fix Q ∈ F_{𝔅}, Q ≠ P. By applying similarities to O, P, and Q if necessary, we can assume that S_{O}(v_{0}) = S_{P}(v_{0}) = S_{Q}(v_{0}) = 0 and r_{O}(v_{0}) = r_{P}(v_{0}) = r_{Q}(v_{0}) = 1 for a designated vertex v_{0} ∈ 𝕂^{(0)}, where the notation is as in Section 2. Denote by f_{1} and f_{2} the cp-maps from O to P and from O to Q, respectively. Notice that f_{1}(0) = 0 = f_{2}(0) and, by Theorem 2.3, f_{1} = ψ_{1} ∘ h_{1} and f_{2} = ψ_{2} ∘ h_{2}, where h_{1}, h_{2} are entire K-quasiconformal mappings, ψ_{1}, ψ_{2} are complex polynomials of degree, say, l, and h_{1}(0) = 0 = h_{2}(0), h_{1}(∞) = ∞ = h_{2}(∞). Moreover, for each j, j = 1, 2,

(4.1)  \frac{1}{K} ≤ \frac{r_{j}(w)}{r_{j}(v)} ≤ K for all pairs of adjacent vertices v, w ∈ 𝕂^{(0)},

where r_{1} and r_{2} are the radius functions of P and Q, respectively. It follows from quasiconformal arguments (Theorem 2.4 of [L]) that there exists a constant c = c(K) depending only on K such that

\frac{max_{α} |h_{j}(δe^{iα})|}{min_{α} |h_{j}(δe^{iα})|} ≤ c for every δ > 0, j = 1, 2.

Since ψ_{j}’s are polynomials of degree l, there is R > 0 such that for each j, j = 1, 2,

(4.2)  \frac{max_{α} |f_{j}(δe^{iα})|}{min_{α} |f_{j}(δe^{iα})|} = \frac{max_{α} |h_{j}(δe^{iα})|}{min_{α} |h_{j}(δe^{iα})|} \frac{|1 + O(\frac{1}{δ})|}{|1 − O(\frac{1}{δ})|} ≤ 2c for all δ > R.

For each n > R let O_{n} denote the largest, simply connected portion of O contained in D(n), D(δ) := {|z| < δ}. Write 𝕂_{n} ⊂ 𝕂 for the complex of O_{n}. Let P_{n} and Q_{n} be portions of P and Q, respectively, associated with the complex 𝕂_{n}. By Theorem 2.2(ii) there exists a Bl-type packing B_{n} for 𝕂_{n} with branch set 𝔅, and normalized so that the circle C_{B_{n}}(v_{0}) is centered at 0. Define ρ_{j}(n) := max_{α} |f_{j}(ne^{iα})| for j = 1, 2. Write P̃_{n} := \frac{1}{ρ_{j}(n)}P_{n} and Q̃_{n} := \frac{1}{ρ_{j}(n)}Q_{n}.

Since P̃_{n}, Q̃_{n} ⊆ D(1) and packings B_{n}, P_{n}, and Q_{n} have identical branch sets, by discrete Schwarz Lemma of [BSt2] one has

(4.3)  \frac{1}{ρ_{j}(n)} = \frac{r_{j}(v_{0})}{ρ_{j}(n)} ≤ η_{n}(v_{0})  for all n, and j = 1, 2,

where η_{n} is the radius function of B_{n}.

From (4.2) we obtain that \frac{1}{ρ_{j}(n)}f_{j}(∂D(n)) ⊆ Ω := \{|z| ≥ \frac{1}{2c}\}. However, it is not

generally true that all boundary circles of P̃_{n} and Q̃_{n} (i.e., circles in P̃_{n} and Q̃_{n} corresponding to boundary vertices of 𝕂_{n}) intersect Ω. Nevertheless, we will now show that they are not far away from the set Ω. To be more precise, for v ∈ bd 𝕂_{n}^{(0)} we define

δ_{j}^{n}(v) = \{ \begin{matrix}0 & if \frac{1}{ρ_{j}(n)} (|f_{j}(v)| + r_{j}(v)) ≥ \frac{1}{2c} \\ \frac{1}{2c} − \frac{1}{ρ_{j}(n)} (|f_{j}(v)| + r_{j}(v)) & otherwise, \end{matrix}

which is the distance between the boundary circle CP̃_{n}(v) and Ω when j = 1 or between the boundary circle CQ̃_{n}(v) and Ω when j = 2 (Figure 4). We are only interested in vertices v ∈ bd 𝕂_{n}^{(0)} with δ_{j}^{n}(v) > 0; for if δ_{j}^{n}(v) = 0 then CP̃_{n}(v) ∩ Ω ≠ ∅ when j = 1 and CQ̃_{n}(v) ∩ Ω ≠ ∅ when j = 2.

Figure 4. δ_{j}^{n}(v) for j = 1.

It is immediate that

(4.4)  \frac{1}{ρ_{j}(n)}r_{j}(v) ≤ \frac{1}{2c} − δ_{j}^{n}(v)  for δ_{j}^{n}(v) > 0.

From the definitions of 𝕂_{n} and the cp-maps f_{j} it is easy to see that if v ∈ bd 𝕂_{n}^{(0)} and CP̃_{n}(v)∩Ω = ∅ (respectively, CQ̃_{n}(v)∩Ω = ∅) then there is at least one neighbor w ∈ 𝕂^{(0)} of v such that the circle in \frac{1}{ρ_{1}(n)}P (respectively, \frac{1}{ρ_{2}(n)}Q) corresponding to w intersects Ω. Therefore, it follows that

δ_{j}^{n}(v) ≤ \frac{2}{ρ_{j}(n)} max_{w∈𝕂^{(0)} w adjucent to v} r_{j}(w)  whenever δ_{j}^{n}(v) > 0, j = 1, 2.

Thus, by (4.1)

(4.5)  δ_{j}^{n}(v) ≤ \frac{2}{ρ_{j}(n)}Kr_{j}(v)  when δ_{j}^{n}(v) > 0.

Hence, (4.4) and (4.5) imply

(4.6)  δ_{j}^{n}(v) ≤ \frac{K}{c} (2K + 1)^{−1} ,

i.e. the boundary circles of P̃_{n} and Q̃_{n} that do not intersect Ω are “not far away” from Ω.

It follows from (4.6) that 2c(2K +1) ≥ (\frac{1}{2c} −δ_{j}^{n}(v))^{−1}. The last inequality implies that packings P̂_{n} := 2c(2K + 1)P̃_{n} and Q̂_{n} := 2c(2K + 1)Q̃_{n} have their boundary circles intersecting {|z| ≥ 1}, and therefore, in the language of [DSt], P̂_{n} and Q̂_{n} properly cover D(1). Hence, by Discrete Distortion Lemma of [DSt]

(4.7)  η_{n}(v_{0}) ≤ 2c(2K + 1)\frac{r_{j}(v_{0})}{ρ_{j}(n)}  for all n > R, and j = 1, 2.

Thus, (4.3) and (4.7) give

(4.8)  \frac{1}{2c(2K + 1)} \frac{r_{1}(v_{0})}{ρ_{1}(n)} ≤ \frac{r_{2}(v_{0})}{ρ_{2}(n)} ≤ 2c(2K + 1)\frac{r_{1}(v_{0})}{ρ_{1}(n)}  for all n > R.

We will now show that (4.8) can be extended to every vertex of 𝕂 with, perhaps, slightly larger but uniform constant instead of 2c(2K + 1). Denote by Õ_{n} a univalent Bl-type packing (i.e., with empty branch set) for 𝕂_{n} with the circle CÕ_{n}(v_{0}) centered at 0. Since 𝕂 is recurrent, it follows from the proof of Discrete Uniformization Theorem of [BSt1,§4] and Theorem 2.5 that for each v ∈ 𝕂^{(0)}, CÕ_{n}(v) converges to a point which is the origin as n → ∞. The monotonicity results of [BSt2, Theorem 4] imply that for each v ∈ 𝕂^{(0)}, C_{B_{n}}(v) converges to a point which is the origin as n → ∞.

Let ϵ > 0 be small. Fix w ∈ 𝕂^{(0)}, w ≠ v_{0}. From the above convergence results there exists R_{w} ≥ R such that

C_{B_{n}}(w) ⊂ D(ϵ), \frac{1}{ρ_{1}(n)}|f_{j}(w)| < ϵ, and \frac{1}{ρ_{1}(n)}|r_{j}(w)| < ϵ for all n ≥ R_{w}.

Let B_{n}(w) be a Bl-type packing for 𝕂_{n} with branch set 𝔅 and normalized so that its circle associated with w is centered at 0. We also define P̃_{n}(w) and Q̃_{n}(w) as packings that are obtained by translating packings (1 − ϵ)P̃_{n} and (1 − ϵ)Q̃_{n}, respectively, so that their circles corresponding to the vertex w are centered at 0. Thus, by discrete Schwarz Lemma of [BSt2],

(4.9)  (1 − ϵ)\frac{r_{j}(w)}{ρ_{j}(n)} ≤ η_{n}^{w}(w)  for all n ≥ R_{w}, and j = 1, 2,

where η_{n}^{w} is the radius function of B_{n}(w). It is clear from the definition of P̃_{n}(w) that the boundary circle of P̃_{n}(w) associated with a vertex v ∈ bd 𝕂_{n}^{(0)} is within the distance δ_{1}^{n}(v) + ϵ(\frac{1}{2c} − δ_{1}^{n}(v)) + ϵ from Ω for all n ≥ R_{w}. Similarly for boundary circles of Q̃_{n}(w). Thus it follows from (4.6) that P̂_{n}(w) := c(K, ϵ)P̃_{n}(w) and Q̂_{n}(w) := c(K, ϵ)Q̃_{n}(w) properly cover D(1), where c(K, ϵ) := \frac{2c(2K+1)}{1−ϵ−ϵ2c(2K+1)}. Hence, by Discrete Distortion Lemma of [DSt],

(4.10)  η_{n}^{w}(w) ≤ c(K, ϵ)(1 − ϵ)\frac{r_{j}(w)}{ρ_{j}(n)}  for all n ≥ R_{w}, and j = 1, 2.

Therefore, (4.9) and (4.10) give

(4.11)  \frac{1}{c(K, ϵ)} \frac{ρ_{2}(n)}{ρ_{1}(n)} ≤ \frac{r_{2}(w)}{r_{1}(w)} ≤ c(K, ϵ)\frac{ρ_{2}(n)}{ρ_{1}(n)}  for all n ≥ R_{w}.

Now (4.8) and (4.11) imply

\frac{1}{2c(2K + 1)c(K, ϵ)} \frac{r_{2}(v_{0})}{r_{1}(v_{0})} ≤ \frac{r_{2}(w)}{r_{1}(w)} ≤ 2c(2K + 1)c(K, ϵ)\frac{r_{2}(v_{0})}{r_{1}(v_{0})}.

Since w is arbitrary vertex of 𝕂, the last double inequality proves the assertion (*). □

From Theorem 2.5 and the above result we obtain

Corollary 4.3. Let U be a univalent, bounded degree circle packing with carr(U) = C. Denote by 𝕂 the complex of U_{.} Then the set of all finite valence circle packings for 𝕂 with finite branch sets is equal to the set of all range packings of discrete complex polynomials for 𝕂. Moreover, each such a packing is determined uniquely, up to similarities of C, by its branch set.

Concluding Remarks. (1) We conjecture that Theorem 4.2 should also be true for triangulations with recurrent 1-skeletons but not necessarily of bounded degree.

(2) For complete analogy with the univalent setting, one should be able to show the uniqueness result, similar to Corollary 4.3, for branched circle packings whose corresponding univalent packings cover C but underlying complexes are not of bounded degree. As it was shown in [HSc], such complexes might have 1-skeletons which are not recurrent even though univalent packings associated with them have carriers equal to C.

References

[BaFP] I. Bárány, Z. Füredi, and J. Pach, Discrete convex functions and proof of the six circle conjecture of Fejes Tóth, Can. J. Math 36 (1984), 569–576.

[BSt1] A. F. Beardon and K. Stephenson, The uniformization theorem for circle packings, Indiana Univ. Math. J. 39 (1990), 1383–1425.

[BSt2] , The Schwarz-Pick lemma for circle packings, Ill. J. Math. 141 (1991), 577–606.

[BeSc] I. Benjamini and O. Schramm, Harmonic functions on planar and almost planar graphs and manifolds, via circle packings, preprint.

[Bo] P. L. Bowers, The upper Perron method for labeled complexes, Proc. Camb. Phil. Soc. 114 (1992), 321–345.

[CdV] Y. Colin de Verdière, Un principe variationnel pour les empilements de cercles, Invent. Math. 104 (1991), 655–669.

[D1] T. Dubejko, Branched circle packings and discrete Blaschke products, Trans. Amer. Math. Soc. (to appear).

[D2] , Infinite branched circle packings and discrete complex polynomials, preprint.

[D3] , Approximation of analytic functions with prescribed boundary conditions by circle packing maps, Math Sci Res Inst preprint #020-95.

[D4] , Circle packings of hyperbolic type, preprint.

[DSt] T. Dubejko and K. Stephenson, The branched Schwarz lemma: a classical result via circle packing, Mich. Math. Jour. (to appear).

[G] B. Garrett, Circle packings and polyhedral surfaces, Discrete & Comput. Geom. 8 (1992), 429-440.

[H] Z.-X. He, An estimate for hexagonal circle packings, J. Differential Geom. 33 (1991), 395–412.

[HSc] Z.-X. He and O. Schramm, Hyperbolic and parabolic packings, preprint.

[L] O. Lehto, Univalent functions and Teichüller Spaces, Springer-Verlag, 1987.

[Mc] G. McCaughan, A recurrence/transience result for circle packings, preprint.

[RS] B. Rodin and D. Sullivan, The convergence of circle packings to the Riemann mapping, J. Differential Geom. 26 (1987), 349–360.

[Sc] O. Schramm, Rigidity of infinite (circle) packings, J. Amer. Math. Soc. 4 (1991), 127-149.

[So] P. M. Soardi, Potential theory on infinite networks, Lecture notes in mathematics, vol. 1590, Springer-Verlag, 1994.

[St1] K. Stephenson, Circle packings in the approximation of conformal mappings, Bull. Amer. Math. Soc. (Research Announcements) 23, no. 2 (1990), 407–415.

[St2] , A probabilistic proof of Thurston’s conjecture on circle packings, preprint.

[St3] , Circle packings: existence and uniqueness, REU’94 Notes.

[T1] W. P. Thurston, The finite Riemann mapping theorem, Invited talk, An International Symposium at Purdue University on the occasion of the proof of the Bieberbach conjecture, March 1985.

[T2] , The Geometry and Topology of 3-Manifolds, Princeton University Notes, Princeton University Press, 1980.

RANDOM WALKS, LIOUVILLE’S THEOREM, AND CIRCLE PACKINGS 17

[W] W. Woess, Random walks on infinite graphs and groups – a survey on selected topics, Bull. London Math. Soc. 26 (1994), 1–60.

Mathematical Sciences Research Institute, Berkeley, CA 94720, U.S.A. E-mail address: tdubejko@msri.org