Annals of Combinatorics 2 (1998) 7-18
A Partial Order for the Set of Meanders
Reinhard O. W. Franz
Department of Mathematics,
Brigham Young University, Provo, UT 84602, USA
Received November 18, 1997
AMS Subject Classification: 05A15, 05A18; 06A07, 06A08
Abstract. In this paper, we present a new approach for studying meanders in terms of non-crossing partitions. We show how this approach leads to a natural partial order on the set of meanders. In particular, meanders form a graded poset with regard to this partial order.
Keywords: meanders, noncrossing partitions, partitions
1. M. Aigner, Combinatorial Theory, Springer-Verlag, Berlin, 1979.
2. V. Arnol’d, The branched covering of CP2 → S4, hyperbolicity and projective topology, Siberian Math. J. 29 (1988) 717–726.
3. C. Berge, Principles of Combinatorics, Academic Press, New York, London, 1971.
4. A. Björner, Shellable and Cohen-Macauly Partially Ordered Sets, Trans. Amer. Math. Soc. 260 (1980) 159–183.
5. N. Dershowitz, Ordered Trees and Non-Crossing Partitions, Discrete Math. 62 (1986) 215–218.
6. P. Di Francesco, O. Golinelli, and E. Guitter, Meanders: a direct enumeration approach, Nuclear Physics B 482 (1996) 497–535.
7. R. Franz, On the representation of meanders, preprint, 1997.
8. R. Franz, Meanders on surfaces, preprint, 1997.
9. R. Franz, On the structure of the partially ordered set of meanders, preprint, 1998.
10. R. Franz, A constructive enumeration algorithm for meanders, preprint, 1998.
11. R. Franz, Counting meanders, preprint, 1998.
12. K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R. Tarjan, Sorting Jordan sequences in linear time using level-linked search trees, Inform. and Control 68 (1986) 170–184.
13. G. Kreweras, Sur les partitions noncroisées d’un cycle, Discrete Math. 1 (1972) 333–350.
14. K.H. Ko and A. Smolinksky, A combinatorial matrix in 3-manifold theory, Pacific. J. Math. 149 (1991) 319–336.
15. S.K. Lando and A.K. Zvonkin, Meanders, Selected translations, Selecta Math. Soviet. 11 (1992) 117–144.
16. S.K. Lando and A.K. Zvonkin, Plane and projective meanders, Theoret. Comput. Sci. 117 (1993) 227–241.
17. R. Simion and D. Ullman, On the structure of the lattice of noncrossing partitions, Discrete Math. 98 (1991) 193–206.
18. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth, Belmont, CA, 1986.
19. R.P. Stanley, Parking functions and noncrossing partitions, The Wilf Festschrift, Electron. J. Combin. 4 (1997), no.2.