On 18/02/2013 18:06, Dan Asimov wrote:
On 2013-02-18, at 5:14 AM, Robert Baillie wrote:
what is the probability that a graph this size is planar? does that question even make sense?
With the number of vertices fixed at N, each of the N-choose-2 pairs of vertices could be considered to be an edge with probability ½ (or more generally p).
If you use probability 1/2, the probability is very small -- planar graphs have to be very sparse. (Add enough edges to make the graph a triangulation; then Euler's formula kinda says that the average degree is about 6.) Erdos and Renyi proved that if you take a random graph with n vertices and n/2 + k n^2/3 edges, there's a nonzero probability that it's not planar. Noy, Ravelomanana and Rue found an explicit formula for the limiting probability as n->oo, as a function of k. When k=0 the probability of planarity is about 0.998. As k->oo the probability of planarity goes to 0. (So, in particular, if you take p = c/n for c>1 then the probability that the graph is planar -> 0 as n -> oo.) I am not an expert on any of this stuff; I just looked it up :-). -- g