Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10480747" target="_blank" >RIV/00216208:11320/24:10480747 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1137/1.9781611977912.46" target="_blank" >https://doi.org/10.1137/1.9781611977912.46</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/1.9781611977912.46" target="_blank" >10.1137/1.9781611977912.46</a>
Alternative languages
Result language
angličtina
Original language name
Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
Original language description
A random 2-cell embedding of a connected graph G in some orientable surface is obtained by choosinga random local rotation around each vertex. Under this setup, the number of faces or the genus of thecorresponding 2-cell embedding becomes a random variable. Random embeddings of two particular graphclasses - those of a bouquet of n loops and those of n parallel edges connecting two vertices - have beenextensively studied and are well-understood. However, little is known about more general graphs despite theirimportant connections with central problems in mainstream mathematics and in theoretical physics (see [Lando& Zvonkin, Graphs on surfaces and their applications, Springer 2004]). There are also tight connections withproblems in computing (random generation, approximation algorithms). The results of this paper, in particular,explain why Monte Carlo methods (see, e.g., [Gross & Tucker, Local maxima in graded graphs of imbeddings,Ann. NY Acad. Sci 1979] and [Gross & Rieper, Local extrema in genus stratified graphs, JGT 1991]) cannotwork for approximating the minimum genus of graphs.In his breakthrough work ([Stahl, Permutation-partition pairs, JCTB 1991] and a series of other papers),Stahl developed the foundation of "random topological graph theory". Most of his results have been unsurpasseduntil today. In our work, we analyze the expected number of faces of random embeddings (equivalently, theaverage genus) of a graph G. It was very recently shown [Campion Loth & Mohar, Expected number of faces ina random embedding of any graph is at most linear, CPC 2023] that for any graph G, the expected number offaces is at most linear. We show that the actual expected number of faces F (G) is almost always much smaller.In particular, we prove the following results:(1) 1/2 ln n - 2 < E[F (Kn)] <= 3.65 ln n + o(1). This substantially improves Stahl's n + ln n upper bound forthis case.(2) For random graphs G(n, p) (p = p(n)), we have E[F (G(n, p))] <= (ln n)^2 + 1/p .(3) For random models B(n, Delta ) containing only graphs, whose maximum degree is at most Delta , we obtainstronger bounds by showing that the expected number of faces is Θ(ln n).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-21082S" target="_blank" >GA19-21082S: Graphs and their algebraic properties</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
ISBN
978-1-61197-791-2
ISSN
—
e-ISSN
—
Number of pages
17
Pages from-to
1177-1193
Publisher name
Society for Industrial and Applied Mathematics
Place of publication
Neuveden
Event location
Alexandria, Virginia
Event date
Jan 7, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—