Phase transitions in graphs on orientable surfaces

M. Kang, Michael Moßhammer, P. Sprüssel*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Let (Formula presented.) be the orientable surface of genus (Formula presented.) and denote by (Formula presented.) the class of all graphs on vertex set (Formula presented.) with (Formula presented.) edges embeddable on (Formula presented.). We prove that the component structure of a graph chosen uniformly at random from (Formula presented.) features two phase transitions. The first phase transition mirrors the classical phase transition in the Erdős-Rényi random graph (Formula presented.) chosen uniformly at random from all graphs with vertex set (Formula presented.) and (Formula presented.) edges. It takes place at (Formula presented.), when the giant component emerges. The second phase transition occurs at (Formula presented.), when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from (Formula presented.) and has only been observed for graphs on surfaces.

Original languageEnglish
Pages (from-to)1117-1170
Number of pages54
JournalRandom Structures & Algorithms
Volume56
Issue number4
Early online date13 Jan 2020
DOIs
Publication statusPublished - 2020

Keywords

  • giant component
  • graphs on surfaces
  • phase transition
  • random graphs

ASJC Scopus subject areas

  • Software
  • Applied Mathematics
  • General Mathematics
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Phase transitions in graphs on orientable surfaces'. Together they form a unique fingerprint.

Cite this