Length of longest path in Erdos Renyi graph Is it possible to compute the expected length of the longest simple path in an Erdos-Renyi graph or even the probability density function of this length?  
 A: While it may be hard to get an exact distribution, there are results giving asymptotic information on the length of the longest path.  


*

*If $p=\frac{c}{n}$ where $c<1$, then the largest component in the graph with high probability has size $O(\log n)$, so there almost surely won't be a path longer than this.

*If $p=\frac{c}{n}$, where $c>1$ is constant, then there is with high probability a path containing $\alpha n$ vertices, where $\alpha>0$ depends on $c$ (Ajtai-Komlós-Szemerédi 's 1981 paper "The Longest Path in a Random Graph")

*Alan Frieze sharpened this result, showing that there is with high probability  a cycle containing all but $(1+o_c(1))ce^{-c} n$ vertices, 
where the $o_c(1)$ notation here means that as $c$ tends to infinity that term tends to $0$.  For large $c$ this is essentially tight -- the graph contains roughly $ce^{-c} n$ vertices of degree $1$, and your path can't contain more than $2$ of them.  This result was later extended to directed graphs by Krivelevich, Lubetsky, and Sudakov.

*If $p=\frac{\ln n + \ln \ln n + \omega(1)}{n}$, where $\omega(1)$ is any function tending to infinity with $n$, then the graph almost surely has a Hamiltonian cycle (see linked paper in mr. gondolier's comment for a stronger result along these lines)

