Unimodality (and otherwise) of some graph theoretic sequences

Combinatorics Seminar
Wednesday, December 15, 2010 - 10:05
1 hour (actually 50 minutes)
Skiles 255
Mathematics, University of Notre Dame
The matching sequence of a graph is the sequence whose $k$th term counts the number of matchings of size $k$. The independent set (or stable set) sequence does the same for independent sets. Except in very special cases, the terms of these sequences cannot be calculated explicitly, and one must be content to ask questions about global behavior. Examples of such questions include: is the sequence unimodal? is it log-concave? where are the roots of its generating function? For the matching sequence, these questions are answered fairly completely by a theorem of Heilmann and Lieb. For the independent set sequence, the situation is less clear. There are some positive results, one startling negative result, and a number of basic open questions. In this talk I will review the known results, and describe some recent progress on the questions.