Georgia Institute of Technology College of Sciences

To any finite real sequence, we can associate a permutation $\pi$, via: $\pi(k)$ is the index of the $k$th smallest element of the sequence. This association was introduced in a 1987 paper of Alavi, Malde, Schwenk and Erd\H{o}s, where they used it to study the possible patterns of rises and falls that can occur in the matching sequence of a graph (the sequence whose $k$th term is the number of matchings of size $k$), and in the independent set sequence. The main result of their paper was that {\em every} permutation can arise as the ``independent set permutation'' of some graph. They left open the following extremal question: for each $n$, what is the smallest order $m$ such that every permutation of $[n]$ can be realized as the independent set permutation of some graph of order at most $m$? We answer this question. We also improve Alavi et al.'s upper bound on the number of permutations that can be realized as the matching permutation of some graph. There are still many open questions in this area. This is joint work with T. Ball, K. Hyry and K. Weingartner, all at Notre Dame.