4
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 15, 2012 at 22:02
  • $\begingroup$ 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 $\endgroup$ Feb 15, 2012 at 22:10
  • $\begingroup$ @Gerhard: They are unimodal and even log-concave. This consequence and others are cited in this thesis: math.kth.se/~pbranden/Avhandling.pdf $\endgroup$ Feb 15, 2012 at 22:27
  • $\begingroup$ @Gerhard: And here is a nice self-contained proof: mat.univie.ac.at/~kratt/artikel/matching.html $\endgroup$ Feb 15, 2012 at 22:32
  • $\begingroup$ Thank you. Let's see if my smartphone can handle dvi format. Gerhard "Or Try A Different Box" Paseman, 2012.02.15 $\endgroup$ Feb 15, 2012 at 22:40

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.