Erdős Problem 900: long paths in a sparse random graph
Statement and result.
For every fixed $c>1/2$, the uniform random graph $G(n,\lfloor cn\rfloor)$ has with probability tending to one a path of at least $f(c)n$ edges, for a positive function with \[
f(c)\longrightarrow0\ (c\downarrow1/2),\qquad
f(c)\longrightarrow1\ (c\to\infty).
\] We reconstruct a depth-first-search proof for the first claim and give a separate elementary estimate for large $c$. Standard binomial concentration is the only probabilistic estimate used beyond union bounds.
Two search invariants.
Depth-first search partitions the vertices into a finished set $S$, a stack $U$, and an undiscovered set $T$. The stack is always a simple path. Every pair in $S\times T$ has already been queried and found to be a nonedge. When the stack is empty, an undiscovered vertex starts a new search. Every positive answer to an edge query discovers a new vertex, so the number of discoveries $|S|+|U|$ is at least the number of positive answers. In $G(n,p)$, the answers to successive previously unqueried edges are independent Bernoulli variables with parameter $p$, even though the search chooses its queries adaptively.
A quantitative supercritical bound.
Fix $0<\epsilon\leq1/8$, set $p=(1+\epsilon)/n$, $u=\epsilon^2n/16$, and $t_0=\lfloor\epsilon n^2/2\rfloor$. Suppose, towards a contradiction, that the search stack always has size at most $u$. By the first time $|S|=\lceil\epsilon n\rceil$, the number of queries is at least \[
|S||T|\geq(\epsilon n+O(1))
(n-\epsilon n-u-O(1))>t_0.
\] Thus the search makes $t_0$ queries, and at that time $|S|\leq\epsilon n+O(1)$. The sum of their Bernoulli answers has mean $(\epsilon/2+\epsilon^2/2)n+O(1)$. A Chernoff bound gives, with probability tending to one, at least $(\epsilon/2+3\epsilon^2/8)n$ positive answers. Hence at that time \[
|S|\geq s_0n,\qquad s_0=\epsilon/2+5\epsilon^2/16.
\] For $s\leq\epsilon n+O(1)$ the function $s(n-s-u)$ is increasing, so the already queried pairs in $S\times T$ number at least \[
s_0(1-s_0-\epsilon^2/16)n^2
=\left(\frac\epsilon2+\frac{\epsilon^2}{16}
-\frac{11\epsilon^3}{32}
-\frac{15\epsilon^4}{128}\right)n^2
>t_0.
\] The strict inequality holds for every $0<\epsilon\leq1/8$. This contradicts the definition of $t_0$. Therefore a stack of more than $u$ vertices occurs, and for sufficiently large $n$ it gives a path with at least $\epsilon^2n/32$ edges.
Transfer to a fixed number of edges.
For given $c>1/2$, choose \[
\epsilon(c)=\min((2c-1)/2,1/8).
\] Then $(1+\epsilon(c))/2<c$. Choose a uniform random ordering of all possible edges and an independent binomial number $K$ of edges with parameters $\binom n2,(1+\epsilon(c))/n$. The first $K$ edges have distribution $G(n,p)$; the first $\lfloor cn\rfloor$ have the uniform fixed-size distribution. Concentration gives $\Pr(K\leq\lfloor cn\rfloor)\to1$, so the path just proved persists in the latter graph.
A path occupying nearly all vertices when $c$ is large.
Put $\alpha=c^{-1/3}$ and $r=\lceil\alpha n\rceil$. For fixed disjoint $r$-sets $X,Y$, the probability that the uniform graph has no edge between them is at most \[
\left(1-\frac{r^2}{\binom n2}\right)^{\lfloor cn\rfloor}
\leq \exp(-(2c\alpha^2+o(1))n).
\] There are at most $3^n$ ordered disjoint pairs of subsets. For fixed $c\geq64$, the union bound therefore shows that every such pair has a connecting edge, with high probability. In depth-first search, consider the instant $|S|=r$. There can then be fewer than $r$ vertices in $T$, since there are no edges from $S$ to $T$. The stack has more than $n-2r$ vertices. For large $n$ it gives a path with at least $(1-3c^{-1/3})n$ edges.
An explicit admissible function and attribution.
Take \[
f(c)=
\begin{cases}
\epsilon(c)^2/32,&1/2<c<64,\\
1-3c^{-1/3},&c\geq64.
\end{cases}
\] It has both required limits and is positive everywhere. The original resolution is due to Ajtai, Komlós and Szemerédi. The search method above follows Krivelevich and Sudakov,
The phase transition in random graphs---a simple proof,
https://arxiv.org/abs/1201.6529, with conservative constants and the model-transfer argument written out. See
https://www.erdosproblems.com/900, checked 24 September 2026. This is a complete reconstruction, not a novel result or a local formal verification.
Completion estimate.
COMPLETION: 100%