Phase transitions in graphs on orientable surfaces

DOI10.1002/RSA.20900zbMATH Open1451.05213arXiv1708.07671OpenAlexW2999511073WikidataQ126355212 ScholiaQ126355212MaRDI QIDQ5128754FDOQ5128754

Authors: Mihyun Kang, M. Moßhammer, Philipp Sprüssel 

Publication date: 26 October 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Let $mathbb{S}_g$ be the orientable surface of genus $g$. We prove that the component structure of a graph chosen uniformly at random from the class $mathcal{S}_g(n,m)$ of all graphs on vertex set $[n]=1,dotsc,n$ with $m$ edges embeddable on $mathbb{S}_g$ features two phase transitions. The first phase transition mirrors the classical phase transition in the ErdH{o}s--R'enyi random graph $G(n,m)$ chosen uniformly at random from all graphs with vertex set $[n]$ and $m$ edges. It takes place at $m=fracn2+O(n^{2/3})$, when a unique largest component, the so-called emph{giant component}, emerges. The second phase transition occurs at $m=n+O(n^{3/5})$, when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from $G(n,m)$ and has only been observed for graphs on surfaces. Moreover, we derive an asymptotic estimation of the number of graphs in $mathcal{S}_g(n,m)$ throughout the regimes of these two phase transitions.

Full work available at URL: https://arxiv.org/abs/1708.07671

Recommendations

• Evolution of the giant component in graphs on orientable surfaces
• The Evolution of Random Graphs on Surfaces
• The evolution of random graphs on surfaces
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Random graphs on surfaces

zbMATH Keywords

phase transitionrandom graphsgraphs on surfacesgiant component

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two critical periods in the evolution of random planar graphs
• Asymptotic enumeration and limit laws of planar graphs
• Random cubic planar graphs
• The birth of the giant component
• On the probability of planarity of a random graph near the critical point
• A Census of Planar Maps
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Sudden emergence of a giant \(k\)-core in a random graph
• Title not available (Why is that?)
• On the Maximum Degree of a Random Planar Graph
• Component behavior near the critical point of the random graph process
• Degree distribution in random planar graphs
• Random planar graphs
• Inverse Relations and Combinatorial Identities
• Asymptotic normality of the \(k\)-core in random graphs
• Asymptotic enumeration and limit laws for graphs of fixed genus
• The order of the giant component of random hypergraphs
• The transitive closure of a random digraph
• The Evolution of Random Graphs
• Thek-Core and Branching Processes
• Poisson Cloning Model for Random Graphs
• On the degree distribution of random planar graphs
• Random graphs on surfaces
• Boltzmann Samplers, Pólya Theory, and Cycle Pointing
• Random planar graphs with \(n\) nodes and a fixed number of edges
• Maximal biconnected subgraphs of random planar graphs
• 3-Connected Cores In Random Planar Graphs
• Uniform random sampling of planar graphs in linear time
• Random planar graphs with given average degree
• On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs
• On the Number of Edges in Random Planar Graphs
• The maximum degree of random planar graphs
• On properties of random dissections and triangulations
• The Structure of a Random Graph at the Point of the Phase Transition
• The random planar graph process
• Counting connected graphs inside-out
• Size and connectivity of the \(k\)-core of a random graph
• Generating unlabeled connected cubic planar graphs uniformly at random
• Generating labeled planar graphs uniformly at random
• Asymptotic normality of the size of the giant component via a random walk
• Random sampling of large planar maps and convex polyhedra
• A simple branching process approach to the phase transition in \(G_{n,p}\)
• Local limit theorems for the giant component of random hypergraphs
• Cubic graphs and related triangulations on orientable surfaces
• Exploring hypergraphs with martingales
• Title not available (Why is that?)
• Limit Distributions of the Height of a Random Forest
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Longest and shortest cycles in random planar graphs
• Cut vertices in random planar graphs
• The evolution of random graphs on surfaces of non-constant genus
• The Evolution of Random Graphs on Surfaces
• Concentration of maximum degree in random planar graphs
• Classes of graphs embeddable in order-dependent surfaces
• Evolution of the giant component in graphs on orientable surfaces

This page was built for publication: Phase transitions in graphs on orientable surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128754)