# Compression of Meanders

Authors: A. Panayotopoulos; P. Vlamos
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

This paper refers to the algorithmic transformation of a meander to its uniquely defined compression. We obtain this directly from meandric permutations, thus creating representations of large classes of meanders of different orders. We prove basic properties, give arithmetic results, and produce generating procedures.


---

## Body

## 1. Introduction

A closed meander of ordern is a closed self-avoiding curve crossing an infinite horizontal line 2n times [1]. In this paper, we obtain the compression as the determination of a unique simple meander, directly from its permutation. The meanders as planar permutations were introduced by Rosenstiehl [2] and they have been studied with nested sets [3, 4].More specifically, in Section2, we define the flow of a meander consisted by its traces and corresponding blocks. In Section 3, we create a specific form of meanders: the simple ones, we study the properties of their numbers of cuttings and cutting degree and we use them in order to introduce the compression. In Section 4, we determine the flow of the meandric permutations and we achieve also numerical results for the classification of the meanders of the compressions according to their order. Finally, in Section 5, we establish the compression of meanders directly from their meandric permutations divided in suitable blocks. Thus, we change their interpretation and produce a simplified procedure for generating the compressions.The following definitions and notation are necessary for the rest of the paper [3].A setS of disjoint pairs of [2n] such that ⋃{a,b}∈S‍{a,b}=[2n] and for any {a,b},{c,d}∈S we never have a<c<b<d is called nested set of pairs on [2n]. Each pair of a nested set consists of an odd and an even number. We denote the set of all nested sets of pairs on [2n] by N2n. Two nested sets S1,S2∈N2n define a permutation σ on [2n], such that σ(2i-1)=jiff{2i-1,j}∈S1 and σ(2i)=jiff{2i,j}∈S2, for every i∈[n]. The sets S1,S2 are k-matching if and only if σ has k cycles. In the case where k=1, S1,S2 are simply called matching. This definition is equivalent to the one given in [3].We callshort pair of S any pair of consecutive numbers that belongs to S, and outer pair of S any pair {a,b}∈S such that there is no pair {c,d}∈S with c<a<b<d. Each nested set of pairs contains at least one outer and one short pair.


## 2. Meanders

A meander of ordern is equivalently defined [3] as a cyclic permutation
(1)μ=μ(1)μ(2)⋯μ(2n)
on [2n], for which the following properties hold true: μ(1)=1, and the sets
(2)U={{μ(i),μ(i+1)}:i=1,3,…,2n-1},L={{μ(i),μ(i+1)}:i=2,4,…,2n}
are both nested and matching.We take all numbersmod2n. It is clear that μ(i) is odd if and only if i is odd. In the corresponding geometrical representation, the nested arcs correspond to nested pairs. A pair of nested sets U, L should be matching, in order to generate a meander. For example, the meander of Figure 1 is of order 14, with
(3)μ=12827231213262522211411817169101518192076232454,U={{1,28},{2,27},{3,12},{4,5},{6,7},{8,11},{9,10},{13,26},{14,21},{15,18},{16,17},{19,20},{22,25},{23,24}},L={{1,4},{2,3},{5,24},{6,23},{7,20},{8,17},{9,16},{10,15},{11,14},{12,13},{18,19},{21,22},{25,26},{27,28}}.Figure 1
A meander of order 14.The set of all the meanders of ordern is denoted by ℳ2n. Let μ∈ℳ2n be a meander crossing a horizontal line. Following [5], for any i∈[2n-1] we consider the vertical line, which shall be called the i-line, passing through the middle point of the segment (i,i+1) of the horizontal line. The numbers of those arcs of the meandric curve which are intersected by the i-line and lie above and beneath the horizontal line of μ, are called the numbers of cuttingsθ(i) and θ′(i), respectively [6].The sumε(i)=θ(i)+θ′(i) of the number of those arcs of the meandric curve which are intersected by the i-line is called the cutting degree of the meander at i. We notice that θ(i) and θ′(i) are of the same parity; hence, ε(i) is always even [5].The meandric curve always has points of intersection with thei-line, which we call traces. Obviously, the number of the traces is equal to ε(i). Starting below the horizontal line, we label the traces with the numbers 1,2,3,…,ε(i), knowing that θ(i) (resp., θ′(i)) of them are lying above (resp., beneath) the horizontal line. From now on, we will consider that the traces are identical to their corresponding labels. For the meander of Figure 1 and for i=14, we have θ(14)=4, θ′(14)=6, and ε(14)=10.Beginning from trace 1 and moving clockwise upon the meandric curve, following its “natural flow,” we obtain a shuffle of the permutation of the traces and the meandric permutation, see Figure2 where the circled elements are the traces.Figure 2In the general case, we have the shuffle(4)ti=τi(1)B1iτi(2)B2i⋯τi(ε(i))Bε(i)i
with τi(1)=1,τi(2),…,τi(ε(i)) being the traces of the meander at i and B1i,B2i,…,Bε(i)i the parts of consecutive elements of the meandric permutation μ, lying between consecutive traces, called blocks of the meander; that is, the block Bki, k∈[ε(i)], is the set of the consecutive elements of the permutation μ, which are lying between the traces τi(k) and τi(k+1). These two traces are called the “entrance” trace and the “exit” trace of the block, respectively, while the shuffle ti is called flow of the meander from the trace (1) of the i-line, or for simplicity i-flow.For everyk∈[ε(i)], τi(k)Bkiτi(k+1) corresponds to the part of the meandric curve starting from the trace τi(k) and ending at the trace τi(k+1), which we denote by cki. If k is odd (resp., even), then this curve lies on the left (resp., right) of the i-line. In Figure 1, we denote the curve cki by (k).


## 3. Simple Meanders and Compression

Letμ∈ℳ2n and its flow ti=τi(1)B1iτi(2)B2i⋯τi(ε(i))Bε(i)i. To each block Bki, k∈[ε(i)], we correspond a number bki such that
(5)bki={1,if|Bki|isodd,2,if|Bki|iseven.The setB(i)={B1i,B1i,…,Bε(i)i} can be partitioned into three classes B1(i), B2(i), and B2′(i), where the set B1(i) consists of the blocks Bki with bki=1 and the set B2(i) consists of the blocks Bki with bki=2 and θ′(i)<τi(k),τi(k+1), while the set B2′(i) consists of the blocks Bki with bki=2 and τi(k),τi(k+1)<θ′(i).A meanderμ∈ℳ2n is called simple at i (i.e., simple referring to the i-line) if |Bki|≤2, k∈[ε(i)]. Hence, every block of the sets B1(i) (resp., B2(i), B2′(i)) has exactly one element (resp., two elements). We notice that the following necessary and sufficient condition holds true.A meander is simple ati if and only if every triple of consecutive terms of its permutation contains elements from both of the sets {1,2,…,i} and {i+1,i+2,…,2n}.For example, the meander of Figure3 is simple at i=8.Figure 3
A meander of order 9, simple ati=8.We note that a meander can be simple at more than one point. For example, the meanderμ=143256 is simple at i=2 and i=3.Letμ∈ℳ2n be a meander that is not simple at n. Further on, we will study every meander according to its n-line, so for simplicity we omit the index n from the notation. Let B(n)={B1,B2,…,B2ν} be its already defined set of blocks, where 2ν=ε(n) and the blocks Bk, for k∈I1={1,3,…,2ν-1} (resp., k∈I2={2,4,…,2ν}), are the ones placed at the left (resp., right) of the n-line. Each block Bk∈B(n) lies between the trace τ(k) and the trace τ(k+1) of the flow t.We denote byγk, k∈[2ν], the closed interval of [2ν] with ends the traces τ(k), τ(k+1). Given a pair of blocks Bk,Bλ∈B(n), k,λ∈I1 or k,λ∈I2, with γλ⊂γk, then the block Bλ is called internal of the block Bk, and the block Bk is called external to the block Bλ. We can easily deduce that the number of the internal blocks of a block Bk∈B(n) is equal to (1/2)(|τ(k)-τ(k+1)|-1).If we replace the blocksBk, k∈[2ν], of the meander μ by blocks having one element (resp., two elements) whenever bk=1 (resp., bk=2), then we obtain a meander μ¯ of order n¯=(1/2)∑k∈[2ν]bk (since its blocks have one or two elements, corresponding to crossing points with the horizontal line) and simple at u=∑k∈I1bk (counting the points of intersection with the horizontal line to the left of the n-line).The result of the above replacement is the set of blocksB¯(u)={B¯1,B¯2,…,B¯2ν}, where B¯k=B¯ku for simplicity. The set B¯(u) is partitioned into the classes B¯1(u), B¯2(u), and B¯2′(u) corresponding to the classes B1(n), B2(n), and B2′(n) of the set B(n).When we put a dash upon any existing notation, we refer to the elements of the deduced simple meanderμ¯. We easily obtain that(i)
u, n are of the same parity,(ii)
ε¯(u)=2ν, θ¯(u)=θ(n), θ¯′(u)=θ′(n), b¯k=bk,(iii)
ifBk∈B2(n) (resp. Bk∈B2′(n)) and |τ(k)-τ(k+1)|=1, then its corresponding block B¯k∈B¯2(u) (resp., B¯k∈B¯2′(u)) contains one short pair of L¯ (resp., U¯). If Bk∈B1(n), then its corresponding block B¯k∈B¯1(u) is the pair {τ(k), τ(k+1)}.The pair(μ¯,u) is called central compression or simply compression of the meander μ. The simple at u meander μ¯ has as same invariants with the meander μ the traces and the flow of curves. For example, the compression of the meander μ of Figure 1 is the pair (μ¯,u), where μ¯ is the meander of Figure 3 and u=1+2+2+1+2=8.


## 4. The Flowt

The traces and the blocks of the flowt of a meander μ can be found from its permutation with the help of the subsets U(n)⊆U and L(n)⊆L, containing the pairs {μ(i),μ(i+1)} satisfying the relation
(6)min{μ(i),μ(i+1)}≤n<max{μ(i),μ(i+1)}.These pairs have one element belonging to the set{1,2,…,n} and the other belonging to the set {n+1,n+2,…,2n}, with |U(n)|=θ(n) and |L(n)|=θ′(n).According to the absolute value|μ(i)-μ(i+1)|, we place the elements of L(n) in decreasing order, while of U(n) in increasing order. If U(n),L(n)≠∅, then we correspond the numbers θ′(n)+1,…,2ν-1,2ν to the ordered pairs of U(n), and the numbers 1,2,…,θ′(n) to the ordered pairs of L(n). If L(n)=∅ (resp., U(n)=∅), then we correspond to the ordered pairs of U(n) (resp., L(n)) the numbers 1,2,…,2ν. It is obvious that the previous numbers coincide with their corresponding traces.In order to start then-flow t from the first trace, we choose the pair {μ(z),μ(z+1)} which corresponds to the trace τ(1)=1. If L(n)≠∅, then this pair is the outer pair of L(n) with μ(z+1) odd and less than μ(z). If L(n)=∅, then this is the pair of U(n) with the smallest value of |μ(i)-μ(i+1)|.For example, for the meander of Figure1, we have that
(7)U(14)={{1,28},{2,27},{13,26},{14,21}},L(14)={{5,24},{6,23},{7,20},{8,17},{9,16},{10,15}}.
Hence, we choose the pair {5,24} of L(14) to correspond to the trace τ(1)=1.Since the permutationμ is cyclic, we do not change the notation, that is,
(8)μ=μ(z+1)⋯μ(1)μ(2)⋯μ(z),
which also defines a partition of [2n] with classes including its consecutive elements, which belong, respectively, to the sets {1,2,…,n} and {n+1,n+2,…,2n}. This partition gives the 2ν classes of the set B(n)={B1,B2,…,B2ν}.Practically, at first we partition the permutation of the meander into classes including the consecutive terms ofμ, which are less or equal to (resp., greater than) n. Thus, we have the partition of μ into blocks, putting at the beginning the last remaining elements and marking the traces.For example, for the meander of Figure1 we have Figure 4.Figure 4The placement of the traces follows the change of parity of the elements of the permutation, if we have an odd (resp., even) element followed by an even (resp., odd) element, then their intermediate trace is lying above (resp., beneath) the horizontal line. From the above partition, we obtain the flow: see Figure2.The meanders of the compression of the setℳ2n are partitioned into classes, with elements belonging to the sets ℳ2,ℳ4,…,ℳ2n.In the methods of generating planar permutations [7], we can also include the way to find the blocks of meanders, their corresponding numbers bk, and consequently the orders of the meanders of their compressions.These meanders can be used as generators for the reverse problem of ‘‘decompression.’’ We can use them to extend a meanderμ¯∈ℳ2n¯ simple at u to all possible meanders μ∈ℳ2n, with n>n¯.Table1 presents the cardinalities of those classes for n=2,3,…,10, without taking into account the corresponding u-line.Table 1
The partition of the setℳ2n into the classes ℳ2n-.
2
n
∖
2
n
-
2
4
6
8
10
12
14
16
18
20
Total
4
0
2
2
6
4
0
4
8
8
0
18
16
8
42
10
64
0
144
24
30
262
12
0
392
616
480
268
72
1828
14
1764
0
6084
1760
3218
712
282
13820
16
0
13122
28000
27412
25040
12340
4220
820
110954
18
68644
0
304704
115200
261380
99664
66224
14512
3130
933458
20
0
578888
1491968
1684384
1980960
1315572
737944
284028
68892
10224
8152860The zeros of the first (resp., second) column verify the fact that if the ordern of the meander is even (resp., odd), then there do not exist meanders of order n with compression of order 1 (resp., 2). We can easily prove that the values of the first column express that there exist |ℳ(n+1)/2|2 meanders of order n with compression of order 1. For meanders of larger order, we should try to calculate the number of different blocks of given orders.


## 5. Determining the Compression

We shall find the compression of a meanderμ with the help of its n-flow t¯=τ(1)B¯1τ(2)B¯2⋯τ(2ν)B¯2ν. We recall that each block B¯k∈B¯(u) consists of one or two elements. Obviously, the elements of B¯k belong to the sets {1,2,…,u} (resp., {u+1,u+2,…,2n¯}), when k∈I1 (resp., k∈I2). The relative position of these points defines a relation of preceding for the blocks of the set B¯(u); hence, the block B¯p precedes the block B¯q (B¯p≺B¯q), iff minB¯p<minB¯q.This relation is defined by the following conditions.(a)
IfBp∈B1(n), Bq∈B(n), with γq⊂γp and p,q∈I1 (resp., p,q∈I2), then B¯p≺B¯q (resp., B¯q≺B¯p), since the block B¯q is internal of the block B¯p.(b)
IfBp∈B2(n)∪B2′(n), Bq∈B1(n), with γq∩γp=∅ and p,q∈I1 (resp., p,q∈I2), then B¯p≺B¯q (resp., B¯q≺B¯p), since this is imposed by the nature of the meander.(c)
IfBp,Bq∈B2(n)∪B2′(n), with γq⊂γp and p,q∈I1 or p,q∈I2, then B¯p≺B¯q, since the block B¯q is internal of the block B¯p.(d)
IfBp,Bq∈B2(n), with γq∩γp=∅, minγq<minγp and p,q∈I1 (resp., p,q∈I2), then B¯p≺B¯q (resp., B¯q≺B¯p), since this is imposed by the nature of the meander. The case where Bp,Bq∈B2′(n) is similar.Obviously, the above results do not cover the cases of two blocks, the one belonging to the setB2(n), and the other to the set B2′(n), where none of them is internal to the other. In order to obtain a unique solution, we have to make the following choice.(e)
IfBp∈B2(n), Bq∈B2′(n), with minB~p<minB~q and p,q∈I1 or p,q∈I2, then B¯p≺B¯q (resp., B¯q≺B¯p), where B~k=bk1bkω, bk1 is the first element of Bk, bkω is the last element of Bk and ω=|Bk|.From the above conditions (a)–(e), we obtain an ordering for the blocks of the setB¯(u), concerning their relation of preceding, that is, B¯r(1),B¯r(2),…,B¯r(2ν).For example, applying the above conditions for the meander of Figure1, we obtain that B¯1≺B¯3≺B¯9≺B¯5≺B¯7 and B¯8≺B¯6≺B¯4≺B¯10≺B¯2. Indeed, B¯1≺B¯3,B¯5,B¯7,B¯9 due to the condition (a), B¯3≺B¯5 due to the condition (b), B¯3≺B¯9 due to the condition (e), B¯5≺B¯7 due to the condition (a), and finally B¯9≺B¯5 due to the condition (b). Similarly, we obtain the ordering for the rest of the blocks. Hence, r=13957864102.In the general case, the ordering is deduced from a Hamiltonian path of the directed graphs with vertices the elements of the setI1 (resp., I2) and arcs the pairs (p,q)∈I12 (resp., (p,q)∈I22) such that B¯p≺B¯q.We note thatB¯p≺B¯q iff r-1(p)<r-1(q), given that r-1(k) defines the position of the block B¯k at the total order of B¯(u). For our example, we have that r-1=11028475629.Practically, the whole procedure of finding the compression can be presented in a table, where the second row refers to the flowt, which includes all the elements necessary for the conditions (a)–(e), while from their application we deduce in the third row the total order of the set B¯(u). The last row refers to the flow t¯ by assigning the numbers of the set [2n¯] to their corresponding blocks of B¯(u), according to the following remarks for the blocks B¯k=b¯k1b¯k2.(i)
Their elements have the same ordering (ascending or descending) with those ofBk.(ii)
When their elements are not consecutive, then|b¯k1-b¯k2|=|τ(k)-τ(k+1)|.For example, for the meander of Figure1, we have Figure 5. Hence, μ¯=11817231615611107891254 13 14, with u=1+2+2+1+2=8.Figure 5


## 6. Conclusions

We have introduced the compression of a meander, directly with the use of blocks of its permutation. The uniqueness of the compression is established by the ordering of the blocks, which is deduced according to its flow.Various open questions can arise by the above meanders, when they are used as representatives of large classes of meanders as shown in Table1. Yet, the main open problem is the reverse procedure of compression. The decompression of a meander to others of larger order having the same traces, number of cuttings, and flow seems to be the final step for integrating the procedures of cutting and compressing meanders, and in parallel being very promising for enumeration results and applications in physical phenomena.



---

*Source: 851751-2013-01-08.xml*