Let $$p(n):=\frac{\text{number of hamiltonian graphs with $n$ nodes}}{\text{number of graphs with $n$ nodes}}$$

Since $883156024$ of the $1018997864$ graphs with $11$ nodes are hamiltonian, we have $p(11) = 0.8667$. Is it known whether $$\lim_{n\to\infty} p(n) = 1$$

and if yes, is it known how fast this convergence is ?

  • $\begingroup$ Perhaps, it helps, that "almost all" graphs are $2$-connected. $\endgroup$ – Peter Oct 21 '14 at 20:08

The following stronger result is known. Assume that the edges of the graph $G$ with $n$ vertices are drawn in mutually independently with probability $\frac{c\ln n}{n}$. Then, for a sufficiently large $c$, the probability that $G$ contains a Hamiltonian circuit tends to $1$ as $n \to \infty$. This is Theorem 2 from this old paper by Pósa, available online for free.

  • $\begingroup$ I do not see why this result is stronger, but since it is plausible that "allmost all" graphs have $O(n\ ln\ n)$ edges, it should answer my question. $\endgroup$ – Peter Oct 21 '14 at 20:41
  • 3
    $\begingroup$ Note that there are about $\frac 12n^2$ potential edges in a graph with $n$ nodes. Since most graphs have of order half the available edges, we would expect most graphs to have more than $c\frac 14n^2 \gt n \ln n$ edges for any $0 \lt c \lt 1$ once $n$ gets large enough. $\endgroup$ – Ross Millikan Oct 21 '14 at 20:43
  • $\begingroup$ @Peter I edited the answer to make it more clear why does it really answer the question. $\endgroup$ – user2097 Oct 22 '14 at 13:46

Your Answer

