Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2024 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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

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
Similar Articles
  • Retrieve articles in Proceedings of the American Mathematical Society with MSC (2020): 05C10
  • Retrieve articles in all journals with MSC (2020): 05C10
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