3
$\begingroup$

Matching polynomials are generating functions that tells us the number of $k$-matching (meaning choosing of $k$ independent/non-adjacent edges) in the graph say $G$.

Farrell et al., "On matching coefficients" (1991), has found the explicit formula for the first 4 coefficients of the matching polynomial, $a_0, a_1, a_2, a_3$.

$a_0 = 1$ because there is simply 1 way to choose 0 edges in any graph.

$a_1 = q$ or number of edges in graph G (because it means just choosing 1 out of the total possible no. of edges.)

$a_2 = \displaystyle \binom{q}{2} - \sum_{i=1}^p \binom{d_i}{2}$, where $p$ is number of nodes and $d_i$ is the valency/degree of the node $i$ in a graph $G$. This can be explained as choosing 2 edges from all $q$ edges minus the sum of all sets of edges whereby 2 of them are from the same node (or non-independent edges).

When it comes to $a_3$, however, I am confused about a part of the formula as follows:

$a_3 = \displaystyle \binom{q}{3} - (q-2)\sum_{i=1}^{p} \binom{d_i}{2} + 2\sum_{i=1}^p \binom{d_i}{3} + \sum_{i,j} (d_j - 1) (d_i - 1) - T$ where the last summation is done over all the edges $i,j$ where $i,j$ are nodes in $G$ and $T$ is the number of triangles in $G$.

From the above, I understand that to get $a_3$, we get first choose 3 out of the total $q$ nodes, then subtract the case whereby 2 edges chosen are from the same node multiplied by choosing the remaining 1 edge (since we need 3 edges) from the remaining $(q-2)$ edges. This explains the first 2 terms on the formula.

QUESTION: However, I am totally confused about what the last summation means... Can anyone kindly explain this to me? Thank you very much.

$\endgroup$
4
  • 1
    $\begingroup$ If you are familiar with the inclusion-exclusion principle, then it should not be too surprising that an expression for 3-matchings that begins with $\binom{q}{3}$, i.e. all choices of 3 edges, needs to exclude some of these combinations by subtracting terms. Typically then one needs to add some terms back, because the same excluded choice may have been "subtracted off" more than once. The explanation I would give for this formula would be in that vein. $\endgroup$
    – hardmath
    Commented Sep 26, 2014 at 15:23
  • $\begingroup$ I understand that however I don't understand what the last summation means in this case of $a_3$... Can you explain to me the physical meaning behind this summation ? $\endgroup$
    – Happytreat
    Commented Sep 27, 2014 at 1:27
  • $\begingroup$ @hardmath I have edited my question above because I kind of get the plus 2 of the second last summation (of $d_i$ choose $3$ (Notice I have made a mistake in stating that it is subtracting that summation previously but have edited there formula for $a_3$ above.)) I think I now understand what's going on with the formula... thanks for your comment though :) $\endgroup$
    – Happytreat
    Commented Sep 27, 2014 at 3:28
  • 1
    $\begingroup$ Perhaps the formula is explained in the paper? $\endgroup$ Commented Sep 27, 2014 at 3:29

1 Answer 1

1
$\begingroup$

There are several graphs possible with three edges:

  1. A 3-matching.

  2. A union of a 1-path and a 2-path.

  3. A 3-path.

  4. A 3-star (three edges incident to the same vertex).

  5. A triangle.

Denote by $N(i)$ the number of occurrences of graphs of type $i$ in your graph. We have $$ \begin{align*} \binom{q}{3} &= N(1) + N(2) + N(3) + N(4) + N(5) \\ -(q-2) \sum_i \binom{d_i}{2} &= -N(2) - 2N(3) - 3N(4) - 3N(5) \\ 2 \sum_i \binom{d_i}{3} &= 2N(4) \\ \sum_{i,j \in E} (d_i-1)(d_j-1) &= N(3) + 3N(5) \\ -T &= -N(5) \end{align*} $$ If you sum everything, you get $N(1)$.

$\endgroup$
5
  • $\begingroup$ What do you mean by a union of 1-path and 2-path? $\endgroup$
    – Happytreat
    Commented Sep 27, 2014 at 3:36
  • $\begingroup$ @Happytreat Use your imagination. A $k$-path is a path with $k$ edges. $\endgroup$ Commented Sep 27, 2014 at 3:42
  • $\begingroup$ Oh I see, I have confused that with the 3-paths... $\endgroup$
    – Happytreat
    Commented Sep 27, 2014 at 3:43
  • $\begingroup$ Doesnt the last summation include $N(5)$ too? $\endgroup$
    – Happytreat
    Commented Sep 27, 2014 at 4:36
  • $\begingroup$ And so does the first, so it cancels out. $\endgroup$ Commented Sep 27, 2014 at 4:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .