A partial matching, or a chord diagram, is a finite graph consisting of edges and vertices of degree zero or one, with the vertex set {1,2,…,m} for a positive integer m [8]. A partial matching is used to present secondary structures of polymeric molecules such as RNAs (see Section 2). The aim of this paper is to establish a mathematical basics for discussing partial matchings, from a viewpoint of lattice presentations.

In this paper, we consider transformations between two states of partial matchings. In Section 3, we introduce the lattice presentation of a partial matching, and we clarify the correspondence between structures of chord diagrams and lattice presentations. In Section 4, we introduce the notion of the lattice polytope associated with a pair of partial matchings, and we discuss the equivalence of lattice polytopes. In Section 5, we introduce transformations of lattice presentations and lattice polytopes, and the area of a transformation. We give a lower estimate of the area of a transformation by using the area of a lattice polytope, and in certain cases we construct transformations with minimal area (Theorem 5.9). In Section 6, we introduce the notion of the reduced graph of a lattice polytope, and we show that there exists a transformation of a lattice polytope with minimal area if and only if its reduced graph is an empty graph (Theorem 6.3). Section 7 is devoted to showing lemmas and propositions. In Section 8, we consider simple connected lattice polytopes. We show that when a lattice polytope P is connected and simple, a certain division of P into n rectangles presents a transformation with minimal area, and in certain cases, any transformation with minimal area is presented by such a division of P (Corollary 8.2).

Partial matchings present secondary structures of polymeric molecules such as RNAs. An RNA is a single-strand chain of simple units of nucleotides called nucleobases, with a backbone with an orientation from 5'-end to 3'-end, which folds back on itself. The nucleobases consist of 4 types, guanine (G), uracil (U), adenine (A), and cytosine (C), and there are interactions between nucleobases: adenine and uracil, guanine and cytosine, which form A-U, G-C base pairs. The secondary structure of an RNA is the information of base pairs. For an RNA strand, regard each nucleobase as a vertex, and label the vertices by integers 1,2,… from 5'-end to 3'-end, and connect two vertices forming each base pair with an edge. Then we have a chord diagram presenting the secondary structure. Chord diagrams have been studied to investigate RNA secondary structures, which consist of nesting structures formed by "parallel" bonds, and pseudo-knot structures containing "cross-serial" bonds. In particular, a special kind of structure called a "k-noncrossing structure" plays an important role and enumerations of k-noncrossing structures are widely investigated [3, 5, 6, 8]. Our motivation of this research was to give a new method of investigating RNA secondary structures.

Partial matchings are used to predict the most possible forms of RNA secondary structures with optimal free energy, by means of dynamic programming, calculating energy for every possible state of partial matchings, and investigating one partial matching at a time; there are many references, for example see [7, 8, 9, 10]. In this paper, from a different viewpoint, we focus on investigating paths between two fixed states of partial matchings.

In this section, we introduce the notion of the lattice presentation of a partial matching, and we see the correspondence between structures of chord diagrams and lattice presentations.

We recall the precise definition of a partial matching, or a chord diagram. A partial matching, or a chord diagram, is a finite graph consisting of edges and vertices of degree zero or one, with the vertex set {1,2,…,m} for a positive integer m. A chord diagram is represented by drawing the vertices 1,2,…,m in the horizontal line and the edges in the upper half plane. We denote by (x,y) (x,y∈{1,2,…,m}, x > y) the edge connecting the vertices x and y and call it an arc, and we call a vertex with degree zero an isolated vertex. In this paper, we use the term "partial matching" when we consider its lattice presentation, and the term "chord diagram" when we consider the chord diagram itself.

For the xy-plane ℝ2, put C={(x,y)∈ℝ2∣x,y>0}, and we denote by C₊ (respectively C_-) the half plane {(x,y)∈C∣x≤y} (respectively {(x,y)∈C∣x≥y}). We call a point (x,y) of C such that x and y are integers a lattice point.

Definition 3.1. For a partial matching δ, the lattice presentation Δ of δ is a set of lattice points in C\∂C+ such that each element (x,y) of Δ presents an arc (x,y) when x (respectively an arc (y,x) when y) of δ. Note that for each arc (x,y) of δ, we have two points (x,y)∈C+ and (y,x)∈C− of Δ.

Example 3.2. The left figure of Figure 3.1 is a chord diagram δ with five arcs (1, 5), (2,4), (3,7), (6,8), (10, 12), and two isolated vertices 9 and 11, and the right figure of Figure 3.1 is the lattice presentation of δ.

Figure 1. A chord diagram (left) and the lattice presentation (right).

Partial matchings are investigated by considering special structures called k-nesting and k-noncrossing; for example, see [3, 5, 6, 8]. We see the correspondence of a partial matching with such a structure and the lattice presentation. By definition of lattice presentation of a partial matching, we have the following propositions. For two points v₁, v₂ of C, we denote by R(v1,v2) the rectangle in C whose diagonal vertices are v₁ and v₂. For a point v=(x,y)∈C+, put v*=(y,x)∈C−.

Two arcs (x₁, y₁) and (x₂, y₂) of a chord diagram are said to be separated if the intervals [x₁, y₁] and [x₂, y₂] in ℝ are disjoint. Two arcs are said to be non-separated if they are not separated.

Proposition 3.3. For a lattice presentation Δ={v1,v2,v1*,v2*} with vj∈C+,vj*∈C− (j=1,2), the following conditions are mutually equivalent (see Figure 3.2).

Figure 2. Separated arcs of a chord diagram and the lattice presentation, where we shadow rectangles R ( v 1 , v 2 ) and R ( v 1 * , v 2 * ) . For this figure, v₁=(1,5) and v₂=(7,10).

• (1) A lattice presentation Δ presents separated arcs.

• (2) We have R(v1,v2)⊂C+.

• (3) We have R(v1,v2)∩R(v1*,v2*)≠∅.

Proof. Put v1=(x1,y1) and v2=(x2,y2). Let us assume x1<x2. Then, two arcs (x1,y1) and (x2,y2) are separated if and only if y1<x2. Let us denote the vertices of the rectangle R(v1,v2) by v1=(x1,y1),u1=(x1,y2),u2=(x2,y1), and v2=(x2,y2). Since xj<yj (j=1,2), with the assumption x1<x2, we see that v1,u1,v2∈C+, and y1<x2 if and only if u2=(x2,y1)∈C−, which is equivalent to the condition that R(v1,v2)⊂C+. Since R(v1*,v2*) is the mirror reflection of R(v1,v2) with respect to the line ∂C+, and v₁ and v₂ are not in ∂C+, R(v1,v2)⊂C+ if and only if R(v1,v2)∩R(v1*,v2*)≠∅.

For a rectangle R(v₁, v₂), we say it is of type I (respectively of type II, III, IV) if the vector from v₁ to v₂, v2−v1∈ℝ2 is in the first (respectively second, third, fourth) quadrant.

Let k be a positive integer. A chord diagram is called k-nesting if its arcs consist of k distinct arcs (x₁, y₁), (x₂, y₂), …, (x_k, y_k) such that

(3.1)x1<x2<⋯<xk<yk<yk−1<⋯<y1,

see Figure 3.3.

Figure 3. A nesting chord diagram and the lattice presentation.

Proposition 3.4. For a lattice presentation Δ={v1,…,vk,v1*,…,vk*} with vj∈C+,vj*∈C− (j=1,…,k), the following conditions are mutually equivalent.

• (1) A lattice presentation Δ presents a k-nesting chord diagram.

• (2) Each rectangle R(vi,vj) is of type II or IV for i,j=1,…,k,i≠j.

• (3) Changing the indices if necessary, we have the following: R(vj,vj+1) is of type IV for each j=1,…,k−1.

Proof. Put vj=(xj,yj) (j=1,…,k). The relation (3.1) is equivalent to xi<xj<yj<yi when i<j (respectively xj<xi<yi<yj when i>j). Since vi,vj∈C+, this is equivalent to xi<xj and yj<yi when i<j (respectively xj<xi and yi<yj when i>j), which is equivalent to the condition that R(vi,vj) is of type IV when i<j (respectively of type II when i>j). Thus the conditions 1 and 2 are equivalent. Again, the relation (3.1) is equivalent to xj<xj+1<yj+1<yj for j=1,…,k−1, which is equivalent to the condition that R(vj,vj+1) is of type IV for each j=1,…,k−1. Thus the conditions 1 and 3 are equivalent.

A chord diagram is called k-crossing if its arcs consist of k distinct arcs (x1,y1),(x2,y2),…,(xk,yk) such that

(3.2)x1<x2<⋯<xk<y1<y2<⋯<yk,

see Figure 3.4. A chord diagram is called k-noncrossing if there exists no k-crossing subgraph.

Figure 4. A crossing chord diagram and the lattice presentation.

Proposition 3.5. For a lattice presentation Δ={v1,…,vk,v1*,…,vk*} with vj∈C+,vj*∈C− (j=1,…,k), the following conditions are mutually equivalent.

• (1) A lattice presentation Δ presents a k-crossing chord diagram.

• (2) Each rectangle R(vi,vj) is of type I or III and contained in C₊ for i,j=1,…,k,i≠j.

• (3) Changing the indices if necessary, we have the following: R(v1,vk) is contained in C₊ and R(vj,vj+1) is of type I for each j=1,…,k−1.

Proof. Put vj=(xj,yj) (j=1,…,k).

The relation (3.1) is equivalent to xi<xj<yi<yj when i<j (respectively xj<xi<yj<yi when i>j).

This is equivalent to xi<xj, yi<yj, and xj<yi when i<j (respectively xj<xi, yj<yi, and xi<yj when i>j). When i<j, xi<xj and yi<yj if and only if R(vi,vj) is of type I, and since R(vi,vj) is a rectangle whose vertices are (xi,yi),(xi,yj),(xj,yi) and (xj,yj), with the condition xi<xj and yi<yj, we see that xj<yi if and only if R(vi,vj) is contained in C₊. Thus, by the same argument, we see that the condition 1 is equivalent to the condition that R(vi,vj) is of type I when i<j (respectively of type III when i>j) and contained in C₊. Thus the conditions 1 and 2 are equivalent. Again, the relation (3.2) is equivalent to xj<xj+1 and yj<yj+1 for j=1,…,k−1, and xk<y1. Then, by the same argument, we see that the conditions 1 and 3 are equivalent.

In this section, we give the definition of the lattice polytope associated with a pair of partial matchings. We take the standard basis e1,e2 of the xy-plane ℝ2, where e1=(1,0) and e2=(0,1). For two distinct points v, w of ℝ2, we denote by vw¯ the segment connecting v and w. We say a segment vw¯ is in the x-direction or in the y-direction if w=v+xe1 or w=v+ye2 respectively for some x,y∈ℝ: we say a segment is in the x-direction or in the y-direction if it is parallel to the x-axis or the y-axis, respectively. We denote by R(v, w) the rectangle in ℝ2 whose diagonal vertices are v and w. For a point v=(x₁,y₁) of ℝ2, we call x₁ (respectively y₁) the x-component (respectively the y-component) of v. For a set of points of ℝ2, {v1,…,vn} with vj=(xj,yj) (j=1,…,n), we call the set {x1,…,xn,y1,…,yn}, the set of x, y components of {v1,…,vn}. The set of x, y-components of a lattice presentation Δ with n arcs is a set X of 2n distinct points of ℝ, which, as a multiset, consists of two copies of X.

Definition 4.1. A lattice polytope is a polytope P consisting of a finite number of vertices of degree zero (called isolated vertices) with multiplicity 2, vertices of degree 2 with multiplicity 1, edges, and faces satisfying the following conditions.

• (1) Each edge is either in the x-direction or in the y-direction.

• (2) The x-components (respectively y-components) of isolated vertices and edges in the x-direction (respectively y-direction) are distinct.

• (3) The boundary ∂P is equipped with a coherent orientation as an immersion of a union of several circles, where we call the union of edges of P the boundary of P, and denote it by ∂P.

The set of vertices are divided to two sets X₀ and X₁ such that each edge in the x-direction is oriented from a vertex of X₀ to a vertex of X₁, and isolated vertices are both in X₀ and X₁ with multiplicity 1. We denote X₀ (respectively X₁) by Ver0(P) (respectively Ver1(P)), and call it the set of initial vertices (respectively terminal vertices).

In graph theory, a lattice polytope is defined as a polytope whose vertices are lattice points [1, 4], but in this paper, when we say that P is a lattice polytope, we assume that each edge of P is either in the x-direction or in the y-direction.

For a lattice polytope P, we denote by -P^* the orientation-reversed mirror reflection of P with respect to the line x=y.

Proposition 4.2. Let Δ,Δ′ be two lattice presentations with the same set of x, y-components. Then, Δ and Δ' form a pair of lattice polytopes P, -P^* satisfying that each edge is either in the x-direction or in the y-direction such that it connects a point of Δ and a point of Δ'. See Figure 4.1.

Figure 5. The lattice polytope associated with Δ and Δ', where Δ is presented by black circles and Δ' is presented by X marks.

Definition 4.3. We call a lattice polytope P as in Proposition 4.2 the lattice polytope associated with lattice presentations Δ and Δ', and denote it by P(Δ,Δ′). Note that we have a choice of P.

We denote by Ver0(P) (respectively Ver1(P)) the vertices of P coming from Δ (respectively Δ'), which consist of a half of the elements of Δ (respectively Δ'). We give an orientation of P by giving each edge in the x-direction (respectively in the y-direction) the orientation from a vertex of Ver0(P) to a vertex of Ver1(P) (respectively from a vertex of Ver1(P) to a vertex of Ver0(P)).

Proof of Proposition 4.2. We take the set of points Δ and Δ' as the set of vertices. Since the set of x, y-components is a set of 2n distinct points in ℝ, for each point v of Δ, v is either an isolated vertex satisfying v=v' for v′∈Δ′, or there are exactly two points v' and w' of Δ' such that vv′¯ and vw′¯ is in the x-direction and the y-direction, respectively. The same argument implies the same thing for each point of Δ'. Thus we have a pair of lattice polytopes P, -P^* satisfying the required conditions. That -P^* is the mirror reflection of P with respect to the line x=y follows from the fact that for each point of Δ or Δ', its mirror reflection is also a point of Δ or Δ'..

Since the sets of x, y-components of vertices of P and -P^* are the same, and the union of the vertices of P∪(−P*) form Δ∪Δ′, the set of x, y-components of vertices of P is the same with that of Δ and Δ'. Since each edge of a lattice polytope is either in the x-direction or the y-direction, the sets of x, y-components of Veri(P) (i=0,1) is the same. Thus the set of x, y-components of Veri(P) (i=0,1) is the same with that of Δ and Δ', and we have the following.

Remark 4.4. Let n be the number of the vertices of Veri(P) (i=0,1). Then, the set X of x, y-components of Veri(P) (i=0,1) is the same with that of Δ and Δ', and it consists of 2n distinct elements. Thus the multiset of x, y-components of the vertices of P is the set of two copies of X.

Conversely, for a pair of sets V₀ and V₁ of points of ℝ2 with the same set of x, y-components consisting of 2n distinct elements of ℝ, there is a unique lattice polytope P such that Veri(P)=Vi (i=0,1).

Remark 4.5. For a lattice polytope P, we denote by -P the lattice polytope obtained from P by orientation-reversal. Then, for a lattice polytope P=P(Δ,Δ′) associated with lattice presentations Δ and Δ', −P(Δ,Δ′)=P(Δ′,Δ). Further, since we equipped P with orientation such that each edge in the x-direction (respectively in the y-direction) is oriented from a vertex of Ver0(P) to a vertex of Ver1(P) (respectively from a vertex of Ver1(P) to a vertex of Ver0(P)), the orientation changes when we rotate P by π/2: the π/2-rotation of unoriented P is as a new polytope -ρ(P), where ρ(P) is the π/2-rotation of oriented P. Similarly, the mirror reflection of unoriented P is as a new polytope -P^*, the orientation-reversed mirror reflection of P.

