  Let $G$ be a graph $G$ whose largest independent set has size $m$. A
permutation $\pi$ of $\{1, \ldots, m\}$ is an {\em independent set permutation}
of $G$ if $$ a_{\pi(1)}(G) \leq a_{\pi(2)}(G) \leq \cdots \leq a_{\pi(m)}(G) $$
where $a_k(G)$ is the number of independent sets of size $k$ in $G$. In 1987
Alavi, Malde, Schwenk and Erd\H{o}s proved that every permutation of $\{1,
\ldots, m\}$ is an independent set permutation of some graph with
$\alpha(G)=m$, i.e. with largest independent set having size $m$. They raised
the question of determining, for each $m$, the smallest number $f(m)$ such that
every permutation of $\{1, \ldots, m\}$ is an independent set permutation of
some graph with $\alpha(G)=m$ and with at most $f(m)$ vertices, and they gave
an upper bound on $f(m)$ of roughly $m^{2m}$. Here we settle the question,
determining $f(m)=m^m$, and make progress on a related question, that of
determining the smallest order such that every permutation of $\{1, \ldots,
m\}$ is the {\em unique} independent set permutation of some graph of at most
that order. More generally we consider an extension of independent set
permutations to weak orders, and extend Alavi et al.'s main result to show that
every weak order on $\{1, \ldots, m\}$ can be realized by the independent set
sequence of some graph with $\alpha(G)=m$ and with at most $m^{m+2}$ vertices.
  Alavi et al. also considered {\em matching permutations}, defined analogously
to independent set permutations. They observed that not every permutation of
$\{1,\ldots,m\}$ is a matching permutation of some graph with largest matching
having size $m$, putting an upper bound of $2^{m-1}$ on the number of matching
permutations of $\{1,\ldots,m\}$. Confirming their speculation that this upper
bound is not tight, we improve it to $O(2^m/\sqrt{m})$.
