Random 2-cell embeddings of multistars
HTML articles powered by AMS MathViewer
- by Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, Bojan Mohar and Robert Šámal
- Proc. Amer. Math. Soc. 150 (2022), 3699-3713
- DOI: https://doi.org/10.1090/proc/15899
- Published electronically: June 3, 2022
- PDF | Request permission
Abstract:
Random 2-cell embeddings of a given graph $G$ are obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces, $\mathbb {E}[F_G]$, of such an embedding which is equivalent to studying its average genus. So far, tight results are known for two families called monopoles and dipoles. We extend the dipole result to a more general family called multistars, i.e., loopless multigraphs in which there is a vertex incident with all the edges. In particular, we show that the expected number of faces of every multistar with $n$ nonleaf edges lies in an interval of length $2/(n+1)$ centered at the expected number of faces of an $n$-edge dipole. This allows us to derive bounds on $\mathbb {E}[F_G]$ for any given graph $G$ in terms of vertex degrees. We conjecture that $\mathbb {E}[F_G]\le O(n)$ for any simple $n$-vertex graph $G$.References
- G. E. Andrews, D. M. Jackson, and T. I. Visentin, A hypergeometric analysis of the genus series for a class of $2$-cell embeddings in orientable surfaces, SIAM J. Math. Anal. 25 (1994), no. 2, 243–255. MR 1266557, DOI 10.1137/S0036141092229549
- Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, Bojan Mohar, and Robert Šámal, Random 2-cell embeddings of multistars, In Jaroslav Nešetřil, Guillem Perarnau, Juanjo Rué, Oriol Serra (eds), Extended Abstracts EuroComb 2021. Trends in Mathematics (2021), 805–810, Springer International Publishing. DOI 10.1007/978-3-030-83823-2_128.
- Guillaume Chapuy, A new combinatorial identity for unicellular maps, via a direct bijective approach, Adv. in Appl. Math. 47 (2011), no. 4, 874–893. MR 2832383, DOI 10.1016/j.aam.2011.04.004
- Ricky X. F. Chen, Combinatorially refine a Zagier-Stanley result on products of permutations, Discrete Math. 343 (2020), no. 8, 111912, 5. MR 4080838, DOI 10.1016/j.disc.2020.111912
- Ricky X. F. Chen and Christian M. Reidys, Plane permutations and applications to a result of Zagier-Stanley and distances of permutations, SIAM J. Discrete Math. 30 (2016), no. 3, 1660–1684. MR 3539895, DOI 10.1137/15M1023646
- Robert Cori, Michel Marcus, and Gilles Schaeffer, Odd permutations are nicer than even ones, European J. Combin. 33 (2012), no. 7, 1467–1478. MR 2923463, DOI 10.1016/j.ejc.2012.03.012
- I. P. Goulden and William Slofstra, Annular embeddings of permutations for arbitrary genus, J. Combin. Theory Ser. A 117 (2010), no. 3, 272–288. MR 2592901, DOI 10.1016/j.jcta.2009.11.009
- Jonathan L. Gross, Toufik Mansour, and Thomas W. Tucker, Valence-partitioned genus polynomials and their application to generalized dipoles, Australas. J. Combin. 67 (2017), 203–221. MR 3607822
- Jonathan L. Gross, David P. Robbins, and Thomas W. Tucker, Genus distributions for bouquets of circles, J. Combin. Theory Ser. B 47 (1989), no. 3, 292–306. MR 1026066, DOI 10.1016/0095-8956(89)90030-0
- John Harer and Don Zagier, The Euler characteristic of the moduli space of curves, Invent. Math. 85 (1986), no. 3, 457–485, DOI 10.1007/BF01390325.
- D. M. Jackson, Counting cycles in permutations by group characters, with an application to a topological problem, Trans. Amer. Math. Soc. 299 (1987), no. 2, 785–801. MR 869231, DOI 10.1090/S0002-9947-1987-0869231-9
- D. M. Jackson, Algebraic and analytic approaches for the genus series for $2$-cell embeddings on orientable and nonorientable surfaces, Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 24, Amer. Math. Soc., Providence, RI, 1996, pp. 115–132. MR 1363509, DOI 10.1090/dimacs/024/06
- D. M. Jackson, On an integral representation for the genus series for $2$-cell embeddings, Trans. Amer. Math. Soc. 344 (1994), no. 2, 755–772. MR 1236224, DOI 10.1090/S0002-9947-1994-1236224-5
- Jin Ho Kwak and Jaeun Lee, Genus polynomials of dipoles, Kyungpook Math. J. 33 (1993), no. 1, 115–125. MR 1231770
- Sergei K. Lando and Alexander K. Zvonkin, Graphs on surfaces and their applications, Encyclopaedia of Mathematical Sciences, vol. 141, Springer-Verlag, Berlin, 2004. With an appendix by Don B. Zagier; Low-Dimensional Topology, II. MR 2036721, DOI 10.1007/978-3-540-38361-1
- Bojan Mohar and Carsten Thomassen, Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. MR 1844449
- Jaroslav Ne et il and Patrice Ossona de Mendez, Sparsity, Algorithms and Combinatorics, vol. 28, Springer, Heidelberg, 2012. Graphs, structures, and algorithms. MR 2920058, DOI 10.1007/978-3-642-27875-4
- Robert G. Rieper, The enumeration of graph imbeddings, Ph.D. Thesis, Western Michigan University, Kalamazoo, Michigan, 1987.
- Saul Stahl, Region distributions of graph embeddings and Stirling numbers, Discrete Math. 82 (1990), no. 1, 57–78. MR 1058710, DOI 10.1016/0012-365X(90)90045-J
- Saul Stahl, Permutation-partition pairs. III. Embedding distributions of linear families of graphs, J. Combin. Theory Ser. B 52 (1991), no. 2, 191–218. MR 1110469, DOI 10.1016/0095-8956(91)90062-O
- Saul Stahl, An upper bound for the average number of regions, J. Combin. Theory Ser. B 52 (1991), no. 2, 219–221. MR 1110470, DOI 10.1016/0095-8956(91)90063-P
- Saul Stahl, On the average genus of the random graph, J. Graph Theory 20 (1995), no. 1, 1–18. MR 1339676, DOI 10.1002/jgt.3190200102
- Richard P. Stanley, Two enumerative results on cycles of permutations, European J. Combin. 32 (2011), no. 6, 937–943. MR 2821562, DOI 10.1016/j.ejc.2011.01.011
- Arthur T. White, Graphs, groups and surfaces, North-Holland Mathematics Studies, No. 8, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. MR 0340026
- Arthur T. White, An introduction to random topological graph theory, Combin. Probab. Comput. 3 (1994), no. 4, 545–555. MR 1314074, DOI 10.1017/S0963548300001395
- Don Zagier, On the distribution of the number of cycles of elements in symmetric groups, Nieuw Arch. Wisk. (4) 13 (1995), no. 3, 489–495. MR 1378813
Bibliographic Information
- Jesse Campion Loth
- Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, V5A 1S6 British Columbia, Canada
- Email: jcampion@sfu.ca
- Kevin Halasz
- Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, V5A 1S6 British Columbia, Canada
- MR Author ID: 1315883
- ORCID: 0000-0003-0573-8410
- Email: khalasz@sfu.ca
- Tomáš Masařík
- Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, V5A 1S6 British Columbia, Canada
- Address at time of publication: Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
- ORCID: 0000-0001-8524-4036
- Email: masarik@mimuw.edu.pl
- Bojan Mohar
- Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, V5A 1S6 British Columbia, Canada
- MR Author ID: 126065
- ORCID: 0000-0002-7408-6148
- Email: mohar@sfu.ca
- Robert Šámal
- Affiliation: Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Praha, 118 00, Czech Republic
- ORCID: 0000-0002-0172-6511
- Email: samal@iuuk.mff.cuni.cz
- Received by editor(s): March 8, 2021
- Received by editor(s) in revised form: July 14, 2021, September 17, 2021, and October 25, 2021
- Published electronically: June 3, 2022
- Additional Notes: The third author was supported by a postdoctoral fellowship at the Simon Fraser University through NSERC grants R611450 and R611368. The fourth author was supported in part by the NSERC Discovery Grant R611450 (Canada) and by the Research Project J1-8130 of ARRS (Slovenia). The fifth author was partially supported by grant 19-21082S of the Czech Science Foundation. This project had received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 810115). This project had received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 823748
An extended abstract of this paper has appeared at the European conference on combinatorics, graph theory and applications (EUROCOMB) 2021 \cite{EUROCOMB21} - Communicated by: Patricia L. Hersh
- © Copyright 2022 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 150 (2022), 3699-3713
- MSC (2020): Primary 05C10
- DOI: https://doi.org/10.1090/proc/15899
- MathSciNet review: 4446223