Two point concentration of maximum degree in sparse random planar graphs

2020/10/28 by Mihyun Kang, Kang, Mihyun, Michael Missethan +1
Mathematics · Computer Science · #Stochastic processes and statistical mechanics #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2010.15083

Abstract

Let P(n,m) be a graph chosen uniformly at random from the class of all planar graphs on vertex set \1, …, n\ with m=m(n) edges. We show that in the sparse regime, when \limsup_{n → ∞} m/n<1, with high probability the maximum degree of P(n,m) takes at most two different values.

Related

• Concentration of maximum degree in random planar graphs
• Local limit of sparse random planar graphs
• Uniform Random Planar Graphs with Degree Constraints
• The maximum degree of planar graphs I. Series-parallel graphs
• A concentration inequality for the maximum vertex degree in random dissections