This material has been published in J. Combin. Theory Ser. A 74 (1996), 351-354, the only definitive repository of the content that has been certified and accepted after peer review. Copyright and all rights therein are retained by Elsevier B.V. This material may not be copied or reposted without explicit permission.

Christian Krattenthaler

Combinatorial proof of the log-concavity of the sequence of matching numbers

(4 pages)

Abstract. For k>=l we construct an injection from the set of pairs of matchings in a given graph G of sizes l-1 and k+1 into the set of pairs of matchings in G of sizes l and k. This provides a combinatorial proof of the log-concavity of the sequence of matching numbers of a graph. Besides, this injection implies that a certain weighted version of the matching numbers is strongly x-log-concave in the sense of Sagan (Discrete Math. 99 (1992), 289-306).


The following versions are available:


Back to Christian Krattenthaler's home page.