Given $N$ labeled points in a plane one can construct $2^{N(N-1)/2}$ graphs(Unweighted, undirected) with them. Is there any theorem that gives the probability of choosing at random from these a graph having a Hamiltonian cycle? Does a similar result exist for Eulerian cycles?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ This seems reasonable for Eulerian cycles, since it comes down to parity of vertex degrees. Without a characterization of when graphs support a Hamilton cycle, such a result would surprise me, although there might be bounds corresponding to necessary or sufficient conditions for Hamiltonian cycles. $\endgroup$– Brian HopkinsJan 21, 2015 at 15:14
-
$\begingroup$ I'm am hoping that at least there are some bounds on the probabilities, even if exact results are not known $\endgroup$– biryaniJan 21, 2015 at 15:16
-
$\begingroup$ To compute some initial values of the probability, oeis.org/A003216 gives counts of Hamiltonian graphs by number of vertices up to 11. However, that counts nonisomorphic graphs, which would each appear several times in the construction behind the 2^(n(n-1)/2) count, so there would be more work than just dividing the OEIS numbers by the powers of 2. $\endgroup$– Brian HopkinsJan 21, 2015 at 15:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, a lot of work has been done on these kinds of questions. Choosing a graph on $n$ vertices at random is the same as including each edge in the graph with probability $\frac{1}{2}$, independently of the other edges. You get a more general model of random graphs if you choose each edge with probability $p$. This model is known as $G_{n,p}$.
It turns out that for any constant $p>0$, the probability that $G$ contains a Hamiltonian cycle tends to 1 when $n$ tends to infinity. In fact, this is true whenever $p>\frac{c \log(n)}{n}$ for some constant $c$. In particular this is true for $p=\frac12$, which is the setting that you describe.
Regarding Eulerian cycles, since a Eulerian cycle exists iff the degrees are all even and the probability that a vertex has even degree is about $\frac12$, the probability that there is a Eulerian cycle is about $2^{-n}$.
For further reading, I recommend the book Random Graphs by Bollobas.
