  Consider a stationary sequence $X=(X_n)$ of integer-valued random variables
with mean $m \in [-\infty, \infty]$. Let $S=(S_n)$ be the stochastic process
with increments $X$ and such that $S_0=0$. For each time $i$, draw an edge from
$(i,S_i)$ to $(j,S_j)$, where $j>i$ is the smallest integer such that $S_j \geq
S_i$, if such a $j$ exists. This defines the record graph of $X$.
  It is shown that if $X$ is ergodic, then its record graph exhibits the
following phase transitions when $m$ ranges from $-\infty$ to $\infty$. For
$m<0$, the record graph has infinitely many connected components which are all
finite trees. At $m=0$, it is either a one-ended tree or a two-ended tree. For
$m>0$, it is a two-ended tree.
  The distribution of the component of $0$ in the record graph is analyzed when
$X$ is an i.i.d. sequence of random variables whose common distribution is
supported on $\{-1,0,1,\ldots\}$, making $S$ a skip-free to the left random
walk. For this random walk, if $m<0$, then the component of $0$ is a unimodular
typically re-rooted Galton-Watson Tree. If $m=0$, then the record graph rooted
at $0$ is a one-ended unimodular random tree, specifically, it is a unimodular
Eternal Galton-Watson Tree. If $m>0$, then the record graph rooted at $0$ is a
unimodularised bi-variate Eternal Kesten Tree.
  A unimodular random directed tree is said to be record representable if it is
the component of $0$ in the record graph of some stationary sequence. It is
shown that every infinite unimodular ordered directed tree with a unique
succession line is record representable. In particular, every one-ended
unimodular ordered directed tree has a unique succession line and is thus
record representable.
