arXiv Analytics

Sign in

arXiv:1203.3079 [math.CO]AbstractReferencesReviewsResources

On the diameter of random planar graphs

Guillaume Chapuy, Éric Fusy, Omer Giménez, Marc Noy

Published 2012-03-14, updated 2014-01-10Version 2

We show that the diameter D(G_n) of a random labelled connected planar graph with n vertices is equal to n^{1/4+o(1)}, in probability. More precisely there exists a constant c>0 such that the probability that D(G_n) lies in the interval (n^{1/4-\epsilon},n^{1/4+\epsilon}) is greater than 1-\exp(-n^{c\epsilon}) for {\epsilon} small enough and n>n_0(\epsilon). We prove similar statements for 2-connected and 3-connected planar graphs and maps.

Related articles: Most relevant | Search more
arXiv:0811.0949 [math.CO] (Published 2008-11-06, updated 2009-11-30)
On percolation and the bunkbed conjecture
arXiv:1511.07813 [math.CO] (Published 2015-11-24)
2-Xor revisited: satisfiability and probabilities of functions
arXiv:2004.01659 [math.CO] (Published 2020-04-03)
Shuffling and $P$-partitions