MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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: – Brendan McKay Feb 15 '12 at 22:27
@Gerhard: And here is a nice self-contained proof: – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.