Enumeration of multi-colored rooted maps

We present a study of n-colored rooted maps in orientable and locally orientable surfaces. As far as we know, no work on these maps has yet been published. We give a system of n functional equations satisfied by n-colored orientable rooted maps regardless of genus and with respect to edges and vertices. We exhibit the solution of this system as a vector where each component has a continued fraction form and we deduce a new equation generalizing the Dyck equation for rooted planar trees. Similar results are shown for n-colored rooted maps in locally orientable surfaces.     

Enumeration of order preserving maps

Three results are obtained concerning the number of order preserving maps of an n-element partially ordered set to itself. We show that any such ordered set has at least 2 ^2n/3 order preserving maps (and 2 ² in the case of length one). Precise asymptotic estimates for the numbers of self-maps of crowns and fences are also obtained. In addition, lower bounds for many other infinite families are found and several precise problems are formulated.Supported by ONR Contract N00014-85-K-0769.Supported by NSF Grant DMS-9011850.Supported by NSERC Grants 69-3378 and 69-0259.     

Enumeration of rooted nonseparable outerplanar maps

In this paper, the number of combinatorially distinct rooted nonseparable outerplanar maps withm edges and the valency of the root-face being n is found to be(m-1)! (m-2) !:(n-1)!(n-2)! (m-n)!(m-n 1)!and, the number of rooted nonseparable outerplanar maps with m edges is also determined to be(2m-2)!:(m-1)!m!,which is just the number of distinct rooted plane trees with m-1 edges.     

Enumeration of rooted planar halin maps

A Halin map is a kind of planar maps oriented by a tree. In this paper the rooted halin maps with the vertex partition as parameters are enumerated such that a famous result on rooted trees due to Harary. Prins, and Tutte is deduced as. a special ease. Further, by using Lagrangian inversion to obtain a number of summation free formulae dixectly, the various kinds of rooted Halin maps with up to three parameters have been counted.     

Counting rooted maps by genus III: Nonseparable maps

A map on an orientable surface is called separable if its underlying graph can be disconnected by splitting a vertex into two pieces, each containing a positive number of edge-ends consecutively ordered with respect to counter-clockwise rotation around the original vertex. This definition is shown to be equivalent for planar maps to Tutte's definition of a separable planar map. We develop a procedure for determining the generating functions N_g,b(x) = Σ_p=0^∞n_g,b,px^p, where n_g,b,p is the number of rooted nonseparable maps with b + p edges and p + 1 vertices on an orientable surface of genus g. Similar results are found for tree-rooted maps.     

Enumeration of maps on the projective plane

1. IntroductionA lnap is rooted if an edge is distinguished togetl1er with an end and a side of the edge.An edge belo11ging to only one face is called double (or 8ingular by some author), al1 othersbelonging to exactly two faces are called s1ngle. The enumeration of rooted p1anar maps wasfirst introduced by Tutte['], Techniques originated by Tutte [2,3l for enumerating variousclasses of rooted Inaps on tIle sphere are here applied to the c1asses of alI rooted maps onthe projective plane. Th…     

Enumeration of platonic maps on the torus

Certain maps (graph embeddings) on the torus are counted, namely those with all faces triangles, respectively quadrilaterals, resp. hexagons, and all vertices having the same degree (which then must be 6, 4 or 3, resp.). These are the toroidal analogues of the spherical maps corresponding to the five Platonic solids. Techniques from combinatorics and number theory are applied to obtain the results.     

Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

Geometric realization of Adams maps

Let G/P be a homogenous space with G a compact connected Lie group and P a connected subgroup of G of equal rank. As the rational cohomology ring of G/P is concentrated in even dimensions, for an integer k we can define the Adams map of type k to be l _k : H*(G/P, ℚ) → H*(G/P, ℚ), l _k (u) = k ⁱ u, u ∈ H ²ⁱ (G/P, ℚ). We show that if k is prime to the order of the Weyl group of G, then l _k can be induced by a self map of G/P. We also obtain results which imply the condition that k is prime to the order of the Weyl group of G is necessary.     

Enumeration of loopless maps on the projective plane

In this paper we study the rooted loopless maps on the sphere and the projective plane with the valency of root-face and the number of edges as parameters. Explicit expression of enumerating function is obtained for such maps on the sphere and the projective plane. A parametric expression of the generating function is obtained for such maps on the projective plane, from which asymptotic evaluations are derived.     

Enumeration of unrooted hypermaps of a given genus

In this paper we derive an enumeration formula for the number of hypermaps of a given genus g and given number of darts n in terms of the numbers of rooted hypermaps of genus γ≤g with m darts, where m|n. Explicit expressions for the number of rooted hypermaps of genus g with n darts were derived by Walsh [T.R.S. Walsh, Hypermaps versus bipartite maps, J. Combin. Theory B 18 (2) (1975) 155-163] for g=0, and by Arquès [D. Arquès, Hypercartes pointées sur le tore: Décompositions et dénombrements, J. Combin. Theory B 43 (1987) 275-286] for g=1. We apply our general counting formula to derive explicit expressions for the number of unrooted spherical hypermaps and for the number of unrooted toroidal hypermaps with given number of darts. We note that in this paper isomorphism classes of hypermaps of genus g≥0 are distinguished up to the action of orientation-preserving hypermap isomorphisms. The enumeration results can be expressed in terms of Fuchsian groups.     

Composite genus one Belyi maps

Motivated by a demand for explicit genus 1 Belyi maps from theoretical physics, we give an efficient method of explicitly computing genus one Belyi maps by (1) composing covering maps from elliptic curves to the Riemann sphere with simpler (univariate) genus zero Belyi maps, as well as by (2) composing further with isogenies between elliptic curves. The computed examples of genus 1 Belyi maps has doubly-periodic dessins d’enfant that are listed in the physics literature as so-called brane-tilings in the context of quiver gauge theories.     

Geometric quantization for proper moment maps

We establish a geometric quantization formula for Hamiltonian actions of a compact Lie group acting on a non-compact symplectic manifold such that the associated moment map is proper. In particular, we give a solution to a conjecture of Michèle Vergne. To cite this article: X. Ma, W. Zhang, C. R. Acad. Sci. Paris, Ser. I 347 (2009).     

Geometric quantization for proper moment maps: the Vergne conjecture

We establish an analytic interpretation for the index of certain transversally elliptic symbols on non-compact manifolds. By using this interpretation, we establish a geometric quantization formula for a Hamiltonian action of a compact Lie group acting on a non-compact symplectic manifold with proper moment map. In particular, we present a solution to a conjecture of Michèle Vergne in her ICM 2006 plenary lecture.