Chen Wang, Rutgers University

Abstract

To a sequence associate a permutation $pi$, via: $pi(k)$ is the index of the k-th smallest element of the sequence. This association was introduced in 1987 by Alavi, Malde, Schwenk and ErdH{o}s, who 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), as well as in the independent set sequence.

Their main result was that every permutation can arise as the ``independent set permutation'' of some graph. They left open the following extremal question: for each n, what's 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 on Alavi et al.'s upper bound on the number of permutations that can be realized as the matching permutation of some graph. This is joint work with T. Ball, K. Hyry and K. Weingartner, all at Notre Dame