Matching polynomials and duality (Q558244): Difference between revisions

Let \(G=(V,E)\) be a finite simple graph where \(V\) is a set of \(n\) vertices and the set of edges \(E\) is a subset of \(\binom{V}{2}\), namely the family of all \(2\)-element subsets of \(V\). The complement of \(G\) is the graph \(\overline G=(V,\overline E)\) with \(\overline E=\binom{V}{2}\setminus E\), and an \(r\)-matching in \(G\) is a set of \(r\) edges of \(G\), no two of which have a vertex in common, therefore \(r\leq \lfloor n/2\rfloor\). In the case \(r=\lfloor n/2\rfloor\), \(n\) even, an \(r\)-matching is called perfect. Let \(p(G,r)\) denote the number of \(r\)-matchings in \(G\), with the convention that \(p(G,0)=1\). Then the matching polynomial of \(G\) is defined by \[ \mu(G,x)=\sum^{\lfloor n/2\rfloor}_{r=0}(- 1)^r\cdot p(G,r)\cdot x^{n-2r} \] and the signless matching polynomial reads \(\overline \mu (G,x)=\sum^{\lfloor n/2\rfloor}_{r=0} p(G,r)\cdot x^{n-2r}\). It follows that \(\overline \mu(G,0)\) counts the number of perfect matchings of \(G\) and \(\overline \mu (G,1)\) counts the number of arbitrary matchings. These polynomials were introduced by Heilmann and Lieb who proved as their main result that all zeros of \(\mu (G,x)\) are real. This result also was obtained by further authors and all those proofs rely on a recurvise approach towards the matching polynomial. Matching polynomials are generalizations of many classical orthogonal polynomials, e.g. Hermite polynomials (matching polynomials of complete graphs), Chebychev polynomials (paths and cycles) and Laguerre polynomials (complete bipartite graphs). The author gets the following results: (1) New duality theorems, e.g. by means of differential operators (Section~3); (2) The matching functions \(e^{-\frac{x^2}{2}}\mu(\overline G,x)\) and \(e^{-\frac{x^2}{2}}\mu(G,x)\) of \(\overline G\) and \(G\) are, up to an eventual multiplication by \((-1)\), real Fourier-transforms of one another (Section~3); (3) New short proof of the theorem that all zeros of \(\mu(G,x)\) are real (Section 4). The algebra of generating functions for set functions is introduced which is developed in Section 2. In Section 3 several duality theorems are proved by application of this generating function method for set functions and moreover the author gets a modification of a known theorem and a scalar product formula by a integral. In Section 4 the combinatorial proof of the Mehler formula for Hermite polynomials is generalized to matching polynomials and with the help of this result the author gets (3). In this manner he yields a proof which avoids the technique by deleting special vertices as mentioned above. And further it is shown that this fact also holds for a common generalization of the matching polynomial and the rook polynomial.