ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 14 (2018) 285-318 https://doi.org/10.26493/1855-3974.862.bb5 (Also available at http://amc-journal.eu) Growth of face-homogeneous tessellations Stephen J. Graves * The University of Texas at Tyler, Tyler, TX, USA Mark E. Watkins f Syracuse University, Syracuse, NY, USA Received 2 June 2015, accepted 23 July 2017, published online 13 September 2017 A tessellation of the plane is face-homogeneous if for some integer k > 3 there exists a cyclic sequence a = [po,Pi,... ,pk-1] of integers > 3 such that, for every face f of the tessellation, the valences of the vertices incident with f are given by the terms of a in either clockwise or counter-clockwise order. When a given cyclic sequence a is realizable in this way, it may determine a unique tessellation (up to isomorphism), in which case a is called monomorphic, or it may be the valence sequence of two or more non-isomorphic tessellations (polymorphic). A tessellation whose faces are uniformly bounded in the hyperbolic plane but not uniformly bounded in the Euclidean plane is called a hyperbolic tessellation. Such tessellations are well-known to have exponential growth. We seek the face-homogeneous hyperbolic tessellation(s) of slowest growth rate and show that the least growth rate of such monomorphic tessellations is the "golden mean," 7 = (1 + %/5)/2, attained by the sequences [4, 6,14] and [3,4,7,4]. A polymorphic sequence may yield non-isomorphic tessellations with different growth rates. However, all such tessellations found thus far grow at rates greater than 7. Keywords: Face-homogeneous, tessellation, growth rate, valence sequence, exponential growth, transition matrix, Bilinski diagram, hyperbolic plane. Math. Subj. Class.: 05B45, 05C63, 05C10, 05C12 *Much of the material in this work comes from the doctoral dissertation [4] of the first author written under the supervision of the second author. ÎThe second author was partially supported by a grant from the Simons Foundation (#209803 to Mark E. Watkins). E-mail addresses: sgraves@uttyler.edu (Stephen J. Graves), mewatkin@syr.edu (MarkE. Watkins) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ Abstract 286 Ars Math. Contemp. 14 (2018) 267-284 1 Introduction It has long been known that there are finitely many homogeneous tessellations of the Euclidean plane; they all have quadratic growth rate. However, in the hyperbolic plane, for various definitions of "homogeneity," infinitely many homogeneous tessellations are realizable, and their growth rate, if not quadratic, is always exponential. Presently we will give a rigorous definition of growth rate, but for now one should think of this parameter intuitively as the asymptotic rate at which additional tiles (or faces) accrue with respect to some chosen center of a tessellation. In this schema, all Euclidean tessellations have growth rate equal to 1, and hyperbolic tessellations have growth rate strictly greater than 1. The first author has shown by construction in [5] that, given any e > 0, there exists a hyperbolic tessellation with growth rate exactly 1 + e. In general, these latter tessellations have few if any combinatorial or geometric symmetries. The question then becomes one of determining the growth rates of hyperbolic tessellations when some sort of homogeneity is imposed. In particular, subject to a homogeneity constraint, how small can the gap be between quadratic and exponential growth? In a seminal work [8], Griinbaum and Shephard defined a graph to be edge-homogeneous with edge-symbol (p, q; k, £) if every edge is incident with vertices of valences p and q and faces of covalences k and I. They proved that the parameters of an edge-symbol uniquely determine an edge-homogeneous tessellation up to isomorphism. The notion of homogeneity was extended by Moran [10]. She defined a tessellation to be face-homogeneous with valence sequence [p0,..., pk-1] if every face is a k-gon incident with vertices of valences p0,... ,pk-1 in either clockwise or counter-clockwise consecutive order. Unfortunately, no uniqueness property analogous to the Grunbaum-Shephard result holds in general for face-homogeneous tessellations. Moran's work on growth rates of face-homogeneous tessellations led the authors (together with T. Pisanski) to return to edge-homogeneous tessellations and conclusively determine their growth rates. In [6] they determined the growth rate of any edge-homogeneous tessellation as a function of its edge-symbol and proved that the least growth rate for an exponentially-growing, edge-homogeneous tessellation is 2 (3 + \/5) « 2.618. The goal of this article is to obtain an analogous result for face-homogeneous tessellations. Our main result is that if a face-homogeneous tessellation with exponential growth rate is determined up to isomorphism by its valence sequence, then its growth rate is at least 2 (1 + %/5), namely the "golden mean." Moreover, we determine exactly the valence sequences for which this golden mean is realized. A significant by-product of our investigation is an abundance of machinery for computing the growth rates of many classes of face-homogeneous planar tessellations. Section 2 consists of six subsections. Following some general definitions concerning infinite graphs in the plane, we present (Subsection 2.2) a system for labeling sets of vertices and sets of faces of a tessellation; such a labeling is called a "Bilinski diagram." Subsection 2.3 presents the notion of face-homogeneity and associated notation. Polynomial and exponential growth, defined on the one hand with respect to the standard graph-theoretic metric, and on the other hand with respect to the notion of angle excess, appear in Subsection 2.4. Subsection 2.5 presents a rigorous theoretical treatment of growth rate with respect to regional distance in a Bilinski diagram. Subsection 2.6 concludes the Preliminaries with a review of the completely resolved case of edge-homogeneous tessellations, summarizing results from [8] and [6]. In Subsection 3.1 we lay out our method for filling in the formulas obtained in Sub- S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 287 section 2.5 while introducing the notion of a transition matrix. Analogous to a Markov process, this matrix encodes for given n > 1 how many faces of each possible configuration are "begotten" at regional distance n +1 from the root of a Bilinski diagram by a face at regional distance n from the root. The maximum modulus of the eigenvalues of the transition matrix are key to the growth rate of T. Subsection 3.2 applies the machinery of Subsection 3.1 to the significant class of valence sequences that are monomorphic, i.e., that are uniquely realizable as a face-homogeneous tessellation and whose Bilinski diagrams are in a certain sense well-behaved, called uniformly concentric. It is shown in Theorem 3.7 that for such valence sequences, the partial order defined in Subsection 2.3 is preserved by their growth rates. The six classes of monomorphic sequences of lengths 3, 4, and 5 whose Bilinski diagrams are not uniformly concentric are identified in Subsection 3.3, where it is proved that they are indeed monomorphic. The exhaustive proof that this list is complete is contained in the Appendix [7]. Finally, we present in Subsection 3.4 the main result of the paper, that the least growth rate of a face-homogeneous tessellation with monomorphic valence sequence is the golden mean 2 (1 + V5). Those valence sequences (described as polymorphic) which admit multiple non-isomor-phic tessellations are alive and well in Subsection 4.1. A general sufficient condition for polymorphism is given. The difficulties posed by polymorphism are illustrated by an example; the polymorphic sequence [4,4,6,8] is considered in some depth in Subsection 4.2. In particular, we see by this example that two different tessellations having the same (polymorphic) valence sequence may well have different growth rates. We conclude the chapter with some conjectures in Subsection 4.3. The appendix [7] alluded to above is to be found with this article on the arXiv, at arXiv:1707.03443. All references therein are to results in the present paper. Due to the considerable length (and tedium!) of the appendix, it will not appear in Ars Mathemat-ica Contemporanea with this article. 2 Preliminaries 2.1 Tessellations For a graph r, the symbol V(r) denotes the vertex set of r. If M is a planar embedding of r, we call M a plane map and denote by F (M) the set of faces of M. A graph r is infinite if its vertex set V (r) is infinite; r is locally finite if every vertex has finite valence. A graph is 3-connected if there is no set of fewer than three vertices whose removal disconnects the graph. It is well known that if the underlying graph r of a plane map M is 3-connected (as is generally the case in this work), then every automorphism of r induces a permutation of F (M) that preserves face-vertex incidence and can be extended to a homeomorphism of the plane. Thus we tend to abuse language and speak of "the faces of r." When a plane map is 3-connected, every edge is incident with exactly two distinct faces. In this case, the number of edges (and hence of vertices) incident with a given face is its covalence. A map is locally cofinite if the covalence of every face is finite. An accumulation point of an infinite plane map M is a point x in the plane such that every open disk of positive radius (in either the Euclidean or hyperbolic metric) containing x intersects infinitely many map objects, be they faces, edges, or vertices. A map is 1-ended when the deletion of any finite submap leaves exactly one infinite component. Definition 2.1. A tessellation is an infinite plane map that is 3-connected, locally finite, 288 Ars Math. Contemp. 14 (2018) 267-284 locally cofinite, 1-ended, and also admits no accumulation point. In the terminology of Griinbaum and Shepherd's exhaustive work [9] on tilings of the plane, a tessellation T is normal if there is an embedding of T in the plane and radii 0 < r < R under a specific metric such that the boundary of each face lies within some annulus with inner radius r and outer radius R. A Euclidean tessellation is a tessellation that is normal with respect to the Euclidean metric, and a hyperbolic tessellation is one that is normal with respect to the hyperbolic metric but not with respect the Euclidean metric. 2.2 Bilinski diagrams A very useful tool for computing "growth rate" is what we have called a Bilinski diagram, because these diagrams were first used by Stanko Bilinski in his dissertation [1, 2]. Definition 2.2. Let M be a map that is rooted at some vertex x. Define a sequence of sets {Un : n > 0} of vertices and a sequence of sets {Fn : n > 0} of faces of M inductively as follows. • Let U0 = {x} and let F0 = 0. • For n > 1, let Fn denote the set of faces of M not in Fn-1 that are incident with some vertex in Un-1. • For n > 1, let Un denote the set of vertices of M not in Un-1 that are incident with some face in Fn. The stratification of M determined by the set-sequences {Un} and {Fn} is called the Bilinski diagram of M rooted at x. In a similar way one can define a Bilinski diagram of M rooted at a face f. In this case U0 = 0 and F0 = {f}. Given a Bilinski diagram of T, the induced submap (Fn) of T is its nth corona. A Bilinski diagram is concentric if each subgraph (Un) induced by Un (n > 1) is a cycle; otherwise the Bilinski diagram is non-concentric. If a plane map yields a concentric Bilinski diagram regardless of which vertex or face is designated as its root, then the map is uniformly concentric; analogously a map which for every designated root yields a non-concentric Bilinski diagram is uniformly non-concentric. To answer the question as to which tessellations are uniformly concentric we state a sufficient condition and a necessary condition. Let Ga,b denote the class of tessellations all of whose vertices have valence at least a and all of whose faces have covalence at least b. Let Ga+bh be the subclass of Ga,b of tessellations with no adjacent a-valent vertices. Proposition 2.3 ([3, Corollary 4.2], [11, Theorem 3.2]). Every tessellation T e G^e U G3+j5 U G4,4 is uniformly concentric, and in every Bilinski diagram of T, for all n > 1, every face in Fn is incident with at most two edges in (Un-1). Proposition 2.4 ([3, Theorem 5.1]). If an infinite planar map admits any of the following configurations, then the map is not uniformly concentric: 1. a 3-valent vertex incident with a 3-covalent face; 2. a 4-valent vertex incident with two nonadjacent 3-covalent faces; 3. a 4-covalent face incident with two nonadjacent 3-valent vertices; 4. an edge incident with two 3-valent vertices and two 4-covalent faces; 5. an edge incident with two 4-valent vertices and two 3-covalent faces. S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 289 2.3 Face-homogeneity and readability Let k > 3 be an integer and let an equivalence relation be defined on the set of ordered k-tuples (po,Pi,... ,pk-i) of positive integers whereby • (po,pi,... ,Pk-i) = (pi,p2,... ,Pk-i,po), and • (po,Pi, . . . ,Pfc-i) = (Pfc-i,Pfc-2, ... ,po). The equivalence class of which (po,... ,pk-i) is a member is the cyclic sequence [po,... ,pk-i], and k is its length. There is a natural partial order < on the set of cyclic sequences: [po,... ,Pk-i] < [qo,... if and only if k < I and there exists a cyclic subsequence qio, q¿1,..., qik-1 occurring in either order in [qo, qi,..., qi-i] such that pj < qij for each j e {0,..., k - 1}. We write ai < a2 if ai < a2 but ai = a2, where ai and a2 are cyclic sequences. Example 2.5. Let ai = [4,6, 8,10], a2 = [6, 8,12,4], and a3 = [10,8,12,6,4]. Then ai < a2 and ai < a3, but a2 and a3 are not comparable. Definition 2.6. Let a = [po,pi,... ,pk-i] be a cyclic sequence of integers > 3. Then a is the valence sequence of a k-covalent face f of a tessellation T if the valences of vertices incident with f in clockwise or counter-clockwise order arepo,pi,... ,pk-i. If every face of T has the same valence sequence a, then T is face-homogeneous and a is the valence sequence of T. Thus, to say briefly that a tessellation T has valence sequence a implies that T is face-homogeneous. Definition 2.7. Let the cyclic sequnce a be realizable as the valence sequence of a tessellation. If every tessellation having valence sequence a is uniformly concentric, then we say that a is uniformly concentric. Otherwise a is non-concentric. If every tessellation having valence sequence a is non-concentric, then a is uniformly non-concentric. Notation. By convention, when distinct letters are used to represent terms in a cyclic sequence (e.g. [p,p, q, r, q]), the values corresponding to distinct letters are all presumed to be distinct; that is, p = q = r = p. Moreover, if some term in the cyclic sequence is given as an integer (usually 3 or 4), then the terms given by letters are presumed to be greater than that integer. For example, if a = [4, p, q], then we understand that p, q > 4 and p = q. When using subscripts in the general form [po,..., pk-i], we do not make this assumption. Remark 2.8. Not all cyclic sequences are realizable as vertex sequences of face-homogeneous tessellations of the plane. For instance, the map with valence sequence [3, 3, 3] (the tetrahedron) is a tessellation of the sphere but not of the plane. More importantly, there are many cyclic sequences for which no face-homogeneous map exists at all. For instance, the valence sequence [4,5, 6,p] for any p > 3 is not realizable, because in any such map the valences of the neighbors of a 5-valent vertex in cyclic order would have to alternate between 4 and 6. However, this does not generalize to all cyclic sequences containing a subsequence [p, q, r] where q is odd and p = r; for instance, [5,4, 5,6,5, 8] is realizable. Conjecture 2.9. Suppose a is the valence sequence of a face-homogeneous tessellation and that a contains [p, q, r] as a subsequence, with q odd and p = r. Then a must contain at least three terms equal to q. 290 Ars Math. Contemp. 14 (2018) 267-284 2.4 Polynomial versus exponential growth Let x be a vertex of a connected graph r. For each nonnegative integer n, the ball of radius n about x is the set of vertices of r at distance < n from x, written Bn(x) = {v e V(r) : d(x, v) < n}, (2.1) where d(—, —) is the standard graph-theoretic metric, that is, d(u, v) is the length of a shortest path with terminal vertices u and v. Definition 2.10. An infinite, locally finite, connected graph r has exponential growth if for some vertex x e V(r) there exist real numbers a > 1 and C > 0 such that, for all n > 0, one has |Bn(x)| > Can; otherwise r has subexponential growth. We say that r has polynomial growth of degree d e N if there exist positive constants C1 and C2 such that Cind < |Bn(x) | < C2nd for all but finitely many n. For example, the graph underlying the square lattice in the plane has quadratic growth (d = 2). If x is any vertex, then |Bn(x) | = 2n2 + 2n + 1 for all n > 1, and one can set Ci = 2 and C2 = 3. Continuing the notation of Equation (2.1) and Definition 2.10, we consider the generating function to &(z) = ^ |B„(x)| zn (2.2) n=0 We denote the radius of convergence of by RB and define the ball-growth rate of V about x to be the reciprocal of RB. If r has exponential growth, then we have TO c & (z) >Y\ Canzn = --, (2.3) 1 — az n=0 where a > 1 is the supremum of values for which the series of Equation (2.2) converges. The convergence is absolute if and only if |z| < 1/a < 1. If r has polynomial growth of degree d, then TO TO TO Ci ^ ndzn < ^ |Bn(x)| zn < C2 ^ ndzn. Jn V 0 By the "ratio test," the first and third series converge if and only if |z| < 1. These computations yield the following. Proposition 2.11. Let RB denote the radius of convergence of the generating function of Equation (2.2). Then RB < 1 if and only if r has exponential growth, and RB = 1 if and only if r has polynomial growth. Moreover, RB is independent of the vertex x about which |Bn(x) | is determined. It will be seen in the next subsection (see Theorem 2.16) that the value of RB is independent of the choice of the root vertex x. It is well known (for example, see [9]) that there exist exactly eleven face-homogeneous Euclidean tessellations, namely the Laves nets. Their valence sequences [p0,... ,pk_1] S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 291 correspond to integer solutions of the equation k-1 _ k - 2 ^pi = 2 ' i=0 ^ : A necessary condition for the existence of a face-homogeneous hyperbolic tessellation with valence sequence [p0,... ,pk-1] is that the inequality k-1 1 k - 2 ^ pi < — (2.4) i=o P: 2 hold. This condition is not sufficient, because as we have seen, not every such integer solution of the inequality (2.4) is realizable as a valence sequence. Definition 2.12. The angle excess of a cyclic sequence a = [p0,... ,pk-1] is given by (s ^)- 2' Motivation for this definition comes from Descartes' notion of angular defect in the Euclidean plane. When n(a) > 0, there are too many faces incident at a vertex for the faces to be regular k-gons in the Euclidean plane. Proposition 2.13. For a cyclic sequence a = [p0,... ,pk-1], inequality (2.4) is equivalent to n(a) > 0 (2.5) and is a necessary condition for a to be a valence sequence of a face-homogeneous hyperbolic tessellation. Angle excess provides a quick gauge of the growth behavior of a tessellation with valence sequence a. If n(a) < 0, the tessellation is finite. If n(a) = 0, the tessellation is one of the Laves nets and has polynomial growth of degree 2. If n(a) > 0, the tessellation has exponential growth. Additionally, we have the following comparison result. Proposition 2.14. Let a1 and a2 be cyclic sequences that are comparable in the partial order Then a1 < a2 if and only if n(a1) < n(a2). Proof. Suppose that a1 < a2, where a1 = [p0,... ,pk-1] and a2 = [q0,.qe-1]. By definition there exist qio,..., qik_1 with pj < q:. for all j = 0,.. .k - 1. So k 1 ¿-v k 1 c\ & 1 n(a1) = s — < S — < S — = n(«2). (2.6) j=0 pj j=0 q:j :=0 q: If k = I, then pj < q:j for some j and the first inequality in (2.6) is strict. If k < I, the second inequality in (2.6) is strict. Since a1 = a2, at least one such strict inequality must hold. □ 292 Ars Math. Contemp. 14 (2018) 267-284 2.5 Growth formulas In Definition 2.10, the standard graph-theoretical metric was used to define polynomial and exponential growth of a connected graph. However, to measure growth rates of tessellations, it is more convenient to use the notion of "regional distance;" we will count the number of graph objects in the nth corona of a Bilinski diagram centered at a given vertex, and our working definition of "growth rate" will be the following. Definition 2.15. Let T be a tessellation labeled as a Bilinski diagram rooted at a vertex x. Let R be the radius of convergence of the power series w 3. Hence for any n > 1 and any vertex v G Un+i(x) there exists a vertex u g Un such that d(u, v) < |_fj. By induction on n, we obtain d(x, v) < (n + 1) |_U, yielding n U Ui (x) C BnLfc/2j(x) (2.8) i=0 and similarly, n Bn(x) C U Ui(x). (2.9) i=0 In addition to the power series yx(z) of Definition 2.15 with radius of convergence RF, we require the power series ux(z) = ^ |Un(x)| zn with radius of convergence Ru. Writing / ^ w I n \ w Yx(z) = = £ E |Ui(x)| zn = ]T U Ui(x) we have that the radius of convergence of Tx(z) equals min {Ru, 1} < RB by Equation (2.8) (where RB is as in Proposition 2.11). But similarly by Equation (2.9) we have that Rb < min {Ru, 1}. Hence the radii of convergence of Tx(z) and ^x(z) are equal, for any choice of root vertex x. zn S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 293 If p is the maximum valence of the vertices in T, each vertex is also incident with at most p faces, while each face is incident with k vertices, giving |Un(x)| < k |Fn+i(x)| < pk |Un+i(x)| for each n > 0, or equivalently, 1 |Un (x)| < |F„+i(x)| < p |U„+i(x)| . Hence the radii of convergence of ux (z) and px (z) are equal, and more importantly, RF = Rb ; that is, the rate of ball-growth equals the rate of growth when the Bilinski diagram is labeled from a vertex x. Finally, it follows from Proposition 2.11 that ball-growth rates computed about distinct vertices are asymptotically equal in locally finite, connected, infinite graphs. Hence the radii of convergence of px(z), Px(z), Py (z), and py (z) are equal for all x, y G V. That is to say, the growth rate of the graph is independent of the choice of root vertex. □ Notation. The subscript on the symbol p of Definition 2.15 has now been shown to be superfluous and will henceforth be suppressed. Consider the function t : N0 ^ N0, (where N0 = {0,1,2,...}) given by t(n) = ^ |Fi|. \ - i=i The quantity lim (2.10) u^to T (n) was the definition of the growth rate of a face-homogeneous tessellation used by Moran [10] provided that this limit exists, in which case she called the tessellation balanced. Moran's limit fails to converge only when there exist subsequences of the sequence j ^Tu+y } with distinct limits. The following proposition shows that the parameters of a face-homogeneous tessellation determine an upper bound for the limit in Equation (2.10). Theorem 2.17. Let T be a face-homogeneous tessellation with valence sequence [p0,... ,pk-i], labeled as a Bilinski diagram. Then t (n +1) k— lim sup-——— < 1 + > pi — 2k < to . u^to T (n) ^ i=0 Proof. By hypothesis, each face of the tessellation shares an incident vertex with exactly k-i k-i Yjp>i — 2) = ^ pi — 2k i=0 i=0 other faces. So for n > 0, |Fn+i| < |Fn| ^pi — 2k^ , 294 Ars Math. Contemp. 14 (2018) 267-284 which in turn gives that for all n > 0, liiiil < 1+ lEnL (£ p, - 2k) t w E,.O vso ) k-i < 1 + P, - 2k < ro, ,=0 since T is locally finite. □ By the "ratio test" of elementary calculus, the above proof implies that in the case of a "balanced" tessellation, Moran's definition of growth rate concurs with Definition 2.15, and 1 t (n +1) t (n +1) — = iim sup-——— = iim -———. R n^TO T (n) n^TO t (n) The definition of growth rate in terms of the radius of convergence of a power series also allows us to prove the following result, which is essential in many comparisons of growth rates of various tessellations. Lemma 2.18 (Comparison Lemma). Let T1 and T2 be tessellations, and for i =1, 2 let \F,,n\ be the number of faces in the nth corona of a Bilinski diagram of T,. Suppose that for some N e N, we have \Fi,n\ < \F2,n\for all n > N. Then y(ti) < 7^2). Proof. Let TO TO ¿1 (z) = £ \Fi,n\zn, ¿2 (z) = £ \F2,n\zn, n=0 n=0 and for i e {1, 2}, let R, be the radius of convergence of ¿,(z) about 0. Then since |,n| < \F2,n\ for sufficiently large n, and limsup = R^= Y(Ti), n^TO Ri we have 7(Ti) < 7^2). □ 2.6 The edge-homogeneous case We conclude our presentation of preliminary material with a quick review of what is known about growth rates of edge-homogeneous tessellations, as this case has been completely resolved and its consequences turn out to be useful here and there in attacking the present problem. The point of departure here is the following classification theorem of Griinbaum and Shephard. (Edge-symbols were defined in Section 1.) Proposition 2.19 ([8, Theorem 1]). Let p,q,k,£ > 3 be integers. There exists an edge-homogeneous, 3-connected, finite or 1-ended map with edge-symbol (p, q; k, t) if and only if exactly one of the following holds: 1. all ofp, q, k, t are even; 2. k = t is even and at least one ofp, q is odd; 3. p = q is even and at least one of k, t is odd; S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 295 4. p = q, k = £, and all are odd. Such a tessellation is edge-transitive, and the parameters p, q, k, £ determine the tessellation uniquely up to homeomorphism of the plane. If p = q, then the tessellation is vertex-transitive. If k = £, then it is face-transitive. Following up on the Griinbaum-Shephard result, the authors together with T. Pisanski completely determined the growth rates of all edge-homogeneous tessellations. Their main result is the following. Proposition 2.20 ([6, Theorem 4.1]). Let the function g : {t e N : t > 4} ^ [1, œ) be given by 1 2 Let T be an edge-homogeneous tessellation with edge-symbol (p, q; k, t), and let g(t)=2 (t - 2+ V(t - 2)2 - ^ . (2.11) t =(P+q - A - 2) (2.12) Then exactly one of the following holds: 1. the growth rate of T is y(T) = g(t); or 2. the edge-symbol of T or its planar dual is (3, p; 4,4) with p > 6, and the growth rate of T is y(T) = g(t - 1). Observe that each value of t > 4 corresponds to only finitely many edge-homogeneous tessellations and that pairs of planar duals correspond to the same value of t. As the growth rates of edge-homogeneous tessellations are determined by an increasing function in one variable, the following is immediate. Corollary 2.21. The least growth rate of an edge-homogeneous hyperbolic tessellation is (3 + a/5)/2. This value is attained only by the tessellations with edge-symbols (3,3; 7, 7), (4,4; 4, 5), (3, 7; 4,4), and their planar duals. Remark 2.22. It is evident from Proposition 2.19 that if a tessellation is both edge- and face-homogeneous, then its edge-symbol and valence sequence have, respectively, either the forms (p, p; k, k) and [p, p,..., p] or the forms (p, q; k, k) and [p, q,..., p, q], the latter pair being possible only when k is even. We mention that, by an argument similar to the proof of Theorem 2.17, one easily obtains the following upper bound for the growth rate of an edge-homogeneous tessellation. Proposition 2.23. Let T be an edge-homogeneous tessellation with edge-symbol (p, q; k, t). Then for any labeling ofT as a Bilinski diagram, one has t (n +1) lim -——— < 1 + max{pk, qk,pt, qt}. n^TO T (n) 296 Ars Math. Contemp. 14 (2018) 267-284 3 Accretion and monomorphic valence sequences 3.1 Accretion Given an arbitrary face-homogeneous tessellation T with valence sequence a = [p0,pi,... ,pk-1], we wish to apply Definition 2.15 to determine its growth rate. Letting T be labeled as a Bilinski diagram, we require a means to evaluate | Fn | for all n g N. This is done inductively; each face f g Fn "begets" a certain number of facial "offspring" in Fn+1, and that number is determined by the configuration of f within (Fn), that is, what the valences are of the vertices incident with f (in the rotational order of a) that belong, respectively, to Un-1 and more importantly to Un. A class of identically configured faces (in any corona) is a face type, and is denoted by f for some range of i = 1,..., r. The benefit of using face types is that we can define an r-dimensional column vector vn, called the nth distribution vector, which lists the frequency with which each face type occurs in the nth corona. Thus, if j is the r-dimensional vector of Is, then |Fn| = j vn via the standard dot product. Figure 1 depicts a face f g Fn of some tessellation and the faces in Fn+1 which are determined by the face type of f. These faces are called the offspring of f, and the figure is accordingly called the offspring diagram for f. As the vertex labeled pj is incident with Un U n+1 f' Pj^ f -—*-""""-—1 -—*-""""-—1 f" A B Figure 1: A face f in Fn of a tessellation T, along with the offspring of f in Fn+1. both faces f and f' g Fn, one-half of those faces in Fn+1 labeled as A in the figure count as offspring of f, and one-half are counted as offspring of f'. Similarly, half of the faces labeled by B count as offspring of f and half as offspring of f". All those faces between labels A and B in Figure 1 are wholly offspring of f. Those faces which are offspring of f, or offspring of offspring of f, and so on, are called collectively descendants of f. Definition 3.1. With respect to the labeling of a Bilinski diagram, each vertex incident with a face f g Fn lies in Un-1 or Un. The pattern of valences of vertices in Un-1 and in Un determines the face type of f. The three face types occurring most routinely are called wedges, bricks, and notched bricks. A face f in Fn is a wedge if it is incident with exactly one vertex in Un-1. The face f is a brick if it incident with exactly two adjacent vertices in Un-1 and at least two vertices in Un. Finally, f is a notched brick if it is incident with three consecutive vertices of Un-1, of which the middle vertex is 3-valent, and f is incident with S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 297 two or more vertices in Un. For a given labeling of a tessellation T as a Bilinski diagram, the face types of T are indexed i\,..., fr for some r e N; we explain the method by which indices are assigned after the statement of Theorem 3.7. An algorithm by which one can describe the faces, corona by corona, of a tessellation labeled as a Bilinski diagram is called an accretion rule. Often some homogeneous system of recurrence relations determines such an accretion rule. In this case, the nth distribution vector vn defined above has the property that the j,th component of vn is the number of faces of type fj in the nth corona. We then encode the system of recurrences into a transition matrix M such that vn+1 = Mvn holds for all n > 1. When M = [m^-] is such a matrix, the entry m^- is the number of faces of type f that are offspring of a face of type fj. We require the following result from [6]. Proposition 3.2 ([6, Theorem 3.1]). Let T be a tessellation labeled as a Bilinski diagram with accretion rule specified by the transition matrix M and first distribution vector v1. Then the ordinary generating function for the sequence j|Fn|}^=1 is ^(z) = |Fo| + z(p ■ (I - zM)-1vi) , (3.1) where I is the identity matrix and j is the vector of 1s. By using Definition 2.15, we can prove the following more directly than we did in Theorem 3.4 of [6]. Theorem 3.3. If M is the transition matrix of a tessellation T and A is the maximum modulus of an eigenvalue of M, then y (T) = A. Proof. We can write the generating function y>(z) of Proposition 3.2 as a rational function u(z)/v(z), with v(z) determined entirely by (I - zM)-1. Specifically, using Cramer's rule where r denotes the order of M, we have (I - zM)-1 = ,Tl—— adj(I - zM) v y det(I - zM) JV y 1 wvadj(I - zM) (3.2) (-z)r det(M - 11) 1z adj(I - zM) (-z)r X( 1) where x( 1) is the characteristic polynomial (in 1) of M. Entries of the adjoint adj(I-zM) are polynomials in z of degree at most r - 1, and so v(z) = (-z)rx( 1). As x( 1) is a polynomial in 1 of degree exactly r, v(z) has a nonzero constant term and the roots of v occur precisely at the roots of x( 1). These are precisely the reciprocals of the eigenvalues of M. Thus the minimum modulus of a pole of <^(z) is 1/A. As this is the definition of the radius of convergence of a power series expanded about 0, we have y(T) = A. □ 3.2 Monomorphic, uniformly concentric sequences As we have already remarked, valence sequences of face-homogeneous tessellations are unlike edge-symbols of edge-homogeneous tessellations in two significant ways: (i) the 298 Ars Math. Contemp. 14 (2018) 267-284 requirements for realizability of an edge-symbol are simpler and less stringent than the realizability criteria for a cyclic sequence, and (ii) two or more non-isomorphic face-homogeneous tessellations may share a common valence sequence. This latter property motivates the following definition. Definition 3.4. Let a be a cyclic sequence. If there exists (up to isomorphism) a unique face-homogeneous tessellation with valence sequence a, then we say that a is monomor-phic. If there exist at least two (non-isomorphic) tessellations with valence sequence a, then a is polymorphic. Proposition 3.5 (Moran [10]). All realizable cyclic sequences of length 3 are monomor-phic. A second property of interest is whether a given valence sequence is uniformly concentric. These two properties thus yield four classes of valence sequences. Not surprisingly, the class most amenable to an elegant and simple accretion rule consists of those that are both monomorphic and uniformly concentric. One can find in [13] a complete classification of cyclic sequences of length k for 3 < k < 5 in terms of Definition 3.4 which will help us to narrow our investigation. (It is actually the equivalent dual problem that is treated in [13], and the term "covalence sequence" is used. In the present work we have opted to follow Moran [10], speaking rather in terms of "valence sequences.") We now turn to considering the relative growth rates of tessellations with monomor-phic valence sequences. The ideal condition would be to have that the partial order on cycic sequences is mirrored by the natural order on growth rates: that is, if Ti and T2 are tessellations with valence sequences ai < a2, then y(T1) < y(T2). For monomorphic, uniformly concentric valence sequences, this is precisely the case, as stated below in Theorem 3.7. In order to prove the theorem, we now demonstrate the necessary machinery via the following example, which can be readily generalized. Example 3.6. Consider Ti and T2 to be face-homogeneous tessellations with monomorphic valence sequences ai = [4, 5,4,5] and a2 = [4,6,6,4, 5], respectively, both labeled as face-rooted Bilinski diagrams. Note that ai < a2. We continue the convention that Fi,n denotes the set of faces of the nth corona of Ti for i = 1,2. (The reader may follow Figures 2 through 7.) Starting with Ti, we construct by induction a sequence {Tj : j e N} of tessellations such that: 1. Tq = Ti as a base for the induction, 2. if we denote by Fj,n the set of faces in the nth corona of Tj, then for each j e N, the unions of the first n coronas of Tj satisfy (U ^ ^ (U ^ as induced subgraphs, and 3. |Fi,n| < |Fj n| for all n e N. To construct Ti from Tq , the valence sequence of the root face of Tq must change from ai to a2. To do so, we augment the valence of a 5-valent vertex v e Ui to 6-valent and then S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 299 Figure 2: The first three coronas of T1. Figure 3: The first three coronas of T[. The dark gray region is a subgraph inserted by augmentation of the valence of a vertex from 5 to 6; the light gray region is a subgraph inserted while interpolating a 6-valent vertex along an incident edge. These insertions continue throughout all coronas of T[. 300 Ars Math. Contemp. 14 (2018) 267-284 subdivide an edge of (U1) incident with v by inserting a 6-valent vertex. Augmentation and interpolation are both performed via the insertion of an infinite "cone" as follows. We choose a sequence of edges e2, e3, e4,..., with eH e (U), such that e2 and v are incident with a common face in F1, and for each i > 2, e4 and ei+1 are incident with a common face in Fj. On each of these edges we interpolate vertices, and we insert edges connecting vertices between U and Ui+1 ensuring that every face so created has covalence 5. Furthermore, if a created face is incident only with interpolated vertices, then its valence sequence is 6 Figure 7: In the diagram to the left, the (4, 6)-edge at the bottom must have a 6-valent vertex interpolated, along with the attendant subgraph. However, we wish to avoid non-concentricity; hence the single 4-valent vertex x is expanded to a (4,6,4)-path as in the diagram on the right. 5 x 5 We continue by induction; suppose a tessellation Tj has been created by this process. Then in the jth corona, there are finitely many faces which require a finite number of vertices to have their valences increased and a finite number of edges along which we must interpolate a vertex. This creates Tj+1 such that |F1,n| < \Fj+1,n\ = lF2,n| for n < j + 1, as the first j coronas are comprised only of faces with valence sequence a2. Furthermore, \ \ for all n G N. In this manner we can construct an infinite sequence of tessellations, namely {Tj : j G N}, with the properties that |F1,n| < \Fj,n\ for any j, n G N0, and \Fj,n\ = |F2,n| whenever j > n. In the previous example, we constructed the sequence in the process of transforming T1 with valence sequence [4,5,4, 5] into T2 with valence sequence [4,6,6,4, 5]; however, the process of creating {Tj : j g N0} is identical in any case where T\ and T2 are face-homogeneous and uniformly concentric with monomorphic valence sequences a1 and a2, respectively, where a1 < a2. Thus by Lemma 2.18, we obtain the following result. Theorem 3.7 (Growth Comparison Theorem). Let a1 and a2 be monomorphic valence sequences realized by tessellations T1,T2 G G4 4 U G3+ 5 U G3 6, with a1 < a2. Then Y(T1) < y(T2). Our convention is to index the face types (f1,..., fr for some r) in the following order: first wedges, then bricks, then notched bricks, and finally, other face types if any. A wedge in Fn with face type f is incident with a pi-1-valent vertex in Un-1, for i = 1,..., k. Similarly, the indices of face types of bricks begin with a brick in Fn incident with a p0-valent vertex and a pk-1-valent vertex in Un-1. A new index fj is not introduced if there is some fj for i < j with the same configuration of vertices in Un-1 and Un, up to orientation. For example, the valence sequence [4,6,8,8, 6,4] yields seven face types f1,..., f7, of which f1, f2, and f3 are wedge types and f4 through f7 are brick types. S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 303 When a monomorphic sequence [p0,... ,pk-1] is realized by a tessellation in G4j4 U G3+,5 U G3,6, then every face, with respect to any Bilinski diagram, can be only a wedge, a brick, or a notched brick. The indexing of face types when pj = pj for i = j allows a stricter labeling which we can use in several other cases. A face f in Fn is a wedge of type wj when the vertex incident with f in Un-1 corresponds to valence p4-1 in a. If instead f is a brick with incident vertices in Un-1 corresponding to valences pj-1 and pj-2 (indices here taken modulo k), then f has face type bj. Finally, if f a notched brick whose incident vertices in Un-1 have valences pj, pj-1 = 3, and pj-2, then f has face type nj. It is important to note that if pj-1 = 3, then faces of type nj never occur as offspring. This stricter labeling is used explicitly only for the few theorems which follow, by which we determine the number of offspring of each instance of these general face types. Furthermore, we demonstrate a first application of the accretion rules and half-counting of faces that were introduced in Section 3.1. Notation. Let T be a face-homogeneous tessellation with valence sequence a, labeled as a Bilinski diagram. We denote by Q(f) the number of faces in Fn+1 that are counted as offspring of a single face of face type f in Fn, for any n > 0. For T G G4,4 U G3+,5 U G3,6 we let 0(wj), 0(bj), and 0(nj) denote the number of offspring of a single wedge, brick, or notched brick of, respectively, of the given type. Lemma 3.8. For a face-homogeneous tessellation in G4,4 UG3+,5 UG3,6 with monomorphic valence sequence a = [p0,... ,pk-1], one has for i G {1,..., k}, A(wj) = Pi-22+ Pi - 2k + 3+ £pj, and (3.3) j/h "(bi) = pj-32+ pj - 2k + 5+ £ pj, (3.4) j/l2 where I1 = {i — 2, i — 1, i} and I2 = {i — 3, i — 2, i — 1, i}. Also, when pj-1 = 3, fi(nj) = pj-3 + pj+1 — 2k + 7 + £ pj (3.5) j/l3 with I3 = {i — 3, i — 2, i — 1, i, i + 1}. Proof. The reader is referred to the three offspring diagrams shown in Figure 8. Letting i G {1,..., k}, the first diagram applies when pj-1 > 4. If also pj-2,pj > 4 as in the diagram, then we have n(wi) = + 4 + k — 2 + £ (pj — 3) j/h pj-2 + pj — 2k + 3+ J2 pj. 2 j/h If instead pj-2 = 3, then the number of wedge offspring of wj is pj — 4 + — 3), 2j j/h 304 Ars Math. Contemp. 14 (2018) 267-284 Un-1 Un Un + 1 \) Un-1 Un Un + 1 Pi-1 Wi+1 bi+2 Wi+2 Wi-2 bi-1 } Wi-1 pi-1 Pi-2 H bi N ► Wi+1 ■ bi+2 ► Wi+2 ► Wi-3 bi-2 Wi-2 un-1 Un Un + 1 Pi Pi-1 Pi-2 Wi+2 bi+3 Wi+3 Wi-3 b i-2 } Wi-2 Figure 8: Offspring diagrams for the three general face types (respectively wedges, bricks, and notched bricks) of a tessellation with monomorphic, uniformly concentric valence sequence [po,... ,pk-1]. the number of brick offspring is k — 3, and the number of notched brick offspring is 1. Thus when pi-2 = 3, "(wi) = 1 + ^ + k - 3+ £ (pj - 3) 3 6. If k > 7 and if a is monomorphic, then a > [3,3,3, 3, 3,3,3]. In that case, Theorem 3.7 and Proposition 2.20 tell us that a has growth rate at least Y([3, 3, 3, 3, 3, 3, 3]) = 2(3 + V5). 3.3 Monomorphic non-concentric sequences The purpose of this section is to characterize the six forms of monomorphic, non-concentric valence sequences with positive angle excess. These sequences give rise to face types other than wedges, bricks, and notched bricks, and so the foregoing methods cannot be applied to compute their growth rates. An interesting situation arises when a tessellation is not uniformly concentric but nonetheless, by prudent selection of the root, admits some Bilinski diagram that is concentric. To illustrate this point, we examine sequences of the form [4,p, q]. Example 3.11. Consider the valence sequence a = [4,p, q] with 4 < p < q, where 1 + 1 < 4, and let T be a face-homogeneous tessellation with valence sequence a. For a to be realizable, clearly p and q must be even. Note as well that the inequality (2.4) is satisfied. While a is monomorphic and admits a concentric Bilinski diagram, a is not uniformly concentric (cf. the second case of Proposition 2.4). When a Bilinski diagram of T admits a 4-valent vertex v0 e Un (for some n) adjacent to the vertices u1,u2 e Un-1 and v1,v2 e Un, then the diagram is not concentric; the vertices v1 and v2 must also be adjacent, as T is 3-covalent. Hence ({v0, v1,v2}) is a cycle within (Un), causing the Bilinski diagram to be non-concentric. However, it is possible to avoid this configuration by choosing the root of the Bilinski diagram to be either a p-valent or a q-valent vertex. When so labeled, only four face types occur, as demonstrated by the offspring diagrams in Figure 11. Un-1 Un Un+1 Un-1 Un Un+1 are correct. □ • : 4-valent ► f1 o: p-valent □: q-valent Figure 11: Offspring diagrams for a concentric tessellation with valence sequence [4,p, q]. S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 307 One sees here that if the root is taken to be a p-valent vertex, the first corona consists entirely of faces of type f1, which produce in turn only offspring of types f2 and f3. Similarly, given a q-valent root, the first corona consists entirely of faces of type f2, which produce in turn only offspring of types f1 and f4. The non-concentric configuration described above can never be produced among the descendants of faces of types f1 or f2. Inspection of Figure 11 gives the first and second columns of the transition matrix M; the third and fourth columns, corresponding to f3 and f4, merit further explanation. A face of type f3 in Fn+1 has a p-valent vertex in Un+1; this vertex is incident with p - 5 faces of type f1 in Fn+2. So the behavior of a face of type f3 is effectively to collapse one of the faces in Un+2 of type f1 begotten by the adjacent face of type f2. Faces of type f4 behave similarly, collapsing a face of type f2 . These considerations give us M= 0 1 (p - 4) -1 0' 1 (q - 4) 0 0 -1 1 0 0 0 0 10 0 as the transition matrix M for this accretion rule for T. As the characteristic equation for M is of degree 4, it can be solved to determine that the maximum modulus of an eigenvalue of M is A = W[2(p - 4)(q - 4) - 16] + 2^(p - 4)2(q - 4)2 - 16(p - 4)(q - 4). By Theorem 3.3 and Theorem 2.16, A is the growth rate of T. This quantity can be minimized by minimizing pq subject to the initial conditions 1 + 1 < 4 and that p and q be even. We shall see in Section 3.4 the role played by this example. Growth rate formulas for each of the other five classes are derived in the Appendix. Theorem 3.12. Let a be a valence sequence such that n(a) > 0. Then a is both monomor-phic and non-concentric if and only if a is of one of the following six forms: (i) [3,p,p], with p > 14 and even; (ii) [4,p, q], with p and q both even, 4 < p < q, and p + 1 < |; (iii) [3,p, 3,p], with p > 7; (iv) [3, p, 4, p], with p > 5 and even; (v) [3, 3,p, 3, p], with p > 5; or (vi) [3,3,p, 3, q], with p, q > 4 and p + 1 < 2. Proof. The parity conditions and the inequalities bounding the parameters in each case are minimal such that a be indeed realizable as a tessellation with n(a) > 0. As noted in Remark 3.10, all valence sequences of length at least 6 are uniformly concentric. Furthermore, by Proposition 3.5, all valence sequences of length 3 are monomor-phic. Valence sequences [3,p,p], [4,p, q], and [3,p, 3,p] give rise to tessellations exemplifying cases 1, 2, and 4 respectively of Proposition 2.4, and hence cannot be uniformly concentric. As a face-homogeneous tessellation with valence sequence [3,p, 3,p] is also edge-transitive, the sequence must be monomorphic. The proof that the sequence [3, p, 4, p] 308 Ars Math. Contemp. 14 (2018) 267-284 must be monomorphic and uniformly non-concentric is given in the Appendix, where the growth rate of a corresponding tessellation is determined. We now prove that [3,3,p, 3,p] is monomorphic for all p > 5. As a 3-valent vertex is incident with a common face with any two of its neighbors, every 3-valent vertex must be adjacent to at least two p-valent vertices; otherwise some face would be incident with a (3,3, 3)-path. Consider a p-valent vertex v1. By face-homogeneity, v1 is adjacent to some 3-valent vertex u1, with u1 adjacent in turn to a 3-valent vertex u2 which is not adjacent to v0. But then the other vertex adjacent to u1 must be a p-valent vertex v2. This forces the pattern of valences at regional distance 1 from v1 to be (3,3,p,..., 3, 3,p); as v1 was arbitrary, this must be the pattern of valences at regional distance 1 from any p-valent vertex. As every vertex is at regional distance 1 from some p-valent vertex, [3, 3,p, 3,p] must be monomorphic; the first two coronas of a tessellation with this valence sequence rooted at a p-valent vertex is depicted in Figure 12. Furthermore, this local configuration to a p-valent vertex forces the local behaviors to a (3,3)-edge and a 3-valent vertex shown in Figure 13. Hence when a 3-valent vertex v0 is taken as the root of the Bilinski diagram of a tessellation with valence sequence [3, 3,p, 3, p], a pendant vertex occurs in (U3). This is shown in Figure 14. So [3, 3,p, 3,p] is monomorphic but not uniformly concentric; the argument for [3, 3,p, 3, q] is analogous. We have shown these six forms to be both monomorphic and non-concentric; that these are the only such valence sequences is proved via the exhaustive examination of cases in the Appendix. □ Figure 12: The first two coronas of a tessellation with valence sequence [3, 3, p, 3, p] rooted at a p-valent vertex. Each shaded region indicates p - 3 faces in F2 all having the same face type. 3.4 The main result The following theorem establishes the so-called "golden mean" as the least rate of exponential growth for face-homogeneous tessellations with monomorphic valence sequences. Theorem 3.13 (Least Exponential Growth Rate of Monomorphic Valence Sequences). The least growth rate of a face-homogeneous tessellation with monomorphic valence sequence a such that n(a) > 0 is 2 (1 + V5) and is attained by exactly the tessellations with valence sequences [4,6,14] and [3,4, 7,4]. • : 3-valent o : p-valent S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 309 • : 3-valent o: p-valent (A) (B) Figure 13: (A) Local configuration along an edge with edge-symbol (3, 3; 5,5} in a face-homogeneous tessellation with valence sequence [3, 3,p, 3,p]. (B) Local configuration in the same tessellation when rooted at a 3-valent vertex. Table 1: Table of the least exponential growth rate within each monomorphic class of valence sequences. All rates of growth have been truncated at four decimal places rather than being rounded. Class a Y(T 4. The following theorem gives a simple sufficient condition under which a realizable valence sequence is polymorphic. U„ Un+1 Figure 15: A configuration of faces demonstrating polymorphicity. Proposition 4.1. Let a = [p0,... ,pk-1] be the valence sequence of a face-homogeneous tessellation T e G4,4 U G3+,5. If there exist distinct i, j e {0,..., k - 1} such that Pi,Pi+1 > 4 and either S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 311 1. p, = pj, p,+ i = pj+i, and p,+2 = pj+2, or 2. p, = pj, p,+ i = pj-i, andp,+2 = pj-2, then a is polymorphic. Proof. As the only two forms of valence sequences of length k = 4 that satisfy the hypothesis, namely [p,p,p, q] and [p,p, q, r], are polymorphic (see Appendix), we assume that k > 5. Also, since condition (2) is identical to (1) save for orientation within the cyclic sequence, it suffices to assume that there are distinct i, j such that (1) holds. Furthermore, we may assume i = 0 due to the rotational equivalence of valence sequences. Since k > 5, there exists for some n a face in Fn incident with three consecutive vertices u0, ui, u2 e Un with valence p(um) = pm for m = 0,1,2. Let b be the brick in Fn+i incident with the edge u0ui, and let b' be the brick (or perhaps notched brick if p2 = 3) in Fn+i incident with the edge uiu2. Let vi,..., vr be the vertices in Un+i incident with ui in consecutive order, so that vi is incident with b and vr is incident with b'. Thus r = pi - 2 > 2. If a contains a subsequence [q,pi,p2] with q = p0, then p(vr) may equal either p0 or q, resulting in a choice of face types for b', and we're done. Otherwise we must have p(vr) = p0, which forces the vertex vr-2 and subsequent alternate neighbors of ui in Un+i also to be p0-valent. If pi is even, then p(vi) may equal either p2 or pj+2 in which case the wedge w e Fn+i incident with vertices vi, ui, v2 may be of either type w2 or type Wj+2, and T is polymorphic. (See Figure 15.) If pi is odd, then working backward as in the even case forces p(vi) = p0, which implies that either p0 = p2 or p0 = pj+2, and without loss of generality, we assume the former. Now we may assign p(v2) to be either p0 or pj+2, and the argument proceeds as in the even case. □ The existence of polymorphic valence sequences considerably complicates the computation of growth rates of face-homogeneous tessellations. The above proof suggests that, unlike in the monomorphic case, polymorphic valence sequences may admit many different accretion rules, as we illustrate in the next section. 4.2 Two non-isomorphic tessellations with the same valence sequence The minimal polymorphic valence sequence under the partial order on cyclic sequences, namely [4,4,4, 5], is unfortunately not amenable to study via our methods. In fact, there is no well-defined transition matrix between coronas, and this problem is shared by all valence sequences of the form [4,4,4, q] for q > 4. However, [4,4,6,8] provides us with the opportunity to investigate two distinct (but related) accretion rules. The valence sequence [4,4,6, 8] is representative of form [p,p, q, r] discussed in the Appendix. As every face is incident with a pair of adjacent 4-valent vertices, every realization of this valence sequence contains a countable infinity of pairwise-disjoint double rays, each induced exclusively by 4-valent vertices. Figure 16 (A) shows a strip-like patch bordering a double ray of 4-valent vertices. To obtain Figure 16 (B) from this (or vice versa), one can fix pointwise the half-plane on one side of the double ray while translating the half-plane on the other side along one edge of the double ray. To construct still other such (non-isomorphic) realizations, one can choose to "translate" along any one of these double rays by leaving fixed the half-plane on one side of the double ray but translating the half-plane on the other side by one edge. Since there exists 312 Ars Math. Contemp. 14 (2018) 267-284 ]- -c p- -c ]- -c -c -c :- - - ]- • : 4-valent o: 6-valent □ : 8-valent (A) (B) Figure 16: Two non-isomorphic patches of a tessellation with valence sequence [4,4,6,8], showing possible neighborhoods of double rays of 4-valent vertices. a countable infinity of double rays along which one may choose to translate one or the other or neither of the adjacent half-planes, there exists an uncountable class of pairwise non-isomorphic tessellations that all have the same valence sequence [4,4, 6,8]. While one might expect that all tessellations having the same valence sequence always have the same growth rate, we show that this is not so. We begin by observing that every 4-valent vertex in a face-homogeneous tessellation with valence sequence [4,4,6,8] is adjacent to two other 4-valent vertices and two vertices with valences 6 or 8; thus any given 4-valent vertex either has exactly one 6-valent and one 8-valent neighbor, has two 6-valent neighbors, or has two 8-valent neighbors. Furthermore, every 4-valent vertex lies on a double ray (two-way infinite path) of 4-valent vertices; if one vertex along this path has a 6-valent neighbor and an 8-valent neighbor, then so does every other vertex along the double ray. This is the behavior demonstrated in Figure 16 (A). If the local configuration specified in Figure 16 (A) is enforced along every double ray of 4-valent vertices, then the tessellation obtained is unique; let this tessellation be T\. We can then construct offspring diagrams for T as given in Figure 17. It is interesting to note that Ti is the dual of the Cayley graph of the group with presentation Gi = (a, b, c | a2 = b2 = c2 = (bc)3 = (caba)4 = 1) . Encoding the offspring diagrams into a matrix, we obtain the transition matrix Mi of Ti given below. The four entries underlined in the matrix are the only entries which change between this example and the next example, T2, that we construct. "0 0 0 1 0 0 0 0" 00100000 3 10 1110 0 M = 25200220 Mi = 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 11000100 The characteristic polynomial of Mi is fi(z) = (z — 1)(z + 1) (z2 + 3z + 1) (z4 — 3z3 — 4z2 — 3z +1) , which in turn gives that the eigenvalue of maximum modulus of Mi is Ai = 4 [3 + * 4.13016. S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 313 314 Ars Math. Contemp. 14 (2018) 267-284 Considering again the double-rays of 4-valent vertices, it is trivial to note that if a vertex on such a double ray has two 6-valent neighbors in the tessellation, then both vertices adjacent to it in the double-ray have two 8-valent neighbors. This local behavior is shown in Figure 16 (B). If this pattern is extended to all such double rays we obtain the tessellation T2, which is also the dual of a Cayley graph. The underlying group of this Cayley graph is G2 = (a, b,c,d | a2 = b2 = c2 = d2 = (ab)2 = (ad)2 = (cd)3 = (bc)4) . The growth behavior of T2 differs from that of T1 only in the offspring of faces of types f3 and f4, as shown in the offspring diagrams in Figure 18. Un-1 Un Un + 1 -1 Un Un + 1 f4 Un — 1 Un Un + 1 Un-1 Un Un+1 Un — 1 Un Un + 1 Kb f8 A f6 £4 Un 1 Un Un n+1 f7 Un — 1 Un Un+1 f8 f6 1 • : 4-valent 6-valent □ : 8-valent Figure 18: Offspring diagrams for T2. f 3 f 3 f 4 1 3 f 2 f 3 f 4 The effect of the change of offspring of types f2 and f3 in the transition matrix of T2 lies only in the underlined 2 x 2 submatrix of Mi, while the remainder of the matrix M2 S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 315 remains identical to M1. Hence we have M2 = 00100000 00010000 3 10 1110 0 25200220 01100010 00110001 1 0 0 1 1 0 0 0 11000100 The characteristic polynomial of M2 is f2(z) = (z - 1)2 (z6 + 2z5 - 15z4 - 40z3 - 15z2 + 2z + 1) . As polynomials of degree 6 are unfortunately not solvable by radicals, we obtain by approximation that the root of maximum modulus is A2 « 4.14659. As these growth rates are nearly the same, there is only a small difference in corona sizes in the first several coronas. However, the size of the coronas and distribution of face types differs greatly farther from the root. To demonstrate this, Table 2 gives corona sizes in Bilinski diagrams of T and of T2, both rooted at 4-valent vertices. Note that the sizes of the coronas of T2 dominate those of T1 only after the 13th corona. 4.3 Some conjectures Ideally, all tessellations realizing the same polymorphic valence sequence would have the same growth rate. The example of valence sequence [4,4,6,8] illustrates that this is not so. We propose the following definitions. Definition 4.2. Let a be some polymorphic valence sequence, and define Ta to be the set of isomorphism classes of face-homogeneous tessellations with valence sequence a. Let Aff =inf{y(T): T e }, (4.1) Aff =sup{Y(T): T e }, (4.2) L = {T : T e and y(T) = Aff}, and (4.3) H = {T : T e and y(T) = Aff}. (4.4) We conjecture that the lower and upper bounds Aa and ACT for any given valence sequence a are realized. Conjecture 4.3. Let a be a polymorphic valence sequence. Then L and Ha are nonempty. Bearing in mind the polymorphic valence sequence [4,4,6,8] analyzed in Section 4.2, we propose as a conjecture the following sharper version of Theorem 3.7. Conjecture 4.4. Let a1 and a2 be valence sequences such that a1 < a2. Then Affl < Aff2. (4.5) In the spirit of the famous quote of the late George Polya [12] ("If you can't solve a problem, then there is an easier problem you can solve: find it."), we offer the following (perhaps) easier conjecture. 316 Ars Math. Contemp. 14 (2018) 267-284 Table 2: Corona sizes in T and T2; emphasis on the 14th corona beyond which the coronas of T2 appear to exceed in size those of T1. n |Fl,n| |F2,n| n |F1 n| |F2 n 1 4 4 29 1.20050 x 1018 1.27748 x 1018 2 30 28 30 4.95826 x 1018 5.29701 x 1018 3 110 108 31 2.04784 x 1019 2.19652 x 1019 4 494 468 32 8.45791 x 1019 9.10786 x 1019 5 1938 1900 33 3.49325 x 1020 3.77673 x 1020 6 8272 7956 34 1.44277 x 1021 1.56603 x 1021 7 33464 32868 35 5.95887 x 1021 6.49377 x 1021 8 140046 136380 36 2.46111 x 1022 2.69268 x 1022 9 573610 565956 37 1.01648 x 1023 1.11655 x 1023 10 2.38167 x 106 2.34358 x 106 38 4.19821 x 1023 4.62986 x 1023 11 9.80378 x 106 9.73259 x 106 39 1.73393 x 1024 1.91983 x 1024 12 4.05773 x 107 4.02988 x 107 40 7.16140 x 1024 7.96071 x 1024 13 1.67365 x 108 1.67318 x 108 41 2.95777 x 1025 3.30099 x 1025 14 6.91836 x 108 6.93034 x 108 42 1.22161 x 1026 1.36878 x 1026 15 2.85585 x 109 2.87639 x 109 43 5.04544 x 1026 5.67580 x 1026 16 1.17992 x 1010 1.19181 x 1010 44 2.08385 x 1027 2.35352 x 1027 17 4.87218 x 1010 4.94504 x 1010 45 8.60662 x 1027 9.75910 x 1027 18 2.01257 x 1011 2.04947 x 1011 46 3.55467 x 1028 4.04670 x 1028 19 8.31149 x 1011 8.50179 x 1011 47 1.46814 x 1029 1.67800 x 1029 20 3.43297 x 1012 3.52419 x 1012 48 6.06363 x 1029 6.95799 x 1029 21 1.41782 x 1013 1.46172 x 1013 49 2.50438 x 1030 2.88520 x 1030 22 5.85596 x 1013 6.05990 x 1013 50 1.03435 x 1031 1.19637 x 1031 23 2.41857 x 1014 2.51322 x 1014 60 1.49395 x 1037 1.79797 x 1037 24 9.98918 x 1014 1.04199 x 1015 70 2.15777 x 1043 2.70207 x 1043 25 4.12567 x 1015 4.32117 x 1015 80 3.11654 x 1049 4.06079 x 1049 26 1.70397 x 1016 1.79166 x 1016 90 4.50134 x 1055 6.10274 x 1055 27 7.03766 x 1016 7.42979 x 1016 100 6.50145 x 1061 9.17148 x 1061 28 2.90667 x 1017 3.08066 x 1017 200 2.56861 x 10123 5.38996 x 10123 Conjecture 4.5. Let a1 and a2 be valence sequences with a1 < a2. Then Affl < Aff2. (4.6) If Conjecture 4.4 holds, then one could delete the condition of monomorphicity from the hypothesis of Theorem 3.7 and therefore from Theorem 3.13 as well. Moreover, the Appendix could be much abbreviated. For example, one could eliminate the exhaustive consideration of the many forms of 6-covalent face-homogeneous tessellations listed and treated there by observing that the least valence sequence a of length 6 with n(a) > 0 is [3, 3, 3,3,3,4]. Thus, if any tessellation with the polymorphic valence sequence [3,3,3, 3, 3,4] has growth rate greater than 1 (1 + a/5), then so does every tessellation with valence S. J. Graves and M. E. Watkins: Growth of face-homogeneous tessellations 317 sequence a > [3, 3, 3,3,3,4]. Beyond these conjectures, there are some open questions. Consider the partially ordered set of valence sequences, and in particular, the poset consisting of the polymorphic valence sequences. Question 4.6. As one goes up a chain in the poset, do intervals of the form [Aa, Aa] become (asymptotically) longer? Question 4.7. Do the intervals in the complement of U { [Act , Act] : a is polymorphic} a become arbitrarily long? If the answer to Question 4.7 is negative, we pose the following. Question 4.8. If x is a sufficiently large real number, is there always some polymorphic valence sequence a such that Aa < x < Aa ? Or, on the other hand, Question 4.9. Do there exist polymorphic sequences a, t such that [Aa,Aa] PI [Ar, At] = 0? References [1] S. Bilinski, Homogene mreze ravnine, Rad Jugoslav. Akad. Znanosti i Umjetnosti 271 (1948), 145-255,http://dizbi.hazu.hr/object/14 96. [2] S. Bilinski, Homogene Netze der Ebene, Bull. Internat. Acad. Yougoslave Cl. Sci. Math. Phys. Tech. (N. S.) 2 (1949), 63-111. [3] J. A. Bruce and M. E. Watkins, Concentric Bilinski diagrams, Australas. J. Combin. 30 (2004), 161-174, https://ajc.maths.uq.edu.au/pdf/30/ajc_v30_p161.pdf. [4] S. J. Graves, Growth of Tessellations, Ph.D. thesis, Syracuse University, May 2009. [5] S. J. Graves, Tessellations with arbitrary growth rates, Discrete Math. 310 (2010), 2435-2439, doi:10.1016/j.disc.2010.04.023. [6] S. J. Graves, T. Pisanski and M. E. Watkins, Growth of edge-homogeneous tessellations, SIAM J. Discrete Math 23 (2009), 1-18, doi:10.1137/070707026. [7] S. J. Graves and M. E. Watkins, Appendix to "Growth of face-homogeneous tessellations", 2017, arXiv:1707.03443 [math.CO]. [8] B. Grunbaum and G. C. Shephard, Edge-transitive planar graphs, J. Graph Theory 11 (1987), 141-155, doi:10.1002/jgt.3190110204. [9] B. Grunbaum and G. C. Shephard, Tilings and Patterns, A Series of Books in the Mathematical Sciences, W. H. Freeman & Company, New York, 1987. [10] J. F. Moran, The growth rate and balance of homogeneous tilings in the hyperbolic plane, Discrete Math. 173 (1997), 151-186, doi:10.1016/s0012-365x(96)00102-1. [11] P. Niemeyer and M. E. Watkins, Geodetic rays and fibers in one-ended planar graphs, J. Combin. Theory Ser. B 69 (1997), 142-163, doi:10.1006/jctb.1996.1733. 318 Ars Math. Contemp. 14 (2018) 267-284 [12] G. P6lya, Mathematical Discovery: On Understanding, Learning, and Teaching Problem Solving, Volume I, John Wiley & Sons, New York, 1962. [13] J. Siagiova and M. E. Watkins, Covalence sequences of planar vertex-homogeneous maps, Discrete Math. 307 (2007), 599-614, doi:10.1016/j.disc.2006.07.014.