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.
Comments: 24 pages, 7 figures
Categories: math.CO
Related articles: Most relevant | Search more
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