  Given a graph $G$ and a bijection $f : E(G)\rightarrow \{1, 2,
\ldots,e(G)\}$, we say that a trail/path in $G$ is $f$-\emph{increasing} if the
labels of consecutive edges of this trail/path form an increasing sequence.
More than 40 years ago Chv\'atal and Koml\'os raised the question of providing
the worst-case estimates of the length of the longest increasing trail/path
over all edge orderings of $K_n$. The case of a trail was resolved by Graham
and Kleitman, who proved that the answer is $n-1$, and the case of a path is
still widely open. Recently Lavrov and Loh proposed to study the average case
of this problem in which the edge ordering is chosen uniformly at random. They
conjectured (and it was proved by Martinsson) that such an ordering with high
probability (whp) contains an increasing Hamilton path.
  In this paper we consider random graph $G=G(n,p)$ and its edge ordering
chosen uniformly at random. In this setting we determine whp the asymptotics of
the number of edges in the longest increasing trail. In particular we prove an
average case of the result of Graham and Kleitman, showing that the random edge
ordering of $K_n$ has whp an increasing trail of length $(1-o(1))en$ and this
is tight. We also obtain an asymptotically tight result for the length of the
longest increasing path for random Erd\H{o}-Renyi graphs with $p=o(1)$.
