  An independent set of size $k$ in a finite undirected graph $G$ is a set of
$k$ vertices of the graph, no two of which are connected by an edge. Let
$x_{k}(G)$ be the number of independent sets of size $k$ in the graph $G$ and
let $\alpha(G)=\max\{k\geq0\colon x_{k}(G)\neq0\}$. In 1987, Alavi, Malde,
Schwenk and Erd\"{o}s asked if the independent set sequence
$x_{0}(G),x_{1}(G),\ldots,x_{\alpha(G)}(G)$ of a tree is unimodal (the sequence
goes up and then down). This problem is still open. In 2006, Levit and
Mandrescu showed that the last third of the independent set sequence of a tree
is decreasing. We show that the first 46.8\% of the independent set sequence of
a random tree is increasing with (exponentially) high probability as the number
of vertices goes to infinity. So, the question of Alavi, Malde, Schwenk and
Erd\"{o}s is ``four-fifths true'', with high probability.
  We also show unimodality of the independent set sequence of Erd\"{o}s-Renyi
random graphs, when the expected degree of a single vertex is large (with
(exponentially) high probability as the number of vertices in the graph goes to
infinity, except for a small region near the mode). A weaker result is shown
for random regular graphs.
  The structure of independent sets of size $k$ as $k$ varies is of interest in
probability, statistical physics, combinatorics, and computer science.
