ALGEBRAIC COMBINATORICS

no. 2
Telescopic groups and symmetries of combinatorial maps
Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 483-508.

In the present paper, we show that many combinatorial and topological objects, such as maps, hypermaps, three-dimensional pavings, constellations and branched coverings of the two-sphere admit any given finite automorphism group. This enhances the already known results by Frucht, Cori–Machì, Širáň–Škoviera, and other authors. We also provide a more universal technique for showing that “any finite automorphism group is possible”, that is applicable to wider classes or, in contrast, to more particular sub-classes of said combinatorial and geometric objects. Finally, we show that any given finite automorphism group can be realised by sufficiently many non-isomorphic such entities (super-exponentially many with respect to a certain combinatorial complexity measure).

Received: 2019-01-30
Revised: 2019-11-07
Accepted: 2019-11-14
Published online: 2020-04-01
DOI: https://doi.org/10.5802/alco.101
Classification: 20E07,  52C20,  52C22,  05C30
Keywords: automorphism, free product, free group, hypermap, ribbon graph, symmetry 
@article{ALCO_2020__3_2_483_0,
     author = {Bottinelli, R\'emi and Grave de Peralta, Laura and Kolpakov, Alexander},
     title = {Telescopic groups and symmetries of combinatorial maps},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {3},
     number = {2},
     year = {2020},
     pages = {483-508},
     doi = {10.5802/alco.101},
     language = {en},
     url={alco.centre-mersenne.org/item/ALCO_2020__3_2_483_0/}
}
Bottinelli, Rémi; Grave de Peralta, Laura; Kolpakov, Alexander. Telescopic groups and symmetries of combinatorial maps. Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 483-508. doi : 10.5802/alco.101. https://alco.centre-mersenne.org/item/ALCO_2020__3_2_483_0/

[1] Arquès, Didier; Koch, Patrice Pavages tridimensionels, Bigre + Globule, Volume 61-62 (1989), pp. 5-15

[2] Bollobás, Béla The asymptotic number of unlabelled regular graphs, J. Lond. Math. Soc., Volume 26 (1982), pp. 201-206 | Article | MR 675164 | Zbl 0504.05051

[3] Breda d’Azevedo, Antonio; Mednykh, Alexander; Nedela, Roman Enumeration of maps regardless of genus: geometric approach, Discrete Math., Volume 310 (2010) no. 6-7, pp. 1184-1203 | Article | MR 2579852 | Zbl 1236.05109

[4] Ciobanu, Laura; Kolpakov, Alexander Three-dimensional maps and subgroup growth (2017) (https://arxiv.org/abs/1712.01418)

[5] Ciobanu, Laura; Kolpakov, Alexander Free subgroups of free products and combinatorial hypermaps, Discrete Math., Volume 342 (2019) no. 5, pp. 1415-1433 | Article | MR 3911640 | Zbl 1407.05127

[6] Cori, Robert Un code pour les graphes planaires et ses applications., Astérisque, Volume 27, Société Mathématique de France (SMF), Paris, 1975, pp. 1-169 | Numdam | MR 404045 | Zbl 0313.05115

[7] Cori, Robert; Machì, Antonio Construction of maps with prescribed automorphism group, Theor. Comput. Sci., Volume 21 (1982) no. 1, pp. 91-98 | Article | MR 672104 | Zbl 0495.05050

[8] Cori, Robert; Machì, Antonio Maps, hypermaps and their automorphisms: a survey, I, II, III, Expo. Math., Volume 10 (1992), p. 403-427, 429–447, 449–467 | MR 1190182 | Zbl 0772.05039

[9] Drmota, Michael; Nedela, Roman Asymptotic enumeration of reversible maps regardless of genus, Ars Math. Contemp., Volume 5 (2012), pp. 77-97 | Article | MR 2869453 | Zbl 1247.05109

[10] Feĭnberg, Valeriĭ Zalmanovich Automorphism groups of trees, Dokl. Akad. Nauk BSSR, Volume 13 (1969), pp. 1065-1067 | MR 282885

[11] Frucht, Roberto Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compos. Math., Volume 6 (1938), pp. 239-250 | MR 1557026 | Zbl 64.0596.02

[12] Jones, Gareth A. Realisation of groups as automorphism groups in permutational categories (2018) (https://arxiv.org/abs/1807.00547)

[13] Jones, Gareth A.; Singerman, David Theory of maps on orientable surfaces, Proc. Lond. Math. Soc., Volume S3-37 (1978) no. 2, pp. 273-307 | Article | MR 505721 | Zbl 0391.05024

[14] Kapovich, Ilya; Myasnikov, Alexei Stallings foldings and subgroups of free groups, J. Algebra, Volume 248 (2002) no. 2, pp. 608-668 | Article | MR 1882114 | Zbl 1001.20015

[15] Lando, Sergei K.; Zvonkin, Alexander K. Graphs on surfaces and their applications, Encycl. Math. Sci., Volume 141, Springer, 2004 | MR 2036721 | Zbl 1040.05001

[16] Mednykh, Alexander; Nedela, Roman Enumeration of unrooted maps of a given genus, J. Comb. Theory, Ser. B, Volume 96 (2006) no. 5, pp. 706-729 | Article | MR 2236507 | Zbl 1102.05033

[17] Mednykh, Alexander; Nedela, Roman Enumeration of unrooted hypermaps of a given genus, Discrete Math., Volume 310 (2010) no. 3, pp. 518-526 | Article | MR 2564806 | Zbl 1185.05082

[18] Serre, Jean-Pierre Trees, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003, x+142 pages | Zbl 1013.20001

[19] Širáň, Josef; Škoviera, Martin Orientable and non-orientable maps with given automorphism groups, Australas. J. Comb., Volume 7 (1993), pp. 47-53 | Zbl 0777.05054

[20] Spehner, Jean-Claude Merging in maps and in pavings, Theor. Comput. Sci., Volume 86 (1991) no. 2, pp. 205-232 | Article | MR 1122788 | Zbl 0733.68093

[21] Stallings, John R. Topology of finite graphs, Invent. Math., Volume 71 (1983) no. 3, pp. 551-565 | Article | MR 695906 | Zbl 0521.20013

[22] Stothers, W. Wilson Free subgroups of the free product of cyclic groups, Math. Comput., Volume 32 (1978) no. 144, pp. 1274-1280 | Article | MR 502015 | Zbl 0395.20013

[23] Tutte, William T. What is a map?, New Directions in Graph Theory (Harary, F., ed.), Academic Press, New York, 1973, pp. 309-325 | Zbl 0258.05105

[24] Welsch, Cora Subgroup graph methods for presentations of finitely generated groups and the contractibility of associated simplicial complexes, J. Algebra, Volume 486 (2017), pp. 119-156 | Article | MR 3666210 | Zbl 1400.20023