Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic

Popis výsledku v původním jazyce

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&amp; 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 &amp; Tucker, Local maxima in graded graphs of imbeddings,Ann. NY Acad. Sci 1979] and [Gross &amp; 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 &quot;random topological graph theory&quot;. 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 &amp; 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 &lt; E[F (Kn)] &lt;= 3.65 ln n + o(1). This substantially improves Stahl&apos;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))] &lt;= (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).

Název v anglickém jazyce

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic

Popis výsledku anglicky

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&amp; 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 &amp; Tucker, Local maxima in graded graphs of imbeddings,Ann. NY Acad. Sci 1979] and [Gross &amp; 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 &quot;random topological graph theory&quot;. 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 &amp; 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 &lt; E[F (Kn)] &lt;= 3.65 ln n + o(1). This substantially improves Stahl&apos;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))] &lt;= (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).

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-21082S" target="_blank" >GA19-21082S: Grafy a jejich algebraické vlastnosti</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

ISBN

978-1-61197-791-2

ISSN

—

e-ISSN

—

Počet stran výsledku

17

Strana od-do

1177-1193

Název nakladatele

Society for Industrial and Applied Mathematics

Místo vydání

Neuveden

Místo konání akce

Alexandria, Virginia

Datum konání akce

7. 1. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—