2
$\begingroup$

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 ?

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

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.

|cite|improve this answer
$\endgroup$
  • $\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

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.