Meanders

This article is under construction.            

Please do not rely on any information it contains.            

This is a draft of an article about meanders written by DF, BJ, DM, DS and JW. If you are not on this list, please contact us before editing this page.

Introduction

This article is about meanders in the sense of Jon Wild (defined below) and some of its generalizations. The number of meanders on a square grid of side $\scriptstyle n\,$ (up to symmetry) was seen to be important enough that it was chosen to be A200000, the 200000^th sequence of the OEIS.

Brief summary

Article abstract.

Brief history

Brief history of (this kind of) meanders.

Other definitions for meanders

Arnold meanders

(TODO: briefly describe)

Arnold meanders: A005315, A005316 and links therein.

Wienand meanders

(TODO: briefly describe)

Wienand meanders: A199932 and links therein, as described by Peter Luschny. (http://oeis.org/wiki/User:Peter_Luschny/Meander)

Acknowledgements

Several persons will go here!

Definitions of meanders

(...)

As equivalence classes of closed loops

Elementary level: consider a rectangular $\scriptstyle n\times k\,$ grid, $\scriptstyle k\,\leq \,n\,$, made of square tiles (chessboard). DESCRIBE the loops

Here is an example of a meander on a 5-by-3 grid:

A meander on a (5,3)-grid

IDs	Image
S, H, W, E, W, V, S, A, N, V, E, W, E, H, N, (2 orientations)

General definition: the natural framework seems to be that of a CW-complex. Given a CW-complex of dimension $\scriptstyle d\,$, we consider the closed simple loops intersecting at least once every open $\scriptstyle d\,$-cell, intersecting at most once every open $\scriptstyle (d-1)\,$-cell, and intersecting no closed $\scriptstyle (d-2)\,$-cell. In the two-dimensional case, these cells are respectively the faces, edges and vertices. Homotopy through loops of this type is an equivalence relation. A meander is an equivalence class for this relation, but by abuse of language, we will also call meander a representant of such a class.

Here is an example of a meander on an irregular CW-complex:

PICTURE [preferably, with irregular triangular, quadrilateral and pentagonal tiles]
A meander on a 2-dimensional CW-complex

As tilings

describe the possible tiles

Square tiles

tile	abbrev.	tile	abbrev.
	N		H
	E		V
	S		A
	W		B

As a mnemonic, N, E, S, W stand for North, East, South, West (slightly tilt your head to the left) and H and V stand for horizontal and vertical.

Besides these eight square tiles, there is one additional tile, which, since meanders are closed loops (that is, are connected), can appear only on a one-by-one grid.

Square tiles (continued)

tile	abbrev.
	O

Equivalence of the two definitions

(...)

Relation with Hamiltonian cycles

We define the dual graph of a $\scriptstyle d\,$-dimensional CW-complex as the graph with vertices corresponding to the $\scriptstyle d\,$-cells and with an edge between two vertices if the corresponding $\scriptstyle d\,$-cells meet in a $\scriptstyle (d-1)\,$-cell. Then a Hamiltonian cycle of that graph gives a meander of the original CW-complex in an obvious way. Similarly, Hamiltonian paths give open meanders. The converse is in general wrong, as the above example of a meander on a (5,3)-grid shows. We will see below that meanders have much more "flexibility".

Actually, Hamiltonian cycles correspond to the meanders that intersect each $d$-cell on a connected set. For instance, for tilings by squares, this amounts to forbidding tiles of type A or B.

Is there a one-by-one meander?

Is there a meander on a single tile, or in terms of a CW-complex, a meander on a single $\scriptstyle d\,$-cell? This question becomes more important in the case of multimeanders.

In the CW-complex definition, there is no obstruction to a meander on a single $\scriptstyle d\,$-cell.

Not yet settled.

Meanders up to symmetry

When the grid or CW-complex has certain symmetries, we will also study the set of "meanders up to symmetry". For instance, the symmetries of a square grid form the dihedral group D₄ with 8 elements, and the symmetries that preserve orientation form the cyclic group C₄ of order 4, which sits as a subgroup of index 2 of D₄. For rectangular grids, and other grids, we will consider the relevant symmetry groups and the corresponding "meanders up to symmetry", that is, the equivalence classes (or orbits) of meanders under the action of the given symmetry group.

Generalizations

Self-crossing meanders

The other generalization is to allow self-crossings. In terms of loops: we consider all closed loops, and not only the simple ones. Equivalently, we consider immersions of the circle, and not only embeddings. In terms of tilings this amounts to allowing one new tile,

Additional square tile for self-crossing meanders

tile	abbrev.
	X

We can also distinguish between over- and under-crossing, adding the two tiles

Additional square tiles for self-crossing meanders with over/under-crossing distinction

tile	abbrev.
	C
	D

Multimeanders

There are two natural generalizations of meanders. The first is to drop the connectedness requirement. We call "not necessarily connected meanders" multimeanders.

In the CW-complex definition, one has to impose that if a given closed $\scriptstyle d\,$-cell contains a connected component of a multimeander, then it does not intersect any other connected component of that multimeander. Or we can more drastically forbid that any closed $\scriptstyle d\,$-cell contain a connected component of a multimeander.

We will see below that multimeanders are much simpler to compute. This is because, using the tiling definition, there are only local conditions to check (that adjacent tiles match), whereas connectedness is a global condition (except on some small grids), and is therefore much harder to check.

Both generalizations at once

Finally, we can obviously consider these two generalizations at once, leading to either multi self-crossing meanders, mutually-crossing multimeanders or mutually-crossing self-crossing multimeanders.

Multi self-crossing meanders

This is the case where disconnected meanders are not allowed to cross each other, but each meander is allowed to be self-crossing.

Mutually-crossing multimeanders

This is the case where disconnected meanders are allowed to cross each other, but each meander is not allowed to be self-crossing.

Mutually-crossing self-crossing multimeanders

This is the case where both disconnected meanders are allowed to cross each other and each meander is allowed to be self-crossing.

Multimeanders on rectangular grids

Although meanders are the main objects of interest, we begin with multimeanders, which are easier to count. We denote by $TT(n,k)$ the number of multimeanders on an $(n,k)$-grid.

We give a construction to find $TT(n,k)$ using a double induction (corresponding to the two dimensions of the grid). The idea is to first find a linear recurrence relation on $n$ given by a matrix $A_{k}$, and then to construct the matrices $A_{k}$ using another induction.

The first step is as follows....

For the second step...

Recurrence relations

relation	tile	relation	tile
A(0i,0j) = 0	(empty)	B(0i,0j) = B(i,j)
A(0i,1j) = B(i,j)		B(0i,1j) = A(i,j),
A(1i,0j) = B(i,j)		B(1i,0j) = A(i,j),
A(1i,1j) = A(i,j)		B(1i,1j) = 2 B(i,j)	&

[HOW to have both tiles on the same row in the last cell?]

So, in summary:

Define two symmetric functions A and B on couples of words on {0,1} of same length by induction on that length, as follows:

$A(\varnothing ,\varnothing )=1,B(\varnothing ,\varnothing )=0$

$A(0i,0j)=0,A(0i,1j)=B(i,j),A(1i,1j)=A(i,j)$

$B(0i,0j)=B(i,j),B(0i,1j)=A(i,j),B(1i,1j)=2B(i,j)$

Let A_k be the matrix whose rows and columns are labelled by the words of size k with an even number of 1's (in any order, say lexicographic order). Then the number of multimeanders on an (n,k)-grid is given by TT(n,k) = [(A_k)^n]_{0,0} the (0,0)-entry of the n-th power of A_k.

Remark: the matrix A has size 2^(k-1) if k>0 and 1 if k=0.

Examples:

For A and B, the first step gives A(0,0) = A(0,1) = 0 ; A(1,1) = 1 ; B(0,0) = B(1,1) = 0 ; B(0,1) = 1.

The first few matrices A_k are

A_0 = (1) gives the empty multimeander on the empty grid

A_1 = (0) proves that TT(1,k)=0 (including on the (1,1)-grid, which is normal since I used the definition without the special tile)

A_2 = (0,1;1,1) so the TT(2,k) are the Fibonacci numbers (shifted by one)

A_3 = (0,0,1,0;0,0,1,2;1,1,0,1;0,2,1,0)

Explanation:

A(i,j) is the number of open multimeanders on an (n,1)-grid (where n is the common length of i and j), with "ends" on the left/right edge given by the words i/j; and similarly for B with in addition one end on the "top" edge.

A(empty,empty) = 1: the empty tiling

B(empty,empty) = 0: one cannot have one end and be empty

Multimeanders with crossings

When crossings are allowed, then the above is still valid with the only modification of B(1i,1j) = 2 B(i,j) into B(1i,1j) = 3 B(i,j). Indeed, as seen in the above table, the coefficient 2 accounts for the tiles A and B when no crossing is allowed, and the coefficient 3 accounts for the tiles A, B and X when crossings are allowed.

Recurrence relations

relation	tile
B(1i,1j) = 3 B(i,j)	& &

[HOW to have both tiles on the same row in the last cell?]

Meanders on rectangular grids

Meanders on rectangular grids

The number of meanders on an $\scriptstyle (n,k)\,$-grid, $\scriptstyle k\,\leq \,n\,$, is given by A201145. We denote it by $\scriptstyle T(n,k)\,$. Obviously, $\scriptstyle T(n,k)\,=\,T(k,n)\,$ since there is a one-to-one correspondence (90 o rotation) between each element of the two sets of meanders. The meanders for $\scriptstyle T(n,k)\,$ or $\scriptstyle T(k,n)\,$ for $\scriptstyle k\,\leq \,2\,$ are trivial, where $\scriptstyle T(1,k)\,=\,T(n,1)\,=\,0^{\{(n-1)+(k-1)\}}\,$ and $\scriptstyle T(2,k)\,=\,T(n,2)\,=\,1.\,$

Number of meanders $\scriptstyle T(n,k)\,$ on an $\scriptstyle (n,k)\,$-grid

$\scriptstyle n\backslash k\,$	1	2	3	4	5	6	7	8	9
1	1	0	0	0	0	0	0	0	0
2	0	1	1	1	1	1	1	1	1
3	0	1	0	2	2	6	10	22	42
4	0	1	2	11	42	199	858	3881	17156
5	0	1	2	42	320	3278	29904	285124	2671052
6	0	1	6	199	3278	71648	1369736	?	?
7	0	1	10	858	29904	1369736	55717584	?	?
8	0	1	22	3881	285124	?	?	?	?
9	0	1	42	17156	2671052	?	?	?	?

(for further values, see ... [the page/b-file dedicated to that sequence, or an appendix; but no need to put too many terms here, IMHO, we might even stop at 7] )

Meanders on rectangular grids (up to symmetry)

(...)

Proof for S(n,3)

(...)

Meanders on rectangular grids (up to oriented symmetry)

(...)

Proof for T(n,3)

(...)

Self-crossing meanders on rectangular grids

(...)

Multimeanders on rectangular grids

(...)

Self-crossing multimeanders on rectangular grids

(...)

Square grids (quadriangulated)

Meanders on square grids

The main diagonal (highlighted) of meanders on rectangular grids (shown above).

It would be nice to know the asymptotic behavior...

Self-crossing meanders on square grids

(...)

Multimeanders on square grids

(...)

Self-crossing multimeanders on square grids

(...)

Rectangular grids with sides identified (quadriangulated)

Meanders on rectangular grids with sides identified

(...)

Self-crossing meanders on rectangular grids with sides identified

(...)

Multimeanders on rectangular grids with sides identified

(...)

Self-crossing multimeanders on rectangular grids with sides identified

(...)

Projective planes (triangulated)

Meanders on projective planes

(...)

Self-crossing meanders on projective planes

(...)

Multimeanders on projective planes

(...)

Self-crossing multimeanders on projective planes

(...)

Triangular grids (triangulated)

Meanders on triangular grids

DESCRIBE: triangular tiles (six kinds, two kinds up to rotation) (pictures...)

(...)

Self-crossing meanders on triangular grids

(...)

Multimeanders on triangular grids

(...)

Self-crossing multimeanders on triangular grids

(...)

Hexagonal grids (triangulated)

Meanders on hexagonal grids

DESCRIBE: hexagonal tiles (1 (x 3) + 1 (x 3) + 1 (x 6) + 1 (x 6) + 1 (x 2), 5 kinds up to rotation) (is that right?...) (pictures...)

(...)

Self-crossing meanders on hexagonal grids

(...)

Multimeanders on hexagonal grids

(...)

Self-crossing multimeanders on hexagonal grids

(...)

Surfaces in 3-space

Surface of polyhedra

Meanders on the surface of polyhedra

We begin with/restrict to the simpler case: the surfaces of the five Platonic solids (i.e. convex regular polyhedra), with one tile per face.

DESCRIBE: triangular tiles (one kind up to rotation: picture) and pentagonal tiles (four kinds up to symmetry: pictures)

VISUALIZATION: show the nets.

Meanders on the surface of tetrahedrons

Triangular tiles. One meander up to symmetry, and three total. Actually, there are no other multimeanders.

Meanders on the surface of hexahedrons (cubes)

Square tiles. (...)

Meanders on the surface of octahedrons

Triangular tiles. (...)

Meanders on the surface of dodecaedrons

Pentagonal tiles. (...)

Meanders on the surface of icosahedrons

Triangular tiles. (...)

Self-crossing meanders on the surface of polyhedra

(...)

Multimeanders on the surface of polyhedra

(...)

Self-crossing multimeanders on the surface of polyhedra

(...)

Spheres (triangulated)

Meanders on spheres

(...)

Self-crossing meanders on spheres

(...)

Multimeanders on spheres

(...)

Self-crossing multimeanders on spheres

(...)

Cylinders (quadriangulated)

Meanders on cylinders

(...)

Self-crossing meanders on cylinders

(...)

Multimeanders on cylinders

(...)

Self-crossing multimeanders on cylinders

(...)

Möbius bands (quadriangulated)

Meanders on Möbius bands

(...)

Self-crossing meanders on Möbius bands

(...)

Multimeanders on Möbius bands

(...)

Self-crossing multimeanders on Möbius bands

(...)

Tori (quadriangulated)

Meanders on tori

(...)

Self-crossing meanders on tori

(...)

Multimeanders on tori

(...)

Self-crossing multimeanders on tori

(...)

Surfaces in 4-space

Klein bottles (quadriangulated)

Meanders on Klein bottles

(...)

Self-crossing meanders on Klein bottles

(...)

Multimeanders on Klein bottles

(...)

Self-crossing multimeanders on Klein bottles

(...)

...

(...)

Description of the algorithms used

(...)

...

(...)

See also

• Meanders

• Meanders filling out an n-by-k grid (reduced for symmetry)
  • Number of meanders filling out an n-by-k grid (reduced for symmetry)
• Meanders filling out an n-by-n grid (reduced for symmetry)
  • Number of meanders filling out an n-by-n grid (reduced for symmetry)

• Meanders filling out an n-by-k grid (not reduced for symmetry)
  • Number of meanders filling out an n-by-k grid (not reduced for symmetry)
• Meanders filling out an n-by-n grid (not reduced for symmetry)
  • Number of meanders filling out an n-by-n grid (not reduced for symmetry)

• Self-crossing meanders filling out an n-by-k grid (reduced for symmetry)
  • Number of self-crossing meanders filling out an n-by-k grid (reduced for symmetry)
• Self-crossing meanders filling out an n-by-n grid (reduced for symmetry)
  • Number of self-crossing meanders filling out an n-by-n grid (reduced for symmetry)

• Self-crossing meanders filling out an n-by-k grid (not reduced for symmetry)
  • Number of self-crossing meanders filling out an n-by-k grid (not reduced for symmetry)
• Self-crossing meanders filling out an n-by-n grid (not reduced for symmetry)
  • Number of self-crossing meanders filling out an n-by-n grid (not reduced for symmetry)

• {{Meander}} graphic template

• Self-avoiding walks#Hamiltonian lattice walks (especially Hamiltonian lattice cycles)