We introduce the equivalence relation among lattice polytopes. Let P be a lattice polytope with 2n vertices. Since the set of x, y-components of Veri(P) (i=0,1) consists of 2n distinct elements, for Veri(P)={v1,…,vn} with vj=(xj,yj) (j=1,2,…,n) satisfying x1<x2<…<xn, we take an element σ of the symmetric group Sn of n elements determined by yσ−1(1)<yσ−1(2)<…<yσ−1(n). We denote the element σ of Sn by σi(P) (i=0,1). Let π be a permutation

π=12…n−1nnn−1…21∈Sn.

Proposition 4.6. Let σ be an element of Sn, which will be identified with a set of points of ℝ2, {(j,σ(j))−(n/2,n/2)∣j=1,2,…,n}. Then, the mirror reflection of σ with respect to the line x=n+1 is πσ, and the π/2 rotation of σ is σ−1π.

Definition 4.7. Let P, P' be lattice polytopes consisting of 2n vertices. Then, we say P and P' are equivalent if (σ0(P),σ1(P)) and (σ0(P′),σ1(P′)), or (σ0(P),σ1(P)) and ((σ0(P′))−1,(σ1(P′))−1), are related by right or left multiplication by the permutation π.

Proof of Proposition 4.6. Let S be a matrix presenting σ. The matrix presenting π, which will be denoted by P, is

P=0⋯010⋯10⋮⋱⋮1⋯00.

Since the right multiplication by P changes the jth column of the operated matrix to the (n-j)th column (j=1,2,…,n), SP presents the mirror reflection of σ with respect to the line x=n+1. Since the order of a product of matrices is the reversed order of a product of the presented elements of Sn, we see that πσ is the mirror reflection of σ with respect to the line x=n+1.

Let {(xj,yj)∣j=1,2,…,n} (x1<x2<…<xn) be the set of points of ℝ2 identified with σ. Then, we have yσ−1(1)<yσ−1(2)<…<yσ−1(n). Let us rotate σ by π/2. Then, the set of points changes to {(−yj,xj)∣j=1,2,…,n}. Put xj′=−y σ−1 (n+1−j) and yj′=x σ−1 (n+1−j). Let ρ be the element of Sn presenting the π/2 rotation of σ. Since −yσ−1(n)<−yσ−1(n−1)<…<−yσ−1(1), x′1<x′2<…<x′n, hence we see that y′ ρ−1 (1)<y′ ρ−1 (2)<…<y′ ρ−1 (n). Since yj′=x σ−1 (n+1−j)=x σ−1 π(j), xj=y′πσ(j) (j=1,2,…,n). Thus ρ−1=πσ, and we see ρ=σ−1π..

In particular, by Proposition 4.6 and by definition, we have the following. For a lattice polytope P, we call a subgraph of P whose boundary is homeomorphic to an immersed circle a component of P, and we say a lattice polytope is connected if it consists of one component.

Proposition 4.8. For a lattice polytope P, P −P*. Thus, a connected lattice polytope P associated with lattice presentations of partial matchings is unique up to equivalence.

In this section, we consider transformations of lattice presentations of partial matchings. In Subsection 5.1, we introduce transformations of lattice presentations and lattice polytopes. In Subsection 5.2, we introduce the area of a transformation and we give a lower estimate of the area of a transformation and in certain cases we construct a transformation with minimal area (Theorem 5.9). Lemmas and propositions are shown in Section 6.

5.1. Transformations of Lattice Presentations and Lattice Polytopes

For two arcs a1=(x1,y1) and a2=(x2,y2) of a chord diagram, we consider new arcs a1′=(x1′,y1′) and a2′=(x2′,y2′), where {x1′,x2′,y1′,y2′}={x1,x2,y1,y2} with {a1,a2}≠{a 1′,a 2′}. We consider a new chord diagram obtained from exchanging a₁, a₂ to a₁', a₂'. We call the new chord diagram the result of a transformation between two arcs a₁ and a₂.

For a lattice presentation of a chord diagram, we define a transformation as the operation presenting a transformation of the chord diagram. For two lattice presentations Δ and Δ' with the same set of x, y-components, we define a transformation from Δ to Δ' as a sequence of transformations such that the initial and the terminal lattice presentations are Δ and Δ', respectively. We denote it by Δ→Δ′.

Definition 5.1. Let Δ be a set of lattice points. For a point u of ℝ2, we denote by x(u) and y(u) the x and y-components of u, respectively. For two distinct points v, w of Δ, we consider the rectangle R(v, w) one pair of whose diagonal vertices are v and w. Put v˜=(x(w),y(v)) and w˜=(x(v),y(w)), which form the other pair of diagonal vertices of R(v,w). Then, consider a new set of lattice points obtained from Δ, from removing v,w and adding v˜,w˜. We call the new set of lattice points the result of a transformation of Δ by the rectangle R(v, w), and denote it by t(Δ,R(v,w)).

For two sets of lattice points Δ and Δ' with the same set of x, y-components, we define a transformation from Δ to Δ' as a sequence of transformations by rectangles such that the initial and the terminal lattice points are Δ and Δ', respectively. We will denote it by Δ→Δ′.

Recall that for a lattice polytope P, we denote by -P^* the orientation-reversed mirror reflection of P with respect to the line x=y.

