# Bounds on numbers of matchings of given sizes in bipartite graphs

I am interested in the following question:

For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for each $1\leq i \leq k$, and no matchings larger than $k$?

Ideally I would like to find a complete classification of such sets, or else an algorithm which, given a set of numbers, will (theoretically) construct a bipartite graph with the desired properties if one exists. However, I realise that this is highly unlikely! In which case, I would like to know as much as possible about the restrictions on such sets.

For example, assume that our desired graph consists of two disjoint sets $A$ and $B$ of vertices with edges between them, such that $|A|\leq |B|$, and such that there are no completely unconnected vertices. Then $|A|=k$. As $m_1$ is simply the number of edges of the graph, we must have $m_1\geq k$ and $m_i\leq {m_1 \choose i}$ for all $i$.

This is just off the top of my head; I'm sure there are many more restrictions which can be easily found. Does anyone know to what extent this problem has been studied? I'd be grateful for any information or references.

-
One strong condition is that if you make a polynomial whose coefficients are these counts, then it has only real zeros. This was proved long ago by Heilmann and Lieb. Godsil's book on algebraic combinatorics is a place to look for this type of thing. I very much doubt that a complete classification is possible. – Brendan McKay Feb 15 '12 at 22:02
A nice result would be that the sequence m_i is unimodal. I do not know of a proof or counterexample. Gerhard "Ask Me About System Design" Paseman, 2012.02.15 – Gerhard Paseman Feb 15 '12 at 22:10
@Gerhard: They are unimodal and even log-concave. This consequence and others are cited in this thesis: math.kth.se/~pbranden/Avhandling.pdf – Brendan McKay Feb 15 '12 at 22:27
@Gerhard: And here is a nice self-contained proof: mat.univie.ac.at/~kratt/artikel/matching.html – Brendan McKay Feb 15 '12 at 22:32
Thank you. Let's see if my smartphone can handle dvi format. Gerhard "Or Try A Different Box" Paseman, 2012.02.15 – Gerhard Paseman Feb 15 '12 at 22:40