Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.

I have been trying to compute the value of $\sigma(n,m)$ but I have been unsuccessful. It looks hard. Is it known? Any idea or suggestion about how can $\sigma$ be computed? Or any good bounds?


If $n=2m$, the answer is $2^{m-2} m! \binom{2m}{m} m^{m-2}$. Let $T_m = \sigma(n,m)$. We go through several transformations. We write $[n]$ for the set $\{ 1,2,\ldots, n \}$ and $[a,b]$ for $\{ a, a+1, \ldots, b \}$.

$T_m$ number of fully matched trees on $[2m]$.

$2 T_m$ number of fully matched trees on $[2m]$ equipped with a bipartite coloring.

$\frac{2}{\binom{2m}{m}} T_m$ number of fully matched trees where $[1,m]$ is colored white and $[m+1, 2m]$ is colored black.

$\frac{2}{m! \binom{2m}{m}} T_m$ number of fully matched trees on $[2m]$ where $i$ is matched to $m+i$.

So we need to show that the last number is $2^{m-1} m^{m-2}$. Let $U$ be one of the objects counted by the last number, and let $V$ be the tree on $[m]$ obtained by contracting the matched edges and labeling the contraction of $(i, i+m)$ by $i$. We claim that every tree $V$ on $[m]$ has $2^{m-1}$ preimages under this map. Proof: To reconstruct $U$ from $V$, for every edge $(i,j)$ of $V$, we must choose whether to join $i$ to $j+m$ or $j$ to $i+m$. This is $m-1$ independent binary choices. $\square$

I don't have any good ideas about $n>2m$, but my basic ideas would be (1) see if you can use Hall's marriage theorem to give a simple description of when a matching is maximal (2) write some code to generate a table of values, and see whether it appears in Sloane's encyclopedia of integer sequences. Looking up a table in Sloane is a bit of a black art. You should try entering several different diagonals, entering individual rows forwards and backwards, looking up any other sequences that come up in restating the problem (for example, Sloane's doesn't list $T_m$ but it does have $\frac{2}{m! \binom{2m}{m}} T_m$). I'd also factor some of the large entries in my table; if all of the prime factors of $\sigma(n,m)$ are $\leq 4n$, it seems likely there is a product formula; if not, I'd bet against it. Hmmm, this might make a good blogpost....

  • $\begingroup$ Thanks David, consider the probability space where all the labelled trees with n vertices are equally likely. Would it be a harder question: what's the expected matching number of a random tree? Is there any paper solving that? $\endgroup$ – Patt Geffrey Jul 23 '12 at 18:35
  • 2
    $\begingroup$ Probably an easier one: I would expect determining the expected value to be easier than determining the whole probability distribution. I have never thought about this before, but a quick google turns up Section 6 of arxiv.org/abs/0903.3589 which seems to have relevant things to say. $\endgroup$ – David E Speyer Jul 23 '12 at 19:41
  • 2
    $\begingroup$ One paper addressing the expected matching number is "On the Kernel of Tree Incidence Matrices" by Bauer and Golinelli (arxiv.org/abs/cond-mat/0003049 ). Their original goal was to study the expected multiplicity of $0$ as an eigenvalue of the adjacency matrix of a random tree, but the rank of the adjacency matrix is equal to twice the size of the maximum matching (removing a leaf and its neighbor from a tree reduces the maximum matching by $1$ and the rank by $2$). $\endgroup$ – Kevin P. Costello Jul 23 '12 at 19:42

This can be done using the canonical coloring of vertices of trees into 3 colors that can be found in

Let me briefly define this coloring (using my own choice of colors). A vertex is

  • red if it belongs to all maximum independent sets
  • orange if it belongs to some max. indep. sets but not to all of them
  • green if it belongs to no max. indep. set

Then it turns out that this has something to do with maximum matchings too. In particular, the number of vertices not covered by a maximum matching is # red vertices - # green vertices.

Using a description of this coloring by local rules, one can write functional equations for the generating series of trees according to the color of their vertices.

  • $\begingroup$ Very nice! In particular, page 5 of the second reference addresses the question of the average size of a maximal matching. $\endgroup$ – David E Speyer Jan 29 '14 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.