Lemma 5.2. A transformation between two arcs of a chord diagram is presented by a transformation of the presenting lattice presentation Δ by rectangles R(v,w) and -R(v,w)^* for v,w∈Δ.

Proof. Since two arcs of a chord diagram are either separated, nesting, or crossing, it suffices to consider the following three cases: (1) a₁, a₂ are separated and a₁', a₂' are nesting, (2) a₁, a₂ are nesting and a₁', a₂' are crossing, and (3) a₁, a₂ are crossing and a₁', a₂' are separated. Since the transformation is described as in Figure 5.1, we have the required result.

Figure 6. Transformations between two arcs and the presenting transformations of lattice presentations.

Let P be a lattice polytope. Then, for v,w∈Ver0(P), consider a new set of vertices obtained from Ver0(P) by a transformation by R(v,w). Since the multiset of x, y-components are preserved, the resulting new vertices and Ver1(P) form a new lattice polytope (see Remark 4.4).

Definition 5.3. For a lattice polytope P and v,w∈Ver0(P), we call the lattice polytope P' determined by the lattice points Ver0(P′)=t(Ver0(P),R(v,w)) and Ver1(P′)=Ver1(P) the result of a transformation of P by the rectangle R=R(v, w) and denote it by t(P , R).

For two lattice polytopes P and P' with the same set of x, y-components, we define a transformation from P to P' as a sequence of transformations by rectangles R_j such that the initial and the terminal lattice polytopes are P and P', respectively. We denote it by P→P′.

