On the probability of planarity of a random graph near the critical point

DOI10.1090/S0002-9939-2014-12141-1MaRDI QIDQ5496430zbMATH OpenOpenAlexFDO

Authors Marc Noy, Vlady Ravelomanana, Juanjo Rué

Publication date 2 February 2015

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Consider the uniform random graph $G(n,M)$ with $n$ vertices and $M$ edges. ErdH{o}s and R'enyi (1960) conjectured that the limit ${\displaystyle }$ lim_{n o infty} Pr{G(n, extstyle{nover 2}) is planar}} ${\displaystyle }$ exists and is a constant strictly between 0 and 1. L uczak, Pittel and Wierman (1994) proved this conjecture and Janson, L uczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact probability of a random graph being planar near the critical point $M=n/2$. For each $lambda$, we find an exact analytic expression for ${\displaystyle }$ p(lambda) = lim_{n o infty} Pr{G(n, extstyle{nover 2}(1+lambda n^{-1/3})) is planar}.${\displaystyle }$ In particular, we obtain $p(0)approx0.99780$. We extend these results to classes of graphs closed under taking minors. As an example, we show that the probability of $G(n,extstylenover2)$ being series-parallel converges to 0.98003. For the sake of completeness and exposition we reprove in a concise way several basic properties we need of a random graph near the critical point.

Recommendations

• The probability of planarity of a random graph near the critical point
• The Structure of a Random Graph at the Point of the Phase Transition
• The evolution of uniform random planar graphs
• scientific article; zbMATH DE number 4183464
• Random planar graphs

Cites work

• Airy phenomena and analytic combinatorics of connected graphs
• Analytic combinatorics
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 4038891 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Random cubic planar graphs
• The birth of the giant component
• The Evolution of Random Graphs
• The first cycles in an evolving graph
• The number of connected sparsely edged graphs. III. Asymptotic results
• The number of graphs not containing \(K_{3,3}\) as a minor
• The number of trees
• The scaling window of the 2-SAT transition
• The Structure of a Random Graph at the Point of the Phase Transition
• Two critical periods in the evolution of random planar graphs

Cited in

(17)

• Cubic graphs and related triangulations on orientable surfaces
• Random planar maps and graphs with minimum degree two and three
• Cycles of given lengths in unicyclic components in sparse random graphs
• Spanning trees in random series-parallel graphs
• Concentration of maximum degree in random planar graphs
• The mesoscopic geometry of sparse random maps
• Two critical periods in the evolution of random planar graphs
• The Structure of a Random Graph at the Point of the Phase Transition
• Subcritical graph classes containing all planar graphs
• The genus of the Erdős-Rényi random graph and the fragile genus property
• Phase transitions in graphs on orientable surfaces
• Expected Maximum Block Size in Critical Random Graphs
• The probability of planarity of a random graph near the critical point
• Longest and shortest cycles in random planar graphs
• Random cubic planar graphs converge to the Brownian sphere
• Canonical labeling of sparse random graphs
• Heuristics for exact 1-planarity testing

This page was built for publication: On the probability of planarity of a random graph near the critical point

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