4
$\begingroup$

Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$, the following fact is well known:

\begin{eqnarray} Pr [G\mbox{ has a Hamiltonian cycle}]= \begin{cases} 1 & (c(n)\rightarrow \infty) \\ 0 & (c(n)\rightarrow - \infty) \\ e^{-e^{-c}} & (c(n)\rightarrow c) \end{cases} \end{eqnarray}

That is, a probability $p=\ln n (1+o(1)) / n$ is enough to get an Hamiltonian cycle.

For a given parameter $k\in\{1,\ldots,n\}$, I'm wondering what is the critical probability $p$ for which it's likely that the graph will have a $k$-path.

It seems that $p=\ln k(1+o(1)) / k$ is too high, as we only need one simple path of length $k$ in an $n$-nodes graph.

$\endgroup$
2
$\begingroup$

When $k$ is a constant, the threshold probability for a path of length $k$ is $p \sim \dfrac{1}{n^{1+1/k}}$. The same is true for any tree with $k$ edges. The general result is that the threshold probability for the appearance of a subgraph $H$ is $max_{J \subseteq H} n^{-|V(J)|/E(J)|}$, which happens to be the same as $n^{-|V(H)|/E|(H)|}$ for balanced graphs $H$ (such as trees, complete graphs, cycles).

The situation is different when $k$ grows with $n$. I don't know what the threshold is, but looking at the Hamiltonian path case, I'd guess that an extra $\log n$ factor suffices.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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