1
$\begingroup$

According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is a necessary condition for planarity) is: $$2^{-n(n-1)/2}\sum_{k=0}^{3n-6}{n(n-1)/2\choose k}$$

Therefore, the plot for this equation is:

enter image description here

If I choose a random graph with 10 vertices, what is the probability that it will remain planar after adding an edge between two randomly chosen vertices?

To be more clear:

Consider event $P_{1}$, the event of choosing a planar graph $G_{1}$ in the universe $U_{10}$ of graphs with 10 vertices.

Consider a subset $S$ of the universe of graphs with 11 vertices $U_{11}$ conditionally defined by the graph $G_{1}$ we got in event $P_{1}$ in this way: $S$ is formed by all possible graphs that can result from adding one edge to $G_{1}$.

And then finally consider event $P_{2}$, the event of choosing a planar graph in the universe $S$ defined in the previous step.

Therefore I want to know what is the probability of event $P_{2}$.

Possible solution:

I followed D.W.'s advice below and wrote a small simulation. According to the code, the probability of choosing a planar graph of 10 vertices is 0.0915 ( 9,15% ) and the probability of a given planar graph of 10 vertices remaining planar after adding one random edge is 0.6140 ( 61,40% ).

#!/usr/bin/python3
import planarity
from itertools import combinations
import random
from multiprocessing import Process, Manager, Pool, cpu_count
import json

nodes = [str(x) for x in range(10)]
edges = list(combinations(nodes,2))
tests = 10**6
filename = 'results.json'
runs = 100

def make_test():
    while 1:
        chosen_edges = list(filter(lambda x: x != None, [x if random.choice([0,1]) else None for x in edges]))
        if planarity.is_planar(chosen_edges):
            break
    extra_edge = random.choice( list(set(edges) - set(chosen_edges)) )
    chosen_edges += [extra_edge]
    return planarity.is_planar(chosen_edges)

if __name__ == '__main__':

    for i in range(runs):
        with Pool(processes=cpu_count()) as pool:
            results = [ pool.apply_async(make_test, ()) for i in range(tests) ]
            lst = [ res.get(timeout=1) for res in results ]
        pool.close()
        pool.join()

        n = len(lst)
        p = len(list(filter(lambda x: x != False, lst)))
        prob = ( p / n )
        print(prob)

        try:
            with open(filename,'r') as f:
                file_lst = json.load(f)
        except:
            open(filename,'w+').close()
            file_lst = []
        file_lst += [prob]
        with open(filename,'w') as f:
            json.dump(file_lst,f)
$\endgroup$
  • $\begingroup$ I'm afraid $n = 10$ is a little small for experiments. $\endgroup$ – Yuval Filmus Aug 12 '18 at 2:27
4
$\begingroup$

Let $S$ be the set of planar graphs on $n$ vertices, and let $E(S,\overline{S})$ be the set of edges between $S$ and its complement, that is, the set of pairs $(G,e)$ where $G \in S$ and $G \cup \{e\} \notin S$. The edge-isoperimetric inequality states that $$ \frac{|E(S,\overline{S})|}{|S|} \geq \binom{n}{2} - \log_2 |S|. $$ It follows that the probability that you're after is at most $$ \frac{\log_2 |S|}{\binom{n}{2}-(3n-6)}. $$ It is known that $\log_2 |S| = O(n \log n)$ (see for example Gimenez and Noy, The number of planar graphs and properties of random planar graphs, and so we conclude that your probability is at most $O\left(\frac{\log n}{n}\right)$.

On the other hand, the same paper shows that with constant probability, a random planar graph has an isolated vertex. When this happens, there is $\Omega\left(\frac{1}{n}\right)$ probability to add an edge adjacent to it, leaving the graph planar. Hence your probability is at least $\Omega\left(\frac{1}{n}\right)$.

$\endgroup$
0
$\begingroup$

I don't know that you're going to find an explicit formula. (You don't even seem to have a formula for the probability that a random graph on 10 vertices is planar, let alone the more complex random process you describe. The formula you give is merely an upper bound for the probability of being planar, not a formula for that probability.)

But you can easily estimate this probability through simulation. Generate 1 million random graphs using this procedure, and test whether the result is planar. Then the fraction that were planar is a good estimate of the underlying probability. That should be easy to code up and fast to run.

$\endgroup$
  • $\begingroup$ I added a simulation to the question. According to the code, the probability of choosing a planar graph of 10 vertices is 0.0915 ( 9,15% ) and the probability of a given planar graph of 10 vertices remaining planar after adding one random edge is 0.6140 ( 61,40% ). $\endgroup$ – Ruan Aug 11 '18 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.