For a pair of lattice polytopes P and -P^*, and rectangles R and -R^*, we denote t(P,R)∪t(−P*,−R*) by t(P∪(−P*),R∪(−R*)), and call it the result of a {\it transformation of P∪(−P*) by rectangles R∪(−R*). Note that t(−P*,−R*)=−t(P,R)* and t(P∪(−P*),R∪(−R*))=t(P,R)∪(−t(P,R)*).

Definition 5.4. For two pairs of lattice polytopes P, -P^* and P', -P'^* with the same set of x, y-components, we define a transformation from P∪(−P*) to P′∪(− P ′ *) as a sequence of transformations by rectangles Rj∪(−Rj*) such that the initial and the terminal lattice polytopes are P∪(−P*) and P′∪(− P ′ *), respectively, and denote it by P∪(−P*)→P′∪(− P ′ *).

For lattice presentations of partial matchings Δ, Δ' with the same set of x, y-components, and an associated lattice polytope P, Δ=Ver0(P∪(−P*)), Δ′=Ver1(P∪(−P*)). Thus, by Lemma 5.2, we have the following. When we consider transformations of lattice polytopes, we regard isolated vertices Ver1(Q) as a lattice polytope Q' whose initial and terminal vertices are the isolated vertices: Ver0(Q′)=Ver1(Q′)=Ver1(Q).

Proposition 5.5. Let Δ, Δ' be lattice presentations of partial matchings with the same set of x, y-components, and let P be a lattice polytope associated with Δ and Δ'. Then, a transformation Δ→Δ′ is described by a transformation of lattice polytopes P∪(−P*)→Ver1(P∪(−P*)).

In particular, a transformation of a lattice polytope P→Ver1(P) presents a transformation Δ→Δ′.

Example 5.6. We consider lattice presentations Δ and Δ' as in Figure 4.1, where we denote the points of Δ=Ver0(P∪(−P*)) by black circles and the points of Δ′=Ver1(P∪(−P*)) by X marks. In Figure 5.2, we give an example of a transformation Δ→Δ′, described by a transformation of lattice polytopes P∪(−P*)→Ver1(P∪(−P*)), where we denote by shadowed rectangles the used rectangles. In this case, it suffices to see a transformation P→Ver1(P), which induces a transformation P∪(−P*)→Ver1(P∪(−P*)).

Figure 7. Transformation of lattice polytopes P∪(−P*) associated with lattice presentations of partial matchings, where the vertices of Ver0(P∪(−P*)) (respectively Ver1(P∪(−P*))) are indicated by black circles (respectively X marks)

5.2. Areas of Transformations

For a lattice polytope P, let us define the area of |P|, Area|P|, as follows. Recall that for a lattice polytope P, we give an orientation of P by giving each edge in the x-direction (respectively in the y-direction) the orientation from a vertex of Ver0(P) to a vertex of Ver1(P) (respectively from a vertex of Ver1(P) to a vertex of Ver0(P)). Then, ∂P has a coherent orientation as an immersion of a union of several circles. The space ℝ2, which contains P, is divided into several regions A1,…,Am by ∂P. For each region A_i (i=1,…,m), let ω(Ai) be the rotation number of P with respect to A_i, which is the sum of rotation numbers of the components of P, with respect to A_i. Here, the rotation number of a connected lattice polytope Q with respect to a region A of ℝ2\∂Q is the rotation number of a map f from ∂Q=ℝ/2πℤ to ℝ/2πℤ which maps x∈∂Q to the argument of the vector from a fixed interior point of A to x. Here, the rotation number of the map f is defined by (F(x)-x)/2π, where F:ℝ→ℝ is the lift of f and x∈∂Q. We define Area(Ai) for a region A_i by the area induced from Area(R)=|x2−x1||y2−y1| for a rectangle R whose diagonal vertices are (x₁, y₁) and (x₂, y₂). Then, we define the area of P, denoted by Area(P), by Area(P)=∑ i=1mω(Ai)Area(Ai), and the area of |P|, denoted by Area|P|, by Area|P|=∑ i=1m|ω(Ai)Area(Ai)|.

Remark 5.7. For two lattice polytopes P₁ and P₂, Area|P1∪P2|=Area|(−P1*)∪(−P2*)|, but Area|P1∪P2| is not always equal to Area|P1∪(−P2*)|. Thus, for a lattice polytope P associated with lattice presentations Δ and Δ', Area|P| depends on the choice of the components of P.

Definition 5.8. Let Δ, Δ' be two lattice presentations of partial matchings with the same set of x, y-components. Let us consider a transformation Δ=Δ0→Δ1→⋯→Δk=Δ′, with Δj=t(Δj−1,Rj∪(−Rj*)) for a rectangle R_j (j=1,2,…,k). Then, we call ∑ j=1k|Area(Rj)| the area of a transformation Δ " Δ'.

We say that a connected lattice polytope P is simple if the face of P is homeomorphic to a 2-disk in ℝ2. For a lattice polytope P with regions A1,…,Am divided by ∂P, attach each region A_i with right-handed (resp. left-handed) orientation when ω(Ai) is positive (resp. negative) (i=1,…,m). Then the union of |ω(Ai)| copies of the closure of A_i bounds ∂P. We call the union the region of P, which will be denoted by the same notation P. Further, if edges uv¯ and wz¯ of P have a transverse intersection, then we call the intersection point a crossing.

Theorem 5.9. Let Δ, Δ' be a pair of lattice presentations of partial matchings with the same set of x, y-components. We consider a transformation Δ=Δ0→Δ1→⋯→Δk=Δ′, with Δj=t(Δj−1,Rj∪Rj*) for a rectangle R_j (j=1,2,…,k). Let P be a lattice polytope associated with Δ and Δ'. Then

(5.1)∑ j=1kArea(Rj)=12Area(P∪(−P*))

and

(5.2)∑ j=1k|Area(Rj)|≥12Area|P∪(−P*)|.

Further, when P satisfies either the following condition (1) or (2),

(5.3)∑ j=1k|Area(Rj)|≥Area|P|,

and there exists transformations which realize the equality of (5.3), where the conditions are as follows.

• (1) The rotation number ω(A) is equal to ϵ for any region A surrounded by an embedded closed path in ∂P, where ϵ∈{+1,−1} (see Figure 5.3 for example).

  Figure 8. Example of a lattice polytope P satisfying the condition (1), where the vertices of Ver 0 ( P ) (respectively Ver 1 ( P ) ) are indicated by black circles (respectively X marks).
  

• (2) The lattice polytopes P and -P^* are disjoint, and, when we regard crossings as vertices, P is regarded as the union of simple lattice polytopes P1,…,Pm and Qi1,…,Qini (i=1,…,m) such that Pi∩Pj (i≠j) is empty or consists of one crossing in ∂Pi∩∂Pj and Qi1,…,Qini are mutually disjoint and contained in the interior of P_i (see Figure 5.4 for example).

  Figure 9. Example of a lattice polytope P satisfying the condition (2), where the vertices of Ver 0 ( P ) (respectively Ver 1 ( P ) ) are indicated by black circles (respectively X marks).
  

Remark 5.10. The condition (1) indicates that each connected component of P is in the form of the projected image into the xy-plane of a closed braid in the xyz-space in general position with respect to the z-axis [2].

Proof of Theorem 5.9. For a point u of ℝ2, we denote by x(u) and y(u) the x and y-components of u respectively. For a rectangular R(v,w), we consider the other pair of diagonal vertices of R(v,w), v˜=(x(w),y(v)) and w˜=(x(v),y(w)). Then, we assign to R(v,w) an orientation such that the edges are oriented from v to v˜, from v˜ to w, from w to w˜, and from w˜ to v. Then, this induces an orientation of P and -P^* which coincides with the original orientation of P and -P^*, and by Lemma 7.1 we see that

∑ j=1k(Area(Rj∪(−Rj*))=Area(P∪(−P*)),

and

∑ j=1kArea|Rj∪Rj*|≥Area|P∪(−P*)|.

Let Q be a lattice polytope. Then, since the mirror reflection of an edge of Q in the x-direction (respectively y-direction) is an edge of Q^* in the y-direction (respectively x-direction), the orientation of any closed path C in ∥ Q and C^* in ∥Q^* coincide as an embedded circle in ℝ2. Hence Area(Q)=Area(Q*), and hence, for j=1,…,k,

Area(Rj∪(−Rj*))=Area(Rj)+Area(−Rj*)=2Area(Rj)

and

Area|Rj∪(−Rj*)|=|Area(Rj)|+|Area(−Rj*)|=2|Area(Rj)|.

Hence we have (5.1) and (5.2).

When the lattice polytope P satisfies the condition 1 or 2, Area(P∪(−P*))=Area(P)+Area(−P*). Since Area(P)=Area(−P*), we have (5.3). In these cases, the boundary ∂P can be divided to a union of boundaries of simple connected lattice polytopes. In order to show that there exists a transformation which realizes the equality of (5.3), first we show the following claims.

Claim (a). For a simple connected lattice polytope Q, there is a transformation Ver0(Q)→Ver1(Q) by rectangles R_j (j=1,…,k) such that

(5.4)∑ j=1k|Area(Rj)|=|Area(Q)|.

Claim (b). For simple connected lattice polytopes Q,Q1,…,Ql such that Q1,…,Ql are mutually disjoint and contained in the interior of Q, and Q∪Q1∪⋯∪Ql is a region obtained from a 2-disk Q by removing Q1,…,Ql, there is a transformation Ver0(Q∪∪i=1lQi)→Ver1(Q∪∪i=1lQi) by rectangles R_j (j=1,…,k) such that

(5.5)∑ j=1k|Area(Rj)|=Area|Q∪∪i=1lQi|=||Area(Q)|−∑ i=1 l|Area(Qi)||.

First we show Claim (a). By Proposition 7.2, there is a rectangular R=R(v,w) contained in the region P with v,w∈Ver0(Q) such that Q\R forms a simple lattice polytope Q'. This implies that |Area(R)|+|Area(Q′)|=|Area(Q)|. Hence, in order to show Claim (a), it suffices to show that there is a transformation Ver0(Q′)→Ver1(Q′) satisfying (5.4) with Q=Q'. Let n be the number of vertices of Ver0(Q). Since v,w of R=R(v,w) are vertices of Ver0(Q), we see that if Q' is connected, then the number of vertices of Ver0(Q′) is n-1. If Q' is not connected, then Q' consists of 2 components, and the sum of the number of vertices of Ver0(Q′) is n, thus the number of vertices of Ver0(Q′) which come from a connected component is less than n. If the number of vertices of Ver0(Q′) is 2, then Q' is a rectangular, and we have (5.4) with Q=Q'. Thus, by induction on the number of vertices of connected components, we can construct a transformation satisfying (5.4).

For the other Claim (b), by a similar argument, we can show that there exists a transformation satisfying (5.5). We can take rectangles R inductively. When the vertices v,w of a used rectangle R(v,w) come from distinct components, then the number l of simple connected lattice polytopes is reduced by one.

Now, we construct a transformation such that ∑j|Area(Rj)|=Area|P|, assuming that P satisfies the condition (1) or (2). We show the case when P is connected, and Qi1,…,Qini (i=1,…,m) of the condition (2) are empty graphs. Let us regard ∂P as an immersion of a circle.

(Step 1) Take an interval I of ∂P which starts from a crossing x and comes back to x. If there is another interval J in I which starts from a crossing y and comes back to y, then take J instead of I. Repeating this process, we have an interval I of ∂P which bounds a simple connected lattice polytope Q₁ whose vertices consists of the vertices of P and one crossing x.

(Step 2) For a lattice polytope Q₁ of Step 1, if x∈Ver1(Q1), then put P₁=Q₁. Then, by Claim (a), we have a transformation P→(P\P1)∪Ver1(P1). If x∈Ver0(Q1), then consider Q2=P\Q1, and repeat Step 1 several times. Since x∈Ver0(Q1) become a vertex in Ver1(Q2), we obtain Q_n such that the crossings are in Ver1(Qn). Put P₁=Q_n, and then by Claim (a) we see that there is a transformation P→(P\P1)∪Ver1(P1).

By repeating this process, we have a transformation P→Ver1(P), which is a transformation Δ→Δ′ such that ∑j|Area(Rj)|=Area|P|. See Figures 5.5 and 5.6.

Figure 10. Example of a transformation of a lattice polytope P satisfying the condition (1). We have a transformation of P by composite of transformations of P₁, P₂, P₃, where P₁, P₂, P₃ are indicated by shadowed regions, and the vertices of Ver0(P) (respectively Ver1(P)) are indicated by black circles (respectively X marks).

Figure 11. Example of a transformation of a lattice polytope P satisfying the condition (2). We have a transformation of P by composite of transformations of P₁, P₂, P₃, P₄, where the vertices of Ver0(P) (respectively Ver1(P)) are indicated by black circles (respectively X marks).

The case when Qi1,…,Qini (i=1,…,m) of the condition 2 may not be empty graphs can be shown by the same argument by using Claim (b). Thus there is a transformation such that ∑j|Area(Rj)|=Area|P| when P satisfies the condition (1) or (2).

Proposition 5.11. There exists a lattice polytope P such that for any transformation of P by rectangles R1,…,Rk, ∑ j=1k|Area(Rj)|>Area|P|.

Proof. We consider a lattice polytope as illustrated by the leftmost figure of Figure 5.7, where the vertices of Ver0(P) (respectively Ver1(P)) are indicated by black circles (respectively X marks), and the numbers in regions divided by ∂P denote the rotation numbers. Assume that there is a transformation of P by rectangles R1,…,Rk such that ∑ j=1k|Area(Rj)|=Area|P|. Then, by Lemma 7.1, any R_j is disjoint with any region whose rotation number is zero. Thus, we have only one applicable rectangle R1=R(v1,w1) for v1,w1∈Ver0(P) as in the figure. Then, by a transformation of P by R₁, we have a lattice polytope P₁ as in the middle figure of Figure 5.7. By the same argument, we have only one applicable rectangle R2=R(v2,w2) for v2,w2∈Ver0(P1) as in the figure. Then, by a transformation of P₁ by R₂, we have a lattice polytope P₂ as in the right figure of Figure 5.7. Now, ignoring the isolated vertex, every possible rectangle of P₂ has intersection with a region with the rotation number zero. This implies that there is not a transformation of P by rectangles R1,…,Rk such that ∑ j=1k|Area(Rj)|=Area|P|, and the required result follows.

Figure 12. Example of a transformation of a lattice polytope P satisfying ∑j=1k|Area(Rj)|>Area|P|, where the vertices of Ver0(P) (respectively Ver1(P)) are indicated by black circles (respectively X marks), and the numbers in regions divided by ∂P denote the rotation numbers.

Corollary 5.12. There exist lattice presentations Δ, Δ' such that any transformation Δ→Δ′ satisfies ∑ j=1k(|Area(Rj)|+|Area(−Rj*)|)>12Area|P∪(−P*)|, where R1,…,Rk are used rectangles and P is a lattice polytope associated with Δ, Δ'. Thus, there exist lattice presentations Δ, Δ' such that the minimal area of transformations Δ→Δ′ is greater than 12Area|P∪(−P*)|.

Proof. Take lattice presentations Δ, Δ' presented by lattice polytopes P, -P^* such that P∩(−P*)=∅ and P is the lattice polytope given in Proposition 5.11. Then Δ, Δ' are the required presentations.

The transformation with minimal area Area|P| which we constructed in the proof of Theorem 5.9 is described by a transformation of P, but we have the following proposition.

Proposition 5.13. There exist lattice presentations of partial matchings Δ, Δ' and a transformation Δ→Δ′ by rectangles Rj∪(−Rj*) (j=1,…,k) such that ∑ j=1k|Area(Rj)|=Area|P| but R1=R(v,w) satisfies v∈Ver0(P) and w∈Ver0(−P*). Thus, there exists a transformation Δ→Δ′ with minimal area Area|P| which is not presented by a transformation of P. We have examples satisfying one of the following conditions.

• (1) The lattice polytope P is connected and simple. In this case, there is also a transformation Δ→Δ′ with minimal area which is presented by a transformation of P.

• (2) The lattice polytope P is connected but not simple. In this example, any transformation Δ→Δ′ with minimal area is not presented by a transformation of P.

Proof. Case (1). We consider lattice presentations with associated lattice polytopes as illustrated in Figure 5.8, where the shadowed polytope is P, and the vertices of Ver0(P∪(−P*)) (respectively Ver1(P∪(−P*))) are indicated by black circles (respectively X marks), and the numbers in regions divided by ∂(P∪(−P*)) denote the rotation numbers. Then, the transformation as shown in Figure 5.9 satisfies ∑j|Area(Rj)|=Area|P| but R₁=R(v,w) satisfies v∈Ver0(P) and w∈Ver0(−P*). The latter statement is obvious, and also follows from Theorem 5.9.

Figure 13. Example of lattice polytopes P∪(−P*) of Proposition Case (1), where the vertices of Ver0(P∪(−P*)) (respectivelyVer1(P∪(−P*))) are indicated by black circles (respectively X marks), and the numbers in regions divided by ∂P denote the rotation numbers.

Figure 14. Example of a transformation of lattice polytopes P∪(−P*) given by Figure 5.8, which has a minimal area but is not presented by a transformation of P, where the vertices of Ver0(P∪(−P*)) (respectively Ver1(P∪(−P*))) are indicated by black circles (respectively X marks).

Case (2). We consider lattice presentations with associated lattice polytopes as illustrated in Figure 5.8 and the transformation as shown in Figure 5.9 satisfies the required condition. The latter statement is obvious, since the minimal area of the lattice polytope P is the sum of the two areas sorrounded by ∂P by Theorem 5.9.

Corollary 5.14. Let Δ, Δ' be two lattice presentations of partial matchings. We consider a transformation Δ→Δ′ with minimal area. Then, if P and -P^* are disjoint and P satisfies the condition (1) or (2) of Theorem 5.9, then Δ→Δ′ is described by a transformation of P. Further, in this case, the transformations consist of those which, as chord diagrams, changes nesting arcs to crossing arcs and vice versa.

Proof. By Lemma 7.5 and the proof of Theorem 5.9, if P and -P^* are disjoint and P satisfies the condition 1 or 2 of Theorem 5.9, then Δ→Δ′ is described by a transformation of P.

Since P and -P^* are disjoint, any used rectangle R is disjoint with -R^*, and it follows from Proposition 3.3 that the two arcs of presented chord diagram are non-separated before and after the transformation, and hence we see that the transformation changes nesting arcs to crossing arcs and vice versa.

Let f(Δ,Δ′) (respectively f(P(Δ,Δ′))) be the number of transformations Δ→Δ′ with minimal area (respectively the number of transformations of P=P(Δ,Δ′) with minimal area). Note that by definition, f(Δ,Δ′)=f(P∪(−P*)).

By Lemma 7.5 and the existence of a transformation with minimal area by Theorem 5.9, we have the following corollary.

Corollary 5.15. If a lattice polytope P=P(Δ,Δ′) satisfies the condition (1) or (2) of Theorem 5.9, then the number of transformation with minimal area f(Δ, Δ') is equal to f(P). Further, by definition of equivalence, for equivalent lattice polytopes P and P', f(P)=f(P'). Thus, for pairs of lattice presentations Δ_i, Δ_i' (i=1,2) such that their lattice polytopes Pi=P(Δi,Δ i′) (i=1,2) satisfies that P_i and -P_i^* are disjoint and P_i satisfies the condition 1 or 2 of Theorem 5.9 (i=1,2), f(Δ1,Δ 1′)=f(Δ2,Δ 2′) if P₁ and P₂ are equivalent.