COMBINATORICA1 (3) (1981) 257--262

HERMITE POLYNOMIALS AND A DUALITY RELATION

FOR MATCHINGS POLYNOMIALS

by
C. D. G O D S I L
Institut ffir Mathematik und Angewandte Geometrie
Montanuniversit/it Leoben, Austria
Received 17 July 1980

Let G be a graph on n vertices. A k-matching in G is a set of k independent edges. If 2k=n

then a k-matching is called perfect. The number of k-matchings in G is p(G, k). (We set p(G, 0) = 1).
The matchings polynomial of G is
[n/~]
o~(G,x)= IS (-1)kp(G,k)~ "~-'k.
k=0

Our main result is that the number of perfect matchings in the complement of G is equal to

(1) (2n) -a/2 f c~(G, x) exp (-xZ/2) dx.

Let Km be the complete graph on m vertices. Then a(K,,, x) is the Hermite polynomial He,~(x)
of degree n. Using (1) we show, amongst other results, that
[nI~l
e(d,x) = k=O
22 p(G,k)~(Kn_2k, x).

1. The basic result

1.1. Let G be a g r a p h with vertex set {1, ..., n}. A k-matching in G is a set o f k edges
o f G, no two o f which have a vertex irl c o m m o n . Clearly k ~ n / 2 , if k=n/2 then a
k - m a t c h i n g o f G is called perfect. The n u m b e r o f k - m a t c h i n g s in G will be d e n o t e d
b y p(G, k), with the c o n v e n t i o n t h a t p(G, 0 ) = 1 .
T h e m a t c h i n g s p o l y n o m i a l c~(G)=a(G, x) is
[,/2]
,~ (-- 1)kp(G, k)x "-ek
k=O

This p o l y n o m i a l was first studied, u n d e r the n o t a t i o n Q(G,x), by H e i l m a n n a n d

Lieb in a p a p e r on statistical physics [4]. It arose there as a form o f t h e r m o d y n a m i c
p a r t i t i o n function. M a n y interesting m a t h e m a t i c a l results on the matchings p o l y -
n o m i a l can be f o u n d in [4]. A m o r e recent survey is presented in [3].

AMS subject classification (1980): 05 A 15; 05 C 99, 33 A 99

4*
258 C.O. GODSIL

The complete graph on n vertices will be denoted by K,. The matchings

polynomial c~(K,,) is identical with the Hermite polynomial He,, (x) of degree n.
(This latter polynomial is usually defined by
d"
He,(x) = ( - 1)"ex2/2~ e - ~"~/'2.

For further information on Hermite polynomials we refer the reader to [2]. The
fact that He,, (x)=ct(K,,, x) is proved in [4].)
We use (~ to represent the complement of the graph G. The main result
of this paper is the following connection between ~(G, x) and c~(G, x).
1.2. Theorem. Let G be a graph. Then the number of pelfect matchings in G is equal to

(2n) -1/2 ? c~(G, x) exp (-x~/2) dx.

Proof. We represent the integral above by I(G). Let En denote the graph with n
vertices and no edges. Clearly the complement of E, is K,, hence the number of
perfect matchings in E, is zero if n is odd and equals (n --1) (n - 3) . . . 1 when n is
even. It is now a simple exercise in integration by parts to show that the theorem
holds when G = E , .
We now prove the theorem for an arbitrary graph G with at least one edge.
Assume inductively that our result holds for each proper subgraph of G. Suppose
u = {1, 2} is an edge in G. Let G. be the graph obtained by deleting the edge {1, 2},
let G12 be obtained by deleting the vertices 1 and 2 from G.
Trivially, the k-matching in G may be partitioned into those that contain u
and those that do not. Hence we have
(l) p(O, k) = p(C~, k)+p(G,.~, k - 1 ) .
Using the definition of e(G) it follows that
(2) c~(G, x) = c~(G,, x)-c~(GI~, x).
From (1) we also have
(3) p(G,,, k) = p(G, k)-bp((~12, k - 1 ) ,
where it is to be understood that complementation is carried out after deletion.
By (2) and the linearity of integration,
(4) I(G) = I(G,,)- I(G12).
If n is odd then G, and Gx2 have no perfect matchings, the right side of (4)
is zero, by our induction hypothesis. Hence I ( G ) = 0 . Since G also has no perfect
matchings when n is odd, the theorem holds in this case.
Suppose then that n=2m. As the theorem holds for G, and G~2, (4) yields
I(G) = p(G,, m)--p(Gl~., m-- 1),
whence the theorem following using (3). |
 D U A L I T Y RELATION FOR M A T C H I N G S POLYNOMIALS 259

2. Some consequences of Theorem 1.2

2.1. In this section we will derive some consequences of Theorem 1.2. If G and H
are graphs we use G U H to denote their disjoint union. It is easy to show that
~(6UH)=~(a)~(H).
2.2. Corollary. Let G be a graph with n vertices. Then

(n - 2k) ! p (G, k) = (2n)-1/2 ? e (G, x) ~ (K,_ 2k, X) exp ( -- xZ/2) dx.

Proof. Let m = n - 2 k . The integral given is just I(GUK,,). By 1.2 this equals the
number of perfect matchings in the complement of GI..JK,,. Each k-matching in G
can be extended to give m! perfect matchings in G UK,,. On the other hand each
perfect matching of GUK,, restricts to a k-matching of G, so our result follows. |
Taking G = K , and m = n - 2 k in 2.2 yields the identity

(2n)-l/e ? e(K"')~'(K')exp(--x2/2)dx = {J; ! mm= n.

This is, of course, just a statement of the orthogonality of the Hermite polynomials
on the real line, with respect to the weight function (2n) -1/2 exp (-x2/2). It should
be evident that 1.2 and 2.2 enable a combinatorial interpretation of many properties
of the Hermite polynomials.
One consequence of the orthogonality of the Hermite polynomials is the
following.
2.3. Corollary. Let G be a graph with n vertices. Then

[,/2j
(G, x) = Z p (G, k) ~ (K,_ ~k, X).
k=0

Proof. It is easy to see that the Hermite polynomials form a basis for the vector
space of all polynomials with real coefficients. Hence ~(G, x) can be expressed in
a unique fashion as a linear combination of Hermite polynomials. By 2.2 and the
orthogonality of the Hermite polynomials we see that the coefficient of c~(Kn_~k)
in such an expression is just p(G, k). |
From either of Corollaries 2.2 or 2.3 we see that the matchings polynomial
of G determines that of C,. Further, taking x = 0 in 2.3 gives an explicit formula for
c~(G, 0), and thus also for the number of perfect matchings in G, in terms of the
numbers p(G, k). This formula is also derived, using inclusion-exclusion, in [8].
In this reference the multigraphs with the property that the matchings polynomial
of each subgraph determines that of its complementary subgraph are determined.
260 c.D. GODSlL

2.4. Theorem. Let G be a graph with n vertices. Then

(2n) -1/~ ? c~(Km, x),x(G, x + y ) exp (-x2/2) dx

k= 0 \ nl ]
711 > H.

Proof. It is straightforward to verify that (n-2k)p(Kn, k)=np(K,_~, k), whence

it follows from the definition of c~(G, x) that ff--~c~(K,)=nc~(K,_l). Hence the Taylor
series expansion of e(K,, x + y ) in powers of y can be written as

j=0\J

Using this we see that the theorem holds when G=Kn, since in this case the integral
in the statement of the theorem equals m[ [ n ] y , _ , , . Given this, the general result
follows at once using 2.3. II
We note one corollary of the preceding result.
2.5. CoroLlary. Let G be a graph with n vertices. Then the number of rnatchings
in G is

(2n) -1/~ ? ~(G, x-F 1) exp (-x"-/2) dx.

Proof. Take y = l , m = 0 in 2.4, II

3. Rook polynomials

3.1. A result analogous to 1.2 can be established for rook polynomials. We com-
ment briefly on this.
A subset of the squares of an m × n chessboard (m<=n) will be referred to as a
board. If B is a board then r(B, k) is the number of ways of placing k non-attacking
rooks on the square~ of B, i.e. the number of choosing k squares of B with no two
in the same row or column.
We identify a board B with a graph G=G(B) as follows. The vertices of
G(B) are the rows and columns of the full m X n chessboard, a row and column
are adjacent if the square in which they intersect lies in B. Given this identification
it follows that r(B, k)=p(G(B), k). Note that if B is the full m × n chessboard then
G(B) is the complete bipartite graph Km, n.
 D U A L I T Y RELATION FOR MATCHFNGS POLYNOMIALS 261

If G is a subgraph of K,,., we define the rook polynomial r(G, x) to be

(-1)kp(C, k)x o'-~.

k=O

Many properties of rook polynomials are established in the last two chapters of
Riordan's book [7]. In particular we find that ( - l ) ' r ( K , , , , x) is the Laguerre poly-
nomial Lm(x) and that, if t=>0, ( - l)"r(Km,,,+,, x) is the generalized Laguerre poly-
nomial L~,,(x). For information o11 the Laguerre polynomials see [2]. We also warn
the reader that our notation for rook polynomials differs slightly from that used by
Riordan.
If G is a subgraph of K,..... we use G* to denote the subgraph of Kin,,, formed
by those edges not in G. Taking the proof of 1.2 as a guide, we obtain:
3.2. Theorem. Let G be a subgraph of K,,,,,. Then the mtmber of pepfect matehings
in G* is equal to
f r(G, x)e-* dx. |
0

This result also occurs as Corollary 2.1 in [5]. We note that if G and H are
subgraphs of K,,,,,, +~and K,,, +~ respectively, then G U H is a subgraph of K~,t where
l=m+n+s. It is routine to verify that the rook polynomial of G U H is
r(G, x)r(H, x)x s. If H=K,,,,_~ ~ then the number of perfect matchings in ( G U H ) *
is just n!(n+s)! p(G*, r n - n ) when n<=m, and is zero otherwise. Hence:
3.3. Corollary. Let G be a subgraph of Km,,,+.~. Then

•/ [ 0 F r ( G ' x ) r ( K " ' n + ~ ' x ) x ~ e - * d x = ~ n ' ( n + s ) ' p ( G * ' n ' - - n ) n<=m,

o n >0. |

It follows from 3.3 that r(G, x) determines r(G*, x), as was first proved by
Riordan (see equation (22) on page 179 of [7]). Taking G=Km.m+~ in 3.3 also yields
the well-known fact that the generalized Laguerre polynomials L~,,(x) (m=0, 1, ...)
are orthogonal on the non-negative reals with respect to the weight function x~e -*.
Using arguments analogous to those employed in the proof of 2.3, we also
obtain:
3.4. Corollary. Let G be a subgraph of K,..... +~. Then
?11
• v-
,.(c*, x) = Z p ( C , m - l ) ; (/(,.;+~, x). |
i=0

In conclusion we remark that, i f G is a subgraph ofK,,,, (m ~n), then ~(G, x ) =

=x"-"r(G, x~). As a special case of this we have
~(K, ..... x) = x"-"r(K, ..... x ~) = ( - 1)'x"-mL",;-"(x%
Furthermore K, .... is the complement of K,,,UK,,. Consequently we may use the
results of Section 2 to derive relations between the Hermite and generalized Laguerre
polynomials. For example taking G=K,, UK,, in 2.3 yields the expansion of L~,-m(x2)
in terms of Hermite polynomicals.
262 C. D. GODSIL: D U A L I T Y RELATION FOR MATCHINGS POLYNOMIALS

Note in proof. I have recently seen an a p p a r e n t l y u n p u b l i s h e d m a n u s c r i p t [1] by

R u t h A z o r , J. Gillis a n d J. D. Victor. This c o n t a i n s a p r o o f o u r T h e o r e m 1.2 u n d e r
the a d d i t i o n a l a s s u m p t i o n t h a t G is a c o m p l e t e m u l t i p a r t i t e graph.
Also the observation t h a t ~(G, x) d e t e r m i n e s ct(G, x) is an i m m e d i a t e con-
sequence o f Exercise 5.18 (a) in L. LovS.sz [6].

References

[1] R. AZOR, J. GiLLIS and J. D. VICTOR, Combinatorial applications of Hermite polynomials,

manuscript.
[21 A. ]~RDI~LYI,W. MAGNUS,F. OBERHETTiNGERand F. G. TRtCOMI, Higher Transcendental Func-
tions (Bateman manuscript project), McGraw-Hill, 1953.
[3] C. D. GODSIL and I. GUTMAN, On the theory of the matching polynomial, J. Graph Theory,
5 (1981), 137--144.
[4] O. J. HEiLMANN and E. H. LisB, Theory of monomer-dimer systems, Comm. Math. Physics,
25 (1972), 190--232.
[5] S. A. JoNI and G-C. ROTA, A vector space analog of permutations with restricted position,
J. Combinatorial Theory, Series A, 29 (1980), 59--73.
[6] L. LovAsz, Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979.
[7] J. RIORDAN, An introduction to Combhlatorial Analysis, Wiley, 1958.
[8] T. ZASLAVSKY,Complementary matching vectors and the uniform matching extension property,
Europ. J. Comb. 2 (1981), 91--103.