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).
Revised: 2019-11-06
Accepted: 2019-11-13
Published online: 2020-04-01
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}, pages = {483--508}, publisher = {MathOA foundation}, volume = {3}, number = {2}, year = {2020}, 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] Pavages tridimensionels, Bigre + Globule, Volume 61-62 (1989), pp. 5-15
[2] The asymptotic number of unlabelled regular graphs, J. Lond. Math. Soc., Volume 26 (1982), pp. 201-206 | Article | MR 675164 | Zbl 0504.05051
[3] 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] Three-dimensional maps and subgroup growth (2017) (https://arxiv.org/abs/1712.01418)
[5] 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] 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 | Zbl 0313.05115
[7] 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] 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] Asymptotic enumeration of reversible maps regardless of genus, Ars Math. Contemp., Volume 5 (2012), pp. 77-97 | Article | MR 2869453 | Zbl 1247.05109
[10] Automorphism groups of trees, Dokl. Akad. Nauk BSSR, Volume 13 (1969), pp. 1065-1067 | MR 282885
[11] Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compos. Math., Volume 6 (1938), pp. 239-250 | MR 1557026 | Zbl 64.0596.02
[12] Realisation of groups as automorphism groups in permutational categories (2018) (https://arxiv.org/abs/1807.00547)
[13] 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] Stallings foldings and subgroups of free groups, J. Algebra, Volume 248 (2002) no. 2, pp. 608-668 | Article | MR 1882114 | Zbl 1001.20015
[15] Graphs on surfaces and their applications, Encycl. Math. Sci., Volume 141, Springer, 2004 | MR 2036721 | Zbl 1040.05001
[16] 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] 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] Trees, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003, x+142 pages | Zbl 1013.20001
[19] Orientable and non-orientable maps with given automorphism groups, Australas. J. Comb., Volume 7 (1993), pp. 47-53 | Zbl 0777.05054
[20] Merging in maps and in pavings, Theor. Comput. Sci., Volume 86 (1991) no. 2, pp. 205-232 | Article | MR 1122788 | Zbl 0733.68093
[21] Topology of finite graphs, Invent. Math., Volume 71 (1983) no. 3, pp. 551-565 | Article | MR 695906 | Zbl 0521.20013
[22] 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] What is a map?, New Directions in Graph Theory (Harary, F., ed.), Academic Press, New York, 1973, pp. 309-325 | Zbl 0258.05105
[24] 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