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 language | English |
---|---|
Pages (from-to) | 1117-1170 |
Number of pages | 54 |
Journal | Random Structures & Algorithms |
Volume | 56 |
Issue number | 4 |
Early online date | 13 Jan 2020 |
DOIs | |
Publication status | Published - 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