Enumeration of rooted 3-connected bipartite planar maps

Marc Noy; Clément Requilé; Juanjo Rué

doi:10.5802/crmath.548

Article de recherche - Combinatoire

Enumeration of rooted 3-connected bipartite planar maps
[Énumération des cartes planaires enracinées biparties et 3-connexes]

Marc Noy ^1,² ; Clément Requilé ¹ ; Juanjo Rué ^1,²

¹ Departament de Matemàtiques and Institut de Matemàtiques (IMTech) de la Universitat Politècnica de Catalunya (UPC), Barcelona, Spain
² Centre de Recerca Matemàtica (CRM), Barcelona, Spain

Comptes Rendus. Mathématique, Volume 362 (2024), pp. 143-158.

Résumé
Abstract

Nous apportons la première solution au problème du dénombrement des cartes enracinées plan-aires qui sont biparties et 3-connexes. Notre point de départ est l’énumération des cartes planaires bi-coloriées, d’après Bernardi et Bousquet-Mélou [J. Comb. Theory Ser. B, 101 (2011), 315–377]. La décomposition d’une carte en composantes 2- et 3-connexes nous permet ensuite d’obtenir les fonctions génératrices des cartes bi-coloriées 2- et 3-connexes. En évaluant à zéro la variable marquant le nombre d’arêtes monochromes, nous obtenons alors la fonction génératrice des cartes biparties 3-connexes. Cette dernière est algébrique de degré 26. Nous en déduisons une estimation asymptotique de la forme $t n^{- 5 / 2} γ^{n}$ du nombre de cartes planaires biparties 3-connexes, avec $γ = ρ^{- 1} \approx 2.40958$ et où $ρ \approx 0.41501$ est un nombre algébrique de degré $10$ .

We provide the first solution to the problem of counting rooted 3-connected bipartite planar maps. Our starting point is the enumeration of bicoloured planar maps according to the number of edges and monochromatic edges, following Bernardi and Bousquet-Mélou [J. Comb. Theory Ser. B, 101 (2011), 315–377]. The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2- and 3-connected bicoloured maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26. We deduce from it an asymptotic estimate for the number of 3-connected bipartite planar maps of the form $t n^{- 5 / 2} γ^{n}$ , where $γ = ρ^{- 1} \approx 2.40958$ and $ρ \approx 0.41501$ is an algebraic number of degree $10$ .

Reçu le : 2022-03-03
Accepté le : 2023-07-21
Publié le : 2024-03-07

DOI : 10.5802/crmath.548

Affiliations des auteurs :

Marc Noy ^{1, 2} ; Clément Requilé ¹ ; Juanjo Rué ^{1, 2}

¹ Departament de Matemàtiques and Institut de Matemàtiques (IMTech) de la Universitat Politècnica de Catalunya (UPC), Barcelona, Spain
² Centre de Recerca Matemàtica (CRM), Barcelona, Spain

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2024__362_G2_143_0,
     author = {Marc Noy and Cl\'ement Requil\'e and Juanjo Ru\'e},
     title = {Enumeration of rooted 3-connected bipartite planar maps},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {143--158},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     year = {2024},
     doi = {10.5802/crmath.548},
     language = {en},
}

TY  - JOUR
AU  - Marc Noy
AU  - Clément Requilé
AU  - Juanjo Rué
TI  - Enumeration of rooted 3-connected bipartite planar maps
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 143
EP  - 158
VL  - 362
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.548
LA  - en
ID  - CRMATH_2024__362_G2_143_0
ER  -

%0 Journal Article
%A Marc Noy
%A Clément Requilé
%A Juanjo Rué
%T Enumeration of rooted 3-connected bipartite planar maps
%J Comptes Rendus. Mathématique
%D 2024
%P 143-158
%V 362
%I Académie des sciences, Paris
%R 10.5802/crmath.548
%G en
%F CRMATH_2024__362_G2_143_0

Marc Noy; Clément Requilé; Juanjo Rué. Enumeration of rooted 3-connected bipartite planar maps. Comptes Rendus. Mathématique, Volume 362 (2024), pp. 143-158. doi : 10.5802/crmath.548. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.548/

Bibliographie
Cité par

[1] Maple session (https://requile.github.io/3connected_bipartite_maps.mw)

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

[3] O. Bernardi; M. Bousquet-Mélou Counting coloured planar maps: differential equations, Commun. Math. Phys., Volume 354 (2017) no. 1, pp. 31-84 | DOI | MR | Zbl

[4] M. Bousquet-Mélou Counting planar maps, coloured or uncoloured, Surveys in combinatorics 2011. Papers from the 23rd British combinatorial conference, Exeter, UK, July 3–8, 2011 (London Mathematical Society Lecture Note Series), Volume 392, London Mathematical Society, 2011, pp. 1-50 | MR | Zbl

[5] M. Bousquet-Mélou; A. Jehanne Polynomial equations with one catalytic variable, algebraic series and map enumeration, J. Comb. Theory, Ser. B, Volume 96 (2006) no. 5, pp. 623-672 | DOI | MR | Zbl

[6] W. G. Brown On the existence of square roots in certain rings of power series, Math. Ann., Volume 158 (1965), pp. 82-89 | DOI | MR | Zbl

[7] P. Chassaing; G. Schaeffer Random planar lattices and integrated superBrownian excursion, Probab. Theory Relat. Fields, Volume 128 (2004) no. 2, pp. 161-212 | DOI | MR | Zbl

[8] R. Cori; B. Vauquelin Planar maps are well labeled trees, Can. J. Math., Volume 33 (1981), pp. 1023-1042 | DOI | MR | Zbl

[9] M. Drmota; M. Noy; G.-R. Yu Universal singular exponents in catalytic variable equations, J. Comb. Theory, Ser. A, Volume 185 (2022), 105522 | DOI | MR | Zbl

[10] M. Drmota; L. Ramos; J. Rué Subgraph statistics in subcritical graph classes, Random Struct. Algorithms, Volume 51 (2017) no. 4, pp. 631-673 | DOI | MR | Zbl

[11] P. Flajolet; R. Sedgewick Analytic Combinatorics, Cambridge University Press, 2009 | DOI | Zbl

[12] J.-F. Le Gall Brownian geometry, Jap. J. Math., Volume 14 (2019) no. 2, pp. 135-174 | DOI | MR | Zbl

[13] V. A. Liskovets; T. R. S. Walsh Enumeration of Eulerian and unicursal planar maps, Discrete Math., Volume 282 (2004) no. 1-3, pp. 209-221 | DOI | MR | Zbl

[14] R. C. Mullin; L. B. Richmond; R. G. Stanton An asymptotic relation for bicubic maps, Proceedings of the Third Manitoba Conference on Numerical Mathematics (Congressus Numerantium), Volume 9, Utilitas Mathematics Publications, Winnipeg (1974), pp. 345-355 | Zbl

[15] M. Noy; C. Requilé; J. Rué Enumeration of labelled 4-regular planar graphs, Proc. Lond. Math. Soc., Volume 119 (2019) no. 2, pp. 358-378 | DOI | MR | Zbl

[16] M. Noy; C. Requilé; J. Rué Further results on random cubic planar graphs, Random Struct. Algorithms, Volume 56 (2020) no. 3, pp. 892-924 | DOI | MR | Zbl

[17] M. Noy; C. Requilé; J. Rué Enumeration of labelled 4-regular planar graphs. II: Asymptotics, Eur. J. Comb., Volume 110 (2023) no. 19, 103661 | DOI | MR | Zbl

[18] A. M. Odlyzko; L. B. Richmond A differential equation arising in chromatic sum theory, Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983) (Congressus Numerantium), Volume 40, Utilitas Mathematics Publications, Winnipeg (1983), pp. 263-275 | MR | Zbl

[19] J. Rué; K. Weller The Ising model on graphs: grammar and applications to bipartite enumeration, Proceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS) (2014), pp. 351-362 | Zbl

[20] G. Schaeffer Conjugaison d’arbres et cartes combinatoires aléatoires, Ph. D. Thesis, Université Bordeaux 1, France (1998)

[21] G. Schaeffer Planar maps, Handbook of Enumerative Combinatorics (M. Bóna, ed.) (Discrete Mathematics and its Applications), CRC Press, 2015, pp. 335-395 | DOI | Zbl

[22] B. A. Trakhtenbrot To the theory of non-repeating contact schemes, Tr. Mat. Inst. Steklova, Volume 51 (1958), pp. 226-269 | MR | Zbl

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

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

[25] W. T. Tutte Dichromatic sums for rooted planar maps, Combinatorics (Univ. California, Los Angeles, 1968) (Proceedings of Symposia in Pure Mathematics), Volume 19, American Mathematical Society (1971), pp. 235-245 | Zbl

[26] W. T. Tutte Chromatic sums for rooted planar triangulations: the cases $λ = 1$ and $λ = 2$ , Can. J. Math., Volume 25 (1973), pp. 426-447 | DOI | Zbl

[27] W. T. Tutte Chromatic solutions. II., Can. J. Math., Volume 34 (1982), pp. 952-960 | DOI | Zbl

[28] W. T. Tutte Graph Theory As I Have Known It, Oxford Lecture Series in Mathematics and its Applications, 11, Clarendon Press, 1998 | Zbl

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

An upper bound on the 2-outer-independent domination number of a tree

Marcin Krzywkowski

C. R. Math (2011)

Rank, term rank and chromatic number of a graph

Saieed Akbari; Hamid-Reza Fanaï

C. R. Math (2005)

Graph-theoretical methods in general function theory

Amine El Sahili

C. R. Math (2002)