6
$\begingroup$

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?

$\endgroup$

3 Answers 3

4
$\begingroup$

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....

$\endgroup$
3
  • $\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$ Jul 23, 2012 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$ Jul 23, 2012 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$ Jul 23, 2012 at 19:42
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Very nice! In particular, page 5 of the second reference addresses the question of the average size of a maximal matching. $\endgroup$ Jan 29, 2014 at 13:03
2
$\begingroup$

The results already mentioned show, at least implicitly, that $\sigma(n,m)$ can be computed efficiently.

But there is a simple characterisation that, as far as I know, might have been overlooked until now (please inform me if I'm the one who overlooked something!):

Roll an $n$-sided die repeatedly, and let $k$ be the largest number such that the first $n-k$ throws produce at least $k$ different numbers. Then $k$ has the same random distribution as the matching number of a uniformly chosen tree on $n$ labelled vertices.

This gives an expression for $\sigma(n,m)$ in terms of Stirling numbers of the second kind:

$$ \sigma(n,m) = \frac{n^{m-2}\cdot n!}{(n-m)!} \cdot \left(\genfrac\{\}{0pt}{}{n-m}{m} + (n-m)\cdot\genfrac\{\}{0pt}{}{n-m-1}{m}\right) $$

In my new paper Slither code and the independence number of a random tree I give a proof based on tweaking the Prüfer correspondence to something I call "slither code". Notice that the independence number of a tree is the number of vertices minus the matching number.

$\endgroup$

Your Answer

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

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