Guillaume Chapuy
-
A new combinatorial identity for unicellular maps, via a direct bijective approach.
dmtcs:2747 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2009,
DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
-
https://doi.org/10.46298/dmtcs.2747
A new combinatorial identity for unicellular maps, via a direct bijective approach.Article
Authors: Guillaume Chapuy 1
NULL
Guillaume Chapuy
1 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
We give a bijective operation that relates unicellular maps of given genus to unicellular maps of lower genus, with distinguished vertices. This gives a new combinatorial identity relating the number $\epsilon_g(n)$ of unicellular maps of size $n$ and genus $g$ to the numbers $\epsilon _j(n)$'s, for $j \lt g$. In particular for each $g$ this enables to compute the closed-form formula for $\epsilon_g(n)$ much more easily than with other known identities, like the Harer-Zagier formula. From the combinatorial point of view, we give an explanation to the fact that $\epsilon_g(n)=R_g(n) \mathrm{Cat}(n)$, where $\mathrm{Cat}(n$) is the $n$-th Catalan number and $R_g$ is a polynomial of degree $3g$, with explicit interpretation.
Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471
Angèle M. Foley;Alejandro H. Morales;Amarpreet Rattan;Karen Yeats, 2022, Combinatorial and Algebraic Enumeration: a survey of the work of Ian P. Goulden and David M. Jackson, Algebraic combinatorics, 5, 6, pp. 1205-1226, 10.5802/alco.269, https://doi.org/10.5802/alco.269.
Houcine Ben Dali, 2022, Generating series of non-oriented constellations and marginal sums in the Matching-Jack conjecture, Algebraic combinatorics, 5, 6, pp. 1299-1336, 10.5802/alco.207, https://doi.org/10.5802/alco.207.
Valentin Féray;Baptiste Louf;Paul Thévenin, 2022, Random generation and scaling limits of fixed genus factorizations into transpositions, Probability theory and related fields, 184, 3-4, pp. 681-748, 10.1007/s00440-022-01170-9, https://doi.org/10.1007/s00440-022-01170-9.
R. Penner, 2016, Moduli spaces and macromolecules, Bulletin (new series) of the American Mathematical Society/Bulletin, new series, of the American Mathematical Society, 53, 2, pp. 217-268, 10.1090/bull/1524, https://doi.org/10.1090/bull/1524.
Ricky X. F. Chen;Christian M. Reidys, 2016, Plane Permutations and Applications to a Result of Zagier--Stanley and Distances of Permutations, arXiv (Cornell University), 30, 3, pp. 1660-1684, 10.1137/15m1023646, https://arxiv.org/abs/1502.07674.
Fenix W.D. Huang;Christian M. Reidys, 2015, Shapes of topological RNA structures, arXiv (Cornell University), 270, pp. 57-65, 10.1016/j.mbs.2015.10.004.
Gilles Schaeffer, Discrete mathematics and its applications, Planar Maps, pp. 335-395, 2015, 10.1201/b18255-8.
Gourab Ray, 2015, Large unicellular maps in high genus, Annales de l'Institut Henri Poincaré. B, Probabilités et statistiques/Annales de l'I.H.P. Probabilités et statistiques, 51, 4, 10.1214/14-aihp618, https://doi.org/10.1214/14-aihp618.
Alejandro H. Morales;Ekaterina A. Vassilieva, 2013, Direct Bijective Computation of the Generating Series for 2 and 3-Connection Coefficients of the Symmetric Group, The Electronic journal of combinatorics/The journal of combinatorics, 20, 2, 10.37236/3226, https://doi.org/10.37236/3226.
Fenix W.D. Huang;Markus E. Nebel;Christian M. Reidys, 2013, Generation of RNA pseudoknot structures with topological genus filtration, Mathematical biosciences, 245, 2, pp. 216-225, 10.1016/j.mbs.2013.07.014.