<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 1" %>
Cellular Structures Determined by Polygons and Trees
Satyan L. Devadoss1and Ronald C. Read2
1Department of Mathematics, Ohio State University, Columbus, Ohio
2Department of Combinatorics and Optimization, University of Waterloo, Canada
Annals of Combinatorics 5(1) p.71-98 March, 2001
AMS Subject Classification: 05A15, 52B11, 14H10
The polytope structure of the associahedron is decomposed into two categories, types and classes. The classification of types is related to integer partitions, whereas the classes present a new combinatorial problem. We solve this and incorporate the results into properties of the real moduli space of Riemann spheres. Connections are discussed with relation to classic combinatorial problems as well as to other sciences.
Keywords: associahedron, Riemann moduli space, polygon dissection, enumeration


1.  A. Barbrook et al., The phylogeny of the canterbury tales, Nature 394 (1998) 839.

2.  L.C. Biedenharn and J.D. Louck, The Racah-Wigner Algebra in Quantum Theory, Encyclopedia of Mathematics and Its Applications, Addison-Wesley Publishing, 1981.

3.  L.J. Billera, S.P. Holmes, and K. Vogtmann, Geometry of the space of phylogenetic trees, preprint, 2000.

4.  J.M. Boardman and R.M. Vogt, Homotopy Invariant Algebraic Structures on Topological Spaces, Lecture Notes in Mathematics 347, 1973.

5.  H.R. Brahana and A.M. Coble, Maps of twelve countries with five sides with a group of order 120 containing an Ikosahedral subgroup, Amer. J. Math. 48 (1926) 1每20.

6.  A. Cayley, On the partitions of a polygon, Proc. Lond. Math. Soc. 22 (1890-91) 237每262.

7.  L. Comtet, Advanced Combinatorics, D. Reidel Publishing, 1974.

8.  S.L. Devadoss, Tessellations of moduli spaces and the mosaic operad, Contemp. Math. 239 (1999) 91每114.

9.  L.R. Foulds and R.W. Robinson, Comparison of phylogenetic trees, Math. Biosci. 53 (1981) 131每147.

10.  L.R. Foulds and R.W. Robinson, Enumeration of phylogenetic trees without points of degree two, Ars Combin. 17A (1984) 169每183.

11.  V.A. Ginzburg and M.M. Kapranov, Kozul duality for operads, Duke Math. J. 76 (1994) 203每272.

12.  A. Grothendieck, Esquisse d'un programme, geometric Galois actions, I, Lond. Math. Soc. Lecture Notes 242 (1997) 5每48.

13.  I.P. Goulden and D.M. Jackson, Combinatorial Enumeration, John Wiley and Sons, 1983.

14.  F. Harary and E.M. Palmer, Graphical Enumeration, Academic Press, 1973.

15.  F. Harary and G. Prins, The number of homeomorphically irreducible trees, and other species, Acta Math. 101 (1959) 141每162.

16.  M.M. Kapranov, The permutoassociahedron, MacLane's coherence theorem, and asymptotic zones for the KZ equation, J. Pure Appl. Alg. 85 (1993) 119每142.

17.  C. Lee, The associahedron and triangulations of the n-gon, Europ. J. Combin. 10 (1989) 551每560.

18.  D. Mumford, J. Fogarty, and F. Kirwan, Geometric Invariant Theory, Third edition, Springer- Verlag, 1994.

19.  R. Otter, The number of trees, Acta Math. 49 (1948) 583 每 599.

20.  R.D.M. Page and E.C. Holmes, Molecular Evolution: A Phylogenetic Approach, Blackwell Science, 1998.

21.  G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937) 142每245.

22.  G. P車lya and R.C. Read, Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer-Verlag, 1987.

23.  J.H. Przytycki and A.S. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, preprint, 1998.

24.  R.C. Read, The use of S-functions in combinatorial analysis, Canad. J. Math. 20 (1968) 808 每 841.

25.  R.C. Read, On general dissections of a polygon, Aeq. Math. 18 (1978) 370 每 388.

26.  R.C. Read, A Survey of Graph Generation Techniques, Lecture Notes in Mathematics 884, 1981, pp. 77每89.

27.  R.C. Read, Enumeration, Graph Connections: Chapter 2, Oxford Science Publishing, 1997.

28.  R.C. Read and R.J. Wilson, An Atlas of Graphs, Oxford University Press, 1999.

29.  R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

30.  J.D. Stasheff, Homotopy associativity of H-spaces I, Trans. Amer. Math. Soc. 108 (1963) 275每292.