- Series
- Graph Theory Seminar
- Time
- Thursday, April 18, 2019 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- David Galvin – University of Notre Dam
- Organizer
- Xingxing Yu

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.