{'fraction_non_alphanumeric': 0.05503630984400215, 'fraction_numerical': 0.01428859601936525, 'mean_word_length': 3.5426084300549787, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Eulerian graph embeddings and trails confined to lattice tubes

Embeddings of graphs in sublattices of the square and simple cubic lattice known as tubes (or prisms) are considered. For such sublattices, two combinatorial bounds are obtained which each relate the number of embeddings of all closed eulerian graphs with k branch points (vertices of degree greater than two) to the number of self-avoiding polygons. From these bounds it is proved that the entropic critical exponent for the number of embeddings of closed eulerian graphs with k branch points is equal to k, and the entropic critical exponent for the number of closed trails with k branch points is equal to k + 1. One of the required combinatorial bounds is obtained via Madras' 1999 lattice cluster pattern theorem, which yields a bound on the number of ways to convert a self-avoiding polygon into a closed eulerian graph embedding with k branch points. The other combinatorial bound is established by constructing a method for sequentially removing branch points from a closed eulerian graph embedding; this yields a bound on the number of ways to convert a closed eulerian graph embedding into a self-avoiding polygon.


Introduction
In [1] combinatorial bounds are obtained which relate the number of square lattice embeddings of all open or all closed eulerian graphs with a fixed number of vertices of degree 4 to the number of selfavoiding walks or polygons, respectively. The work established general versions of bounds first proposed by Guttmann and Whittington [3] and Gaunt et al [4] and extends and improves on arguments given by Zhao and Lookman [5]. Let Z 3 (N, M ) denote the sublattice of the simple cubic lattice defined by the vertex set {(x, y, z) ∈ Z 3 |0 ≤ y ≤ N, 0 ≤ z ≤ M }. For given N ≥ 0, M ≥ 1, such a sublattice is referred to here as an (N, M )-tube (or prism). In this paper, combinatorial bounds are obtained which relate the number of embeddings in an (N, M )-tube of all closed eulerian graphs with a fixed number of branch points (vertices of degree greater than two) to the number of self-avoiding polygons in an (N, M )-tube. Embeddings of graphs in tubes have been studied as models of branched polymers in confined geometries, and the effects of such confinement on the limiting (as the number of edges in the embedding goes to infinity) entropic and entanglement properties of these models have been studied (see [6,7,8,9,10] and references therein). An essential feature of the tube is that the graph embeddings can only extend indefinitely in one of the lattice directions, i.e. the tube is essentially a onedimensional lattice [8], and this can fundamentally change the nature of the entropic and entanglement behaviour of these models when compared to less restrictive geometric confinement. This type of confinement can however be relevant to real polymer systems such as polymers confined to pores or between parallel plates. The combinatorial bounds established herein lead to the result that the entropic critical exponent for embeddings of all closed eulerian graphs with k branch points is equal to k more than the corresponding exponent for self-avoiding polygons. This is analogous to the situation in the square lattice, so the confinement to a tube has not changed this asymptotic property of the limiting entropy. However it is important to note that while for the square lattice the limit defining the entropic critical exponent for self-avoiding polygons has yet to be proved to exist, for the tube this limit is known to exist and is zero [10].
In order to explain the results of this paper and their significance more clearly, it is essential to first introduce various definitions and notation for graph embeddings. (Definitions are similar to those given in [1,10].) In particular, the term closed (open) trail on a graph refers to a walk on the graph which uses no edge of the graph more than once and which starts and ends (does not start and end) at the same vertex. An open trail on a graph which does not use any vertex of the graph more than once is called a self-avoiding walk on the graph. The set of edges underlying a self-avoiding walk forms a subgraph referred to as an undirected self-avoiding walk. A closed trail on a graph which returns to the first vertex only once and does not use any other vertex more than once is called a self-avoiding circuit on the graph. The set of edges underlying a self-avoiding circuit forms a subgraph referred to as a self-avoiding polygon. The term closed (open) eulerian trail on a connected graph refers to a closed (open) trail that uses each edge of the graph exactly once. The well known result due to Euler is that a closed (open) eulerian trail exists for a given connected graph with at least one edge if and only if the graph has no (exactly two) odd degree vertices. Any graph which admits a closed (open) eulerian trail is referred to as a closed (open) eulerian graph. As mentioned above, a vertex of degree greater than two in a graph is referred to as a branch point of the graph, and a vertex of degree one will be referred to as a leaf or end point.
Given integers N, M ≥ 0 and k ≥ 1, define G(N, M ) to be the set of all homeomorphically irreducible (all degree two vertices are supressed) connected abstract graphs which have at least one embedding in an (N, M )-tube; a lattice embedding of a graph τ is any subgraph of the lattice which is homeomorphic to τ (e.g. an undirected self-avoiding walk on the (N, M )-tube is homeomorphic to the connected graph with exactly one edge, and hence the undirected walk is an embedding of that graph). Define G 0 (N, M ) ⊆ G(N, M ) to be the set of all such abstract graphs which have no odd degree vertices, and finally define G 0 k (N, M ) ⊆ G(N, M ) to be the subset of these graphs with exactly k even degree vertices, i.e. k branch points. For any graph τ ∈ G(N, M ), we define g n (τ, N, M ) to be the number of n-edge embeddings (up to translation in the x-direction) of τ in Z 3 (N, M ); define p n (N, M ) to be the number of n-edge self-avoiding polygons (up to translation in the x-direction) in Z 3 (N, M ); and define E k n (N, M ) = τ ∈G 0 k (N,M ) g n (τ, N, M ) to be the number of n-edge closed eulerian embeddings having k branch points, n-edge k-euler embeddings for short. Furthermore, let E 0 n (N, M ) = p n (N, M ) and let E n (N, M ) = k≥0 E k n (N, M ) be the number of n-edge closed eulerian embeddings. Finally, define t k n (N, M ) to be the number of n-step closed trails on Z 3 (N, M ) starting in the plane x = 0 and having k branch points (k vertices which are traversed more than once in the trail), n-step k-trails for short, and let t n (N, M ) = k≥0 t k n (N, M ), the total number of n-step closed trails. Note that, following the arguments that lead to [1, equation (1.18)], it can be shown that: where the term on the right uses the fact that for N, M ≥ 1 the maximum vertex degree is six. For branched polymer models, counts such as g n (τ, N, M ) represent the number of possible configurations for a polymer of size n so that the entropy per monomer is given by n −1 log g n (τ, N, M ). In general, for such a model it is believed that the asymptotic form of such a count is given by An θ e κn as n → ∞, where κ represents the limiting entropy per monomer and θ is known as the entropic critical exponent associated with the given model. Thus the entropic critical exponent is obtained by dividing the count by e κn , taking logarithms, dividing by log n and then taking the limit as n → ∞, and the entropic critical exponent is said to exist if this limit can be proved to exist. The focus here will be on the counts defined above hence we denote the entropic critical exponents for g n (τ, N, M ), p n (N, M ), The limiting entropy per monomer for each of p n (N, M ) and g n (τ, N, M ) has been previously studied. Soteros and Whittington [7] proved that the following limit exists and is strictly less than the corresponding limit for self-avoiding walks (this latter fact is notably distinct from the situation in the full lattice where the two limits are known to be the same [11]): In [10], for any graph τ ∈ G 0 (N, M ) it is proved that Thus the limiting entropy per monomer for all of these quantities is the same. Furthermore, via a transfermatrix approach similar to that used in [8] to study self-avoiding walks in one dimensional lattices, it is proved in [10, equation ( Note again that the existence of this limit has yet to be proved for unconfined self-avoiding polygons. For any integer k ≥ 1 define τ k to be the k-daisy graph as defined in [1, Section 3], i.e. a specific abstract connected closed eulerian graph with k vertices of degree 4. In this paper, for any k ≥ 1 any N, M ≥ 0 such that τ k ∈ G 0 k (N, M ), it is proved that there exist positive constants (independent of n) , C, C, r, and N such that for all even n ≥ N , For even n, dividing by e κp(N,M )n , taking logarithms, dividing by log n, and then letting n → ∞ in equation (1.8) proves that the entropic critical exponents for g n (τ k , N, M) and E k n (N, M ), respectively, are given by where the fact that lim n→∞ log ( an b ) log n = b has been used. Thus the entropic critical exponent goes up by one for each branch point of the embedding. For the entropic critical exponent of k-trails, equations (1.1) and (1.
which is k more than the corresponding critical exponent for rooted self-avoiding polygons or selfavoiding circuits.
For the corresponding square lattice results in [1], establishing bounds similar to equation (1.8) involved a pattern theorem argument for the lower bound and, for the upper bound, a construction for removing branch points from a closed eulerian embedding. An analogous approach is taken here. For the lower bound, we first establish a pattern theorem, i.e. we prove, given an appropriate kind of pattern, that there exists > 0 for which all but exponentially few sufficiently large n-edge self-avoiding polygons in Z 3 (N, M ) each contain the pattern at least n times (i.e. with positive density). This pattern theorem is proved here using the results of Madras [2]. The approach to obtaining the pattern theorem here is different than that used for the square lattice result since the limiting entropy (given by equation (1.2)) for self-avoiding polygons in a tube is not the same as that for self-avoiding walks in a tube. The resulting pattern theorem is then used to show that it is possible to convert all but exponentially few sufficiently large self-avoiding polygons into k-euler embeddings. For the upper bound, a construction for removing branch points from an arbitrary k-euler embedding is presented; this construction does not involve the detailed case analysis that was required for the square lattice results of [1], however, the constants C and r in equation (1.8) now depend on the tube dimensions (N and M ).
We obtain the pattern theorem and lower bound result in the next section, and in the third section present the upper bound result.

A Pattern Theorem for Lattice Clusters in (N, M )-tubes
In this section, the arguments of Madras [2] are used to obtain pattern theorems for certain types of clusters, including self-avoiding polygons, in an (N, M )-tube. While the transfer-matrix arguments as presented in the proof in [10, Lemma 5.5] and in [8,Section 5] can be used to yield the required pattern theorem for self-avoiding polygons in tubes, two advantages of the approach presented here are that a pattern theorem for closed eulerian embeddings also results and some details of the argument used for the closed eulerian embedding case can also be applied to establishing the upper bound in Section 3.
In order to obtain the required pattern theorem for clusters in tubes via [2, Theorem 2.1], the cluster axioms (CA1), (CA2), and (CA4) of [2] must hold for any clusters under consideration. Cluster axiom (CA1) basically defines the types of clusters that can be considered. For the purposes here, given any integers N ≥ 0 and M ≥ 0 let the lattice L = Z 3 (N, M ). We note that the set S * of translations which leave L invariant are just translations in the x-direction, i.e. S * = {(x, y, z) ∈ Z 3 |x ∈ Z, y = 0, z = 0}. Thus S * is isomorphic to Z and in that sense L is a one-dimensional lattice. For N, M ≥ 1, following the notation of [2, Section 3.1 (j)], L is also called a 1-dimensional slab in Z 3 .
For convenience we focus on clusters which are (or can be characterized as) subgraphs of L and denote the "size" of the cluster to be the number of edges in the cluster (although the results in [2] are applicable to other measures of size). Given a set of clusters of interest, for each positive integer n, let C n be the set of all clusters with n edges. Then (CA1) of [2] is satisfied provided G ∈ C n implies that any x-translate of G (i.e. G + (x, 0, 0) for x ∈ Z) is also in C n . This axiom is satisfied for any of the embeddings of interest, e.g. self-avoiding polygons in L, eulerian graph embeddings in L, and lattice trails in L. Satisfaction of cluster axiom (CA2) of [2] depends on how each cluster is "weighted" within C n . For simplicity, we focus on the case that for each n ≥ 0, each G ∈ C n is given weight one. In this case, cluster axiom (CA2) is automatically satisfied.
Let C * n ⊆ C n be the set of clusters in C n whose lexicographically smallest vertex is in the plane In this case, we refer to the plane x = −x G as the left-most plane of the cluster and x = b − x G as the right-most plane of the cluster.
In order to easily prove a version of cluster axiom (CA4) of [2], we define patterns and proper patterns in a more restrictive way than in [2]. Given any b ∈ Z, any subgraph of V b with at least one vertex in each of the planes x = 0 and x = b is referred to as a pattern with span b, or b-pattern for short. Given a set of clusters of L, C = ∪ n<∞ C n , we say G ∈ C contains a b-pattern P if P is the subgraph of G generated by the vertices in V b , i.e. G ∩ V b = P , or if there exists a translate of V b such that G ∩ (V b + (x, 0, 0)) = P + (x, 0, 0); in the latter case we say P occurs at (x, 0, 0) in G.
A b-pattern P is said to be a proper b-pattern with respect to C if i) there are infinitely many values of n such that P is contained in some cluster in C n , and ii) there exists a cluster G ∈ C in which P occurs at t ∈ S * and such that G \ (V b + t) still contains the left-most and right-most planes of G.
Condition (ii) is needed to exclude patterns which can only occur at the left-most or the right-most plane of a cluster and nowhere else.
It will be useful to consider two additional potential properties (Tube Axioms) of C, namely: There exists a concatenation process defined for C on L and associated integers t L ≥ 1, c L ≥ 0 such that: only the right-most plane of G 1 and the left-most plane of G 2 can be altered in the concatenation process).

TA 2.
There exists an integer m L > 0 such that: For any integer b ≥ 0 and any b-pattern (not necessarily proper) P that occurs at (0, 0, 0) in some finite size cluster in C * with span s ≥ b + 1 (i.e. P occurs at the start of some cluster), there exists a cluster G ∈ C * with span b + m L which also contains P at (0, 0, 0) (i.e. P is also at the start of G). Similarly, given any b-pattern P that occurs at (s − b, 0, 0) in some finite size cluster in C * with span s ≥ b + 1 (i.e. P occurs at the end of some cluster), there exists a cluster G ∈ C * with span b + m L which contains P at (m L , 0, 0) (i.e. P also ends G ).
Essentially (TA2) says that any pattern P which starts (ends) some cluster can occur at the start (end) of another cluster whose span only depends on the span of P and on L, and not on the size of the original cluster in which P occurred.
In most circumstances if (TA1) holds it is also possible to prove that (CA3) of [2] is satisfied, i.e. that the limit lim n→∞ n −1 log |C * n | exists and is finite. The fact that for this case these arguments lead to equation (2.1) was presented earlier with equation (1.2). The same concatenation argument can be applied to closed eulerian embeddings in L (without altering the total number of branch points) so that (TA1) and equation (2.1) are satisfied for C = E. That is: Lemma 2. (TA1) holds for C = E, i.e. for closed eulerian embeddings, for the same choice of t L and c L as applies in Lemma 1. Furthermore, concatenating a k 1 -euler embedding to a k 2 -euler embedding by this process yields a (k 1 + k 2 )-euler embedding and the following limit exists To see that (TA2) holds for self-avoiding polygons: without loss of generality consider the first case, i.e. let P be a b-pattern that occurs at the start (at (0,0,0)) of a self-avoiding polygon π ∈ E 0, * with span s π > b. In the plane x = b, P has an even number m ≥ 2 of vertices of degree one (since it is a pattern in a polygon with span greater than b). Since π is a polygon, these vertices of degree one (end points) must be joined in pairs within π by m/2 mutually avoiding self-avoiding walks to the right of x = b (i.e. in V sπ−b−1 + (b + 1, 0, 0)). In order to create another polygon which starts with P , we only need to ensure that to the right of x = b the same pairs of vertices are joined to each other as were joined in π. The existence of π tells us that there is a way to join these specific pairs of vertices by m/2 mutually avoiding self-avoiding walks within a section of span s π − b − 1, i.e. within V sπ−b−1 + (b + 1, 0, 0). Define s min to be the minimum value of s such that these specific pairs of end points can be connected in a self-avoiding manner within V s + (b + 1, 0, 0). Clearly s min only depends on the location of the end points in x = b and on the number of ways to connect them using m/2 mutually avoiding self-avoiding walks in L, i.e. it does not depend on any properties of P other than P 's configuration in x = b. More generally, let H be the vertex set of V 0 (the subgraph of L obtained by the intersection of L with the plane x = 0). H has (N + 1)(M + 1) vertices. For each non-empty vertex set S j ⊆ H with an even number of elements, and each partition σ j,k of S j into two element subsets, let s j,k denote the minimum span s required to connect the vertex pairs of σ j,k using mutually avoiding self-avoiding walks within V s (if it is not possible to connect the pairs in σ j,k this way, set s j,k = 0). Define m L = 1 + max j,k s j,k > 0. Thus s min ≤ m L − 1 and by the definition of s min there exists a span s min + b + 1 self-avoiding polygon such that P occurs at the start of the polygon. This polygon can easily be extended to a polygon with span m L by concatenating a specific span (m L − 1 − s min ) polygon starting at the plane x = b + s min + 1. This argument establishes (TA2) for self-avoiding polygons, that is: Furthermore, the same definition of m L works for the case of C = E, the set of all closed eulerian embeddings. As above, consider a b-pattern P that occurs at the start (at (0,0,0)) of a closed eulerian embedding π with span s π > b. In this case, the right-most plane of P will always contain an even number, m ≥ 2, of odd degree vertices. Note that if there exists a way to connect the odd degree vertices of P in x = b pairwise using a set of m/2 mutually avoiding self-avoiding walks to the right of x = b such that a closed eulerian embedding is created, then (TA2) can be proved using the same argument as was used for the self-avoiding polygon case. The following argument shows that such a set of mutually avoiding self-avoiding walks exists. Add an edge in the +x-direction to each odd degree vertex of P in x = b to obtain P 1 . The plane x = b + 1 intersects the (L, M )-tube in an L × M grid; such a grid has at least one Hamiltonian walk, a walk which visits each vertex of the grid exactly once. Let h be such a Hamiltonian walk for the L × M grid and now label the degree one vertices of P 1 in x = b + 1 as v i , i = 1, ..., m, according to the order in which they occur in h. For each i = 1, ..., m/2, join v 2i−1 to v 2i using the edges of h that go from v 2i−1 to v 2i . The result is a set, W 1 , of up to m/2 mutually avoiding closed eulerian embeddings in the (L, M )-tube. Each embedding in W 1 has at least one edge in the plane x = b + 1. Let k be the number of distinct embeddings in W 1 . For each distinct embedding, there is a corresponding minimum value of i such that the vertex v i and an edge of h leaving from v i to a vertex, call it u i , is an edge of the embedding. Translate this edge of the embedding a distance 2 in the +x-direction, and reconnect its endpoints to v i and u i respectively using two sequences of two edges in the +x-direction so that the result is still a closed eulerian embedding. Perform this operation to each distinct embedding in W 1 to create W 2 , another set of k mutually avoiding closed eulerian embeddings in the (L, M )-tube. Label the embeddings of W 2 as π j , j = 1, ..., k (k ≤ m/2), according to the order that they are encountered in h on x = b + 3. Let i j be the value of i such that v i + (2, 0, 0) is in π j . Next for k > 1, concatentate the π j together to form W 3 , a single closed eulerian embedding, using the following procedure: For each j = 1, ..., k − 1, concatenate π j to π j+1 by removing the edges {u i j + (1, 0, 0), u i j +(2, 0, 0)} and {v i j+1 + (1, 0, 0), v i j+1 +(2, 0, 0)}, and then adding in the sequence of edges of h that join u i j to v i j+1 twice so that first the sequence of edges is translated to join u i j + (1, 0, 0) to v i j+1 + (1, 0, 0) and next the sequence is translated to join u i j + (2, 0, 0) to v i j+1 + (2, 0, 0). Note that W 3 \ P is a set of mutually avoiding self-avoiding walks which connect the odd degree vertices of P pairwise. Hence (TA2) holds as discussed above. Note further that the number of branch points in the embedding is not increased in such a construction; this fact will be used later for the upper bound argument in Section 3. More specifically the above argument leads to the following lemma. Returning now to the more general situation, basically (TA1) and (TA2) ensure that, given any cluster G ∈ C n , one can remove a section of span b, say, from the middle of the cluster and by (TA2) the two bits of the cluster that remain (one contains the left-most plane of G and the other the right-most plane) can be each turned into clusters (without using order of n space), and then (TA1) implies a third cluster can be concatenated in between the two "end-clusters". If the third cluster contains a specific proper pattern P , then this is a way to insert the pattern P into a given cluster at an arbitrary location. This sketch of an argument leads us to the following proposition. Note that this proposition means that (CA4) of [2] is satisfied and hence [2, Theorem 2.1] ensures that the required pattern theorem follows. Proposition 1. Given L = Z 3 (N, M ) and a set of clusters C of L which satisfy (CA1) and (CA2) of [2] and (TA1) and (TA2), for every proper pattern P with respect to C there exists an integer b ≥ 0 and a vector b ∈ S * such that: For every cluster G ∈ C and every vertex v of G, there is another cluster G ∈ C and a translation vector t = t(v) ∈ S * such that v ∈ V b +b +t, G contains P at t, and G \(V b +b +t) = G\(V b +b +t).
Proof. Let P be a proper pattern with span b 1 . Since P is a proper pattern, there exists at least one element of C * which contains P in its interior (i.e. not starting at the left-most plane or ending at the right-most plane). Choose such an element, G p ∈ C * , which has the least span, b 2 . Let n p be the number of edges in G p , and let (x p , 0, 0) be the location of P in G p . Let m L be as in (TA2) and t L be as in (TA1) and define b = 2m L + 2t L + b 2 and b = (−m L − t L − x p , 0, 0).
Let G ∈ C and v = (x v , y v , z v ) be a vertex in G. Without loss of generality assume that the leftmost plane of G is at x = 0 and let b G ≥ 0 be the span of G. Define t = (x v + m L + t L + x p , 0, 0) so that b + t = (x v , 0, 0). Consider the two subgraphs of L given by For 0 ≤ x v < b G , by definition P 1 contains v and is an x v -pattern that occurs at the left-most plane of a cluster (namely G) with span greater than x v , hence (TA2) implies that there exists a span x v + m L cluster G 1 such that P 1 = G 1 ∩ V xv . Using (TA1), concatenate G 1 and G p to create G 3 such that P 1 = G 3 ∩ V xv (since m L > 0 and only the right-most plane of G 1 is altered in the concatenation) and P occurs at t = ( , 0, 0)). So that G has the desired properties.
For x v = b G ≥ 0, the existence of the concatenation process of (TA1) tells us that G can be concatenated to any cluster to create a third cluster,G, with a span greater than or equal to t L + b G and such thatG ∩ is a pattern that can occur in a cluster with span greater than b G (i.e. inG) and thus by (TA2) it can be extended on the right to a cluster G 1 with span x v + m L . Then using (TA1), concatenate G 1 and G p to create the required G .
Let C = E 0 , i.e. the set of self-avoiding polygons in L, and let P be any proper pattern with respect to E 0 . Define p n (N, M ; ≤ m, P ) to be the number of self-avoiding polygons in E 0, * n which contain at most m translates of P . The following result is the required pattern theorem and by Theorem 2.1 of [2] it is an immediate consequence of Proposition 1 and the fact that self-avoiding polygons in L satisfy (CA1), (CA2), (TA1) and (TA2). For self-avoiding polygons, given any proper pattern P , two straightforward consequences of Corollary 1 are that: There exist > 0 and n P > 0 such that

Removing branch points from eulerian lattice embeddings (N, M )-tubes
In this section we obtain the upper bound result. The basic idea is to start with an n-edge closed eulerian embedding with k branch points and convert it into a self-avoiding polygon while only altering m edges of the original embedding, where m depends on N , M and k and not on n. One can actually use a construction similar to that used in the proof of Proposition 1 by taking advantage of Lemmas 2 and 4 from the previous section.
Thus consider m L , t L and c L as fixed at the polygon values (i.e. those needed for Lemmas 2 and 4).
Let ω be any n-edge, span s, k-euler embedding in L with its left-most plane at x = 0. Label the branch points of ω as v 1 , v 2 , v 3 , ..., v k according to the lexicographic order of their coordinates in Z 3 . The goal will be to remove the branch points and create a span s polygon ω which differs from ω only on sections of span at most (2m L + t L ) with the section locations determined by a set V of up to k x-coordinates. If s ≤ 2m L + t L , then this can be accomplished by setting ω to be a polygon with span s and letting V = {0}. Otherwise, the branch points can be removed via the following algorithm: Define 0, 0)). P 1 does not contain v k−i and it is a pattern that can appear in a closed eulerian embedding, hence via Lemma 4 it can be extended on the right to a closed eulerian embedding G 1 with span x k−i and with l 1 < k i branch points. Similarly P 2 can be extended on the left to a closed eulerian embedding G 2 with span s − x k−i − t L and with l 2 < k i − l 1 branch points. Concatenate G 1 and G 2 via Lemma 2 to create ω i+1 , a closed eulerian embedding with k i+1 = l 1 + l 2 < k i branch points. For x k−i ≥ m L and s < x k−i + t L + m L , again let P 1 = ω i ∩ V x k−i −m L and form G 1 with span x k−i and with l 1 < k i branch points as above. Now extend one of the edges of G 1 in the plane x = x k−i by adding parallel pairs of horizontal edges to the right of x = x k−i to create a span s closed eulerian embedding ω i+1 with k i+1 = l 1 < k i branch points. Similarly for x k−i < m L , let P 2 = ω i ∩ (V s−m L + (m L , 0, 0)) and use Lemma 4 to extend it to the left to create a span s closed eulerian embedding ω i+1 with k i+1 < k i branch points. In all cases, ω i+1 differs from ω i only on a section of span at most (2m L + t L ). If k i+1 = 0 then set ω = ω i+1 and V = V i+1 and stop, otherwise continue. Since at least one branch point is removed at each step, if the process continues to step i = k − 1 the result will be k k = 0 and ω = ω k . Note that since ω is an eulerian embedding with zero branch points it must be a self-avoiding polygon.
The result from this procedure is a n -edge, span s, polygon ω and a set V consisting of l ≤ k positive integers corresponding to the x-coordinates where a section of the embedding was replaced. Note that n + l (m L + t L /2) − 2l (2m L + t L + 1)(2m L + t L +1) ≤ n ≤ n − l (m L + t L /2) + 2l (2m L + t L + 1)(2m L + t L + 1). The number of distinct (ω , V )'s resulting from the above algorithm is bounded above by the number of ways to form such a pair, i.e. More than one choice of ω however could lead to the same pair (ω , V ). To determine an upper bound on the number of distinct ω's leading to the same (ω , V ), consider the number of ways of starting with (ω , V ) and reversing the process. The number of ways of reversing the process is bounded above by the number of ways of choosing n − |ω \ ∪ x∈V (V 2m L +t L + (x + m L , 0, 0))| edges from ∪ x∈V (V 2m L +t L + (x + m L , 0, 0)) to replace those edges removed from ω. But this is certainly bounded above by the total number of subsets of the edge set of ∪ x∈V (V 2m L +t L + (x + m L , 0, 0)), which is bounded above by 2 2k(2m L +t L +1)(2m L +t L +1) . This leads to the following upper bound: where r = 2(2m L + t L + 1)(2m L + t L + 1) and C = 2 r D, and where D is such that k(2rk + 1) ≤ D k for all k ≥ 1. This gives the required upper bound for equation (1.8).