Alejandro Morales ; Ekaterina Vassilieva
-
Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution
dmtcs:2682 -
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.2682
Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution
2 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
We derive a new formula for the number of factorizations of a full cycle into an ordered product of two permutations of given cycle types. For the first time, a purely combinatorial argument involving a bijective description of bicolored maps of specified vertex degree distribution is used. All the previous results in the field rely either partially or totally on a character theoretic approach. The combinatorial proof relies on a new bijection extending the one in [G. Schaeffer and E. Vassilieva. $\textit{J. Comb. Theory Ser. A}$, 115(6):903―924, 2008] that focused only on the number of cycles. As a salient ingredient, we introduce the notion of thorn trees of given vertex degree distribution which are recursive planar objects allowing simple description of maps of arbitrary genus. \par
Bernardi, Olivier; Du, Rosena R. X.; Morales, Alejandro H.; Stanley, Richard P., 2013, Separation Probabilities For Products Of Permutations, Combinatorics, Probability And Computing, 23, 2, pp. 201-222, 10.1017/s0963548313000588.
Bernardi, Olivier; Morales, Alejandro H., 2013, Bijections And Symmetries For The Factorizations Of The Long Cycle, Advances In Applied Mathematics, 50, 5, pp. 702-722, 10.1016/j.aam.2013.01.004.
FĂŠray, Valentin; Vassilieva, Ekaterina A., 2012, Bijective Enumeration Of Some Colored Permutations Given By The Product Of Two Long Cycles, Discrete Mathematics, 312, 2, pp. 279-292, 10.1016/j.disc.2011.09.010.
Vassilieva, Ekaterina, 2017, Moments Of Normally Distributed Random Matrices Given By Generating Series For Connection Coefficients â Explicit Bijective Computation, Annals Of Combinatorics, 21, 3, pp. 445-477, 10.1007/s00026-017-0356-y.
Vassilieva, Ekaterina A., 2014, Polynomial Properties Of Jack Connection Coefficients And Generalization Of A Result By DĂŠnes, Journal Of Algebraic Combinatorics, 42, 1, pp. 51-71, 10.1007/s10801-014-0573-y.