ALGEBRAIC COMBINATORICS

no. 6
Enumeration of non-oriented maps via integrability
Bonzom, Valentin1; Chapuy, Guillaume2; Dołęga, Maciej3
1 Université Sorbonne Paris Nord LIPN, CNRS, UMR 7030 F-93430 Villetaneuse France
2 CNRS, IRIF UMR 8243 Université Paris Cité.
3 Institute of Mathematics Polish Academy of Sciences ul. Śniadeckich 8 00-956 Warszawa Poland.
Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1363-1390.

In this note, we examine how the BKP structure of the generating series of several models of maps on non-oriented surfaces can be used to obtain explicit and/or efficient recurrence formulas for their enumeration according to the genus and size parameters.

Using techniques already known in the orientable case (elimination of variables via Virasoro constraints or Tutte equations), we naturally obtain recurrence formulas with non-polynomial coefficients. This non-polynomiality reflects the presence of shifts of the charge parameter in the BKP equation. Nevertheless, we show that it is possible to obtain non-shifted versions, meaning pure ODEs for the associated generating functions, from which recurrence relations with polynomial coefficients can be extracted. We treat the cases of triangulations, general maps, and bipartite maps.

These recurrences with polynomial coefficients are conceptually interesting but bigger to write than those with non-polynomial coefficients. However they are relatively nice-looking in the case of one-face maps. In particular we show that Ledoux’s recurrence for non-oriented one-face maps can be recovered in this way, and we obtain the analogous statement for the (bivariate) bipartite case.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.268
Classification: 05A15, 05C30, 37K10
Keywords: combinatorial maps, nonorientable surfaces, enumeration, BKP hierarchy, zonal polynomials, matrix integrals
Bonzom, Valentin 1; Chapuy, Guillaume 2; Dołęga, Maciej 3

1 Université Sorbonne Paris Nord LIPN, CNRS, UMR 7030 F-93430 Villetaneuse France
2 CNRS, IRIF UMR 8243 Université Paris Cité.
3 Institute of Mathematics Polish Academy of Sciences ul. Śniadeckich 8 00-956 Warszawa Poland.
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2022__5_6_1363_0,
     author = {Bonzom, Valentin and Chapuy, Guillaume and Do{\l}\k{e}ga, Maciej},
     title = {Enumeration of non-oriented maps via integrability},
     journal = {Algebraic Combinatorics},
     pages = {1363--1390},
     publisher = {The Combinatorics Consortium},
     volume = {5},
     number = {6},
     year = {2022},
     doi = {10.5802/alco.268},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.268/}
}
TY  - JOUR
AU  - Bonzom, Valentin
AU  - Chapuy, Guillaume
AU  - Dołęga, Maciej
TI  - Enumeration of non-oriented maps via integrability
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 1363
EP  - 1390
VL  - 5
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.268/
DO  - 10.5802/alco.268
LA  - en
ID  - ALCO_2022__5_6_1363_0
ER  - 
%0 Journal Article
%A Bonzom, Valentin
%A Chapuy, Guillaume
%A Dołęga, Maciej
%T Enumeration of non-oriented maps via integrability
%J Algebraic Combinatorics
%D 2022
%P 1363-1390
%V 5
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.268/
%R 10.5802/alco.268
%G en
%F ALCO_2022__5_6_1363_0
Bonzom, Valentin; Chapuy, Guillaume; Dołęga, Maciej. Enumeration of non-oriented maps via integrability. Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1363-1390. doi : 10.5802/alco.268. https://alco.centre-mersenne.org/articles/10.5802/alco.268/

[1] Adler, M.; van Moerbeke, P. Hermitian, symmetric and symplectic random ensembles: PDEs for the distribution of the spectrum, Ann. of Math. (2), Volume 153 (2001) no. 1, pp. 149-189 | DOI | MR

[2] Adrianov, N. M. An Analog of the Harer–Zagier Formula for Unicellular Bicolored Maps, Funktsional. Anal. i Prilozhen., Volume 31 (1997) no. 3, pp. 1-9 | DOI

[3] Albenque, M.; Lepoutre, M. Blossoming bijection for higher-genus maps, and bivariate rationality (2019) (Preprint arXiv:2007.07692)

[4] Alexandrov, A.; Chapuy, G.; Eynard, B.; Harnad, J. Weighted Hurwitz numbers and topological recursion, Comm. Math. Phys., Volume 375 (2020) no. 1, pp. 237-305 | DOI | MR

[5] Belliard, R.; Charbonnier, S.; Eynard, B.; Garcia-Failde, E. Topological recursion for generalised Kontsevich graphs and r-spin intersection numbers (2021) (Preprint arXiv:2105.08035) | arXiv

[6] Bender, E. A.; Canfield, E. R. The asymptotic number of rooted maps on a surface, J. Combin. Theory Ser. A, Volume 43 (1986) no. 2, pp. 244-257 | DOI | MR | Zbl

[7] Bender, E. A.; Canfield, E. R. The number of rooted maps on an orientable surface, J. Combin. Theory Ser. B, Volume 53 (1991) no. 2, pp. 293-299 | DOI | MR | Zbl

[8] Bender, E. A.; Canfield, E. R. The number of degree-restricted rooted maps on the sphere, SIAM J. Discrete Math., Volume 7 (1994) no. 1, pp. 9-15 | DOI | MR | Zbl

[9] Bender, E. A.; Gao, Z.; Richmond, L. B. The map asymptotics constant t g , Electron. J. Combin., Volume 15 (2008) no. 1, p. Research paper 51, 8 pp | DOI | MR

[10] Bernardi, O.; Bousquet-Mélou, M. Counting colored planar maps: Algebraicity results, J. Combin. Theory Ser. B, Volume 101 (2011) no. 5, pp. 315-377 | DOI | MR

[11] Bernardi, O.; Bousquet-Mélou, M. Counting Coloured Planar Maps: Differential Equations, Comm. Math. Phys., Volume 354 (2017) no. 1, pp. 31-84 | DOI | MR

[12] Bernardi, O.; Chapuy, G. Counting unicellular maps on non-orientable surfaces, Adv. in Appl. Math., Volume 47 (2011) no. 2, pp. 259-275 | DOI | MR

[13] Bonzom, V.; Chapuy, G.; Dołęga, M. Worksheet accompanying the present paper, available at http://www.irif.fr/~chapuy/worksheets/countingMaps-nonoriented.html or http://www.irif.fr/~chapuy/worksheets/countingMaps-nonoriented.mw, 2021

[14] Bonzom, Valentin; Chapuy, Guillaume; Charbonnier, Séverin; Garcia-Failde, Elba Topological recursion for Orlov-Scherbin tau functions, and constellations with internal faces, 2022 | arXiv | DOI

[15] Bonzom, Valentin; Chapuy, Guillaume; Dołęga, Maciej b-Monotone Hurwitz Numbers: Virasoro Constraints, BKP Hierarchy, and O(N)-BGW Integral, Int. Math. Res. Not. IMRN (2022), Paper no. rnac177 | DOI

[16] Bouttier, J.; Guitter, E. On Irreducible Maps and Slices, Combin. Probab. Comput., Volume 23 (2014) no. 6, pp. 914-972 | DOI | MR | Zbl

[17] Bouttier, J.; Guitter, E.; Miermont, G. Bijective enumeration of planar bipartite maps with three tight boundaries, or how to slice pairs of pants (2021) (Preprint arXiv:2104.10084) | arXiv

[18] Budzinski, T.; Louf, B. Local limits of uniform triangulations in high genus, Invent. Math., Volume 223 (2020) no. 1, pp. 1-47 | DOI | MR | Zbl

[19] Bychkov, B.; Dunin-Barkowski, P.; Kazarian, M.; Shadrin, S. Topological recursion for Kadomtsev-Petviashvili tau functions of hypergeometric type (2020) (Preprint arXiv:2012.14723) | arXiv

[20] Carrell, S. R. The Non-Orientable Map Asymptotics Constant p g (2014) (Preprint arXiv:1406.1760) | arXiv

[21] Carrell, S. R.; Chapuy, G. Simple recurrence formulas to count maps on orientable surfaces, J. Combin. Theory Ser. A, Volume 133 (2015), pp. 58-75 | DOI | MR | Zbl

[22] Chapuy, G.; Dołęga, M. A bijection for rooted maps on general surfaces, J. Combin. Theory Ser. A, Volume 145 (2017), pp. 252-307 | DOI | MR | Zbl

[23] Chapuy, G.; Marcus, M.; Schaeffer, G. A bijection for rooted maps on orientable surfaces, SIAM J. Discrete Math., Volume 23 (2009) no. 3, pp. 1587-1611 | DOI | MR | Zbl

[24] Chekhov, L.; Eynard, B.; Orantin, N. Free energy topological expansion for the 2-matrix model, J. High Energy Phys. (2006) no. 12, p. 053, 31 | DOI | MR | Zbl

[25] Dołęga, M.; Lepoutre, M. Blossoming bijection for bipartite pointed maps and parametric rationality of general maps of any surface, Adv. in Appl. Math., Volume 141 (2022), p. Paper No. 102408 | DOI | MR | Zbl

[26] Eynard, B. Counting surfaces, Progress in Mathematical Physics, 70, Birkhäuser/Springer, [Cham], 2016, xvii+414 pages (CRM Aisenstadt chair lectures) | DOI | MR

[27] Eynard, B.; Orantin, N. Invariants of algebraic curves and topological expansion, Commun. Number Theory Phys., Volume 1 (2007) no. 2, pp. 347-452 | DOI | MR | Zbl

[28] Eynard, Bertrand An overview of the topological recursion, Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. III, Kyung Moon Sa, Seoul, 2014, pp. 1063-1085 | MR | Zbl

[29] Goulden, I. P.; Jackson, D. M. The KP hierarchy, branched covers, and triangulations, Adv. Math., Volume 219 (2008) no. 3, pp. 932-951 | DOI | MR | Zbl

[30] Kac, V.; van de Leur, J. The geometry of spinors and the multicomponent BKP and DKP hierarchies, CRM Proceedings and Lecture Notes, Volume 14, 1998, pp. 159-202 | DOI | MR | Zbl

[31] Kac, V. G.; Raina, A. K.; Rozhkovskaya, N. Bombay lectures on highest weight representations of infinite dimensional Lie algebras, 29, World Scientific, 2013 | DOI

[32] Kazakov, V. A.; Kostov, I. K.; Nekrasov, N. D-particles, matrix integrals and KP hierarchy, Nuclear Physics B, Volume 557 (1999) no. 3, pp. 413-442 | DOI | MR | Zbl

[33] Kazarian, M.; Zograf, P. Virasoro constraints and topological recursion for Grothendieck’s dessin counting, Lett. Math. Phys., Volume 105 (2015) no. 8, pp. 1057-1084 | DOI | MR | Zbl

[34] Ledoux, M. A recursion formula for the moments of the Gaussian orthogonal ensemble, Ann. Inst. Henri Poincaré Probab. Stat., Volume 45 (2009) no. 3, pp. 754-769 | DOI | Numdam | MR | Zbl

[35] Lepoutre, M. Blossoming bijection for higher-genus maps, J. Combin. Theory Ser. A, Volume 165 (2019), pp. 187-224 | DOI | MR | Zbl

[36] Louf, B. Simple Formulas for Constellations and Bipartite Maps with Prescribed Degrees, Canad. J. Math., Volume 73 (2019) no. 1, pp. 160-176 | DOI | MR | Zbl

[37] Miwa, T.; Jimbo, M.; Date, E. Solitons, Cambridge Tracts in Mathematics, 135, Cambridge University Press, Cambridge, 2000, x+108 pages (Differential equations, symmetries and infinite-dimensional algebras, Translated from the 1993 Japanese original by Miles Reid) | MR

[38] Okounkov, A. Toda equations for Hurwitz numbers, Math. Res. Lett., Volume 7 (2000) no. 4, pp. 447-453 | DOI | MR | Zbl

[39] Tutte, W. T. A census of planar triangulations, Canad. J. Math, Volume 14 (1962) no. 1, pp. 21-38 | DOI | MR | Zbl

[40] Tutte, W. T. A census of slicings, Canad. J. Math, Volume 14 (1962) no. 4, pp. 708-722 | DOI | MR | Zbl

[41] Tutte, W. T. A census of planar maps, Canad. J. Math., Volume 15 (1963), pp. 249-271 | DOI | MR | Zbl

[42] Van de Leur, J. Matrix integrals and the geometry of spinors, J. Nonlinear Math. Phys., Volume 8 (2001) no. 2, pp. 288-310 | DOI | MR

[43] Walsh, T. R. S.; Lehman, A. B. Counting rooted maps by genus. I, J. Combinatorial Theory Ser. B, Volume 13 (1972), pp. 192-218 | DOI | MR | Zbl

Cited by Sources: