<p>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). </p>

<p>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.</p>

CC BY-SA 4.0
2018-06-20T07:46:27.927Z
2018-06-20T07:46:27.927Z
Aravind
<p>Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$,
the following fact is well known:</p>

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

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

<p>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.</p>

<p>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.</p>

<graph-theory><co.combinatorics><pr.probability><random-graphs>
Probability of a $k$-path in a random graph
R B
# Probability of a $k$-path in a random graph

(Asked by: username_0 on 2018-06-19)

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.

**Tags:** graph-theory, co.combinatorics, pr.probability, random-graphs

---

## 1 answers

### Answer by username_1 on 2018-06-20. Score: 2 | Accepted answer

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.


---

