Combinatorial proof of the log-concavity

of the sequence of matching numbers

C. Krattenthaler

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Pap.Univie.Ac.At

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, 289–306).

Let G be a loopless graph. Let m_{k}(G) denote the number of k-element matchings in G, where by convention we set m_{0}(G) = 1 (cf. [12, p. xxxii, p. 333ff]). It is well-known that the matching numbers m_{k}(G) form a log-concave sequence (cf. [12, Ex. 8.5.10]), i.e. that

(1.1)  m_{k−1}(G)m_{k+1}(G) ≤ m_{k}(G)^{2}  for all k ≥ 1.

In particular, this implies the unimodality of the numbers m_{k}(G). The log-concavity of the sequence (m_{k}(G)) follows from a result of Heilmann and Lieb [9, Theorem 4.2; 12, Cor. 8.5.7] which basically says that the zeros of the polynomial ∑_{k≥0} m_{k}(G)x^{k} are all real and nonpositive. (It is well-known [8] that this implies log-concavity of the coefficients of the polynomial. For surveys on log-concavity and unimodality see [4, 16].)

Now, the inequality (1.1) is a statement about combinatorial quantities. In view of recent combinatorial work on log-concavity [1, 2, 3, 5, 7, 10, 11, 13, 14, 15] one is tempted to ask for a combinatorial proof of (1.1). We give such a proof below by constructing an explicit injection from the set of pairs (M_{1}, M_{2}) of a (k − 1)-element matching M_{1} and a (k + 1)-element matching M_{2} into the set of pairs (N_{1}, N_{2}) of k-element matchings N_{1}, N_{2}. Of course, this does not imply the Heilmann–Lieb result on the zeros of the matching polynomial. However, our combinatorial proof, besides from being simple and very natural, also yields a weighted log-concavity result (in the sense of Sagan [14]) which does not follow from the Heilmann–Lieb result (see Theorem 2 below).

1980 Mathematics Subject Classification (1991 Revision). Primary 05C70; Secondary 05A05, 05A20.

Key words and phrases. matching in graphs, log-concavity, unimodality.

What we shall actually prove combinatorially is the strong log-concavity of the numbers m_{k}(G). Recall [13, 14] that this means

(1.2)  m_{l−1}(G)m_{k+1}(G) ≤ m_{l}(G)m_{k}(G)  for all k ≥ l ≥ 1.

In fact, strong log-concavity is equivalent to log-concavity, but this is not true for the weighted version.

Theorem 1. Let G be a loopless graph. There is an explicit injection from the set of all pairs (M_{1}, M_{2}) of an (l−1)-element matching M_{1} in G and a (k +1)-element matching M_{2} in G into the set of all pairs (N_{1}, N_{2}) of an l-element matching N_{1} in G and a k-element matching N_{2} in G.

Construction of the injection. Let M_{1} be an (l − 1)-element matching in G and M_{2} be a (k + 1)-element matching in G. Let us colour the edges of M_{1} by blue and the edges of M_{2} by red. Now consider the graph G(M_{1}, M_{2}) being induced by all edges of M_{1} and M_{2}. Because M_{1} and M_{2} are matchings, the connected components of G(M_{1}, M_{2}) are either circuits or chains, in both cases the edges are coloured alternatively … -blue-red-blue-red- …. Therefore all the circuits contain an equal number of blue and red edges. On the other hand, there are three different types of chains. Either the number of blue edges in a chain equals the number of its red edges, or it is one more, or it is one less. For the moment disregard the circuits and chains with an equal number of blue and red edges. Let us call a chain a blue chain if the number of blue edges is one more than the number of red edges, and a red chain if the number of blue edges is one less than the number of red edges. Suppose that G(M_{1}, M_{2}) contains b blue chains and r red chains. Clearly we have r − b = (k + 1) − (l − 1) = k − l + 2.

Now assume a fixed numbering of the vertices of G. Consider the set of all blue and red chains of G(M_{1}, M_{2}) and number the chains according to the numbers of the vertices they contain. To be more precise, the chain that contains the vertex with minimum number gets the number 1, the chain that contains the vertex with the smallest number among all vertices that are not contained in the first chain gets number 2, etc. Thus, the set of blue chains and the set of red chains of G(M_{1}, M_{2}) can be uniquely identified with two disjoint subsets of {1, 2, …, b + r}, one of cardinality b, the other of cardinality r, the union of both being the complete set {1, 2, …, b+r}. Because of k ≥ l and r − b = k − l + 2 we may deduce b ≤ \frac{b+r}{2} − 1. Trivially, under this assumption there is an injection from all b-element subsets of {1, 2, …, b + r} into all (b + 1)-subsets of {1, 2, …, b + r} (see e.g. [19] for an explicit one). Thus our b-element subset of {1, 2, …, b + r} that corresponds to the set of all blue chains is mapped to a (b + 1)-subset of {1, 2, …, b + r}. Let c_{1}, c_{2}, …, c_{b+1} denote the chains that correspond to this subset, and let d_{1}, d_{2}, …, d_{r−1} denote the chains that correspond to its complement. We change the colours of the edges of these chains such that c_{i} is coloured blue-red- … -red-blue and d_{i} is coloured red-blue- … -blue-red. Note that now we have (b + 1) blue chains and (r − 1) red chains. Now we consider the graph consisting of these freshly coloured chains, of the chains with an equal number of blue and red edges, and of all the circuits. The blue edges define an l-element matching N_{1} in G and the red edges a k-element matching N_{2} in G. It is easily checked that this defines the desired injection. □

Finally we turn to the weighted matching numbers. To each edge e of the graph G we assign a weight x_{e}. Then we define the weighted matching number m_{k}(G, x) by

m_{k}(G, x) = ∑_{M} ∏_{e∈M} x_{e},

where the sum is over all k-element matchings M in G. (This weighted version already appears in Heilmann and Lieb’s paper [9] although in their physical context the weights x_{e} are real numbers while in our context they are regarded as indeterminates.) It is easily observed that our injection also establishes the following assertion.

Theorem 2. The sequence (m_{k}(G, x)) is strongly x-log-concave in k [14, pp. 295/296], i.e. for k ≥ l ≥ 1 the polynomial

m_{l}(G, x)m_{k}(G, x) − m_{l−1}(G, x)m_{k+1}(G, x)

is a polynomial in the x_{e}’s (where e varies over all edges of G) with nonnegative coefficients. □

Remark. A generalization of this Theorem in connection with Stanley’s symmetric function generalization [17, 18] of the chromatic polynomial has been recently found by Gasharov [6, Theorem 1.1].

References

1. F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc., no. 413, Amer. Math. Soc., Providence, R. I, 1989.

2. F. Brenti, Log-concavity and combinatorial properties of Fibonacci lattices, Europ. J. Combin. 12 (1991), 459–476.

3. F. Brenti, Combinatorics and total positivity, preprint.

4. F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, preprint.

5. L. M. Butler, The q-log concavity of q-binomial coefficients, J. Combin. Theory Ser. A 54 (1990), 54–63.

6. V. Gasharov, On Stanley’s chromatic symmetric function and stable set polynomials, preprint.

7. L. Habsieger, Inequalities between elementary symmetric functions — application to log-concav-ity problems, Discrete Math. 115 (1993), 167–174.

8. G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, 2nd edition, Cambridge University Press, Cambridge, 1952.

9. O. J. Heilmann and E. H. Lieb, Theory of momomer-dimer systems, Comm. Math. Phys. 25 (1972), 190–243.

10. C. Krattenthaler, On the q-log-concavity of Gaussian binomial coefficients, Monatshefte Math. 107 (1989), 333–339.

11. P. Leroux, Reduced matrices and q-log concavity properties of q-Stirling numbers, J. Combin. Theory Ser. A 54 (1990), 64–84.

12. L. Lovász and M. D. Plummer, Matching theory, Ann. Discrete Math., vol. 29, North–Holland, Amsterdam, New York, 1986.

13. B. E. Sagan, Inductive and injective proofs of log concavity results, Discrete Math. 68 (1988), 281–292.

14. B. E. Sagan, Inductive proofs of q-log concavity, Discrete Math. 99 (1992), 289–306.

15. B. E. Sagan, Log concave sequences of symmetric functions and analogs of the Jacobi–Trudi determinants, Trans. Amer. Math. Soc. 329 (1992), 795–811.

16. R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci. 576 (1989), 500–534.

17. R. P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. in Math., (to appear).

18. R. P. Stanley, Graph colorings and related symmetric functions: Ideas and applications, preprint.

19. D. Stanton and D. White, Constructive Combinatorics, Undergraduate Texts in Math., Springer–Verlag, New York, Berlin Heidelberg, Tokyo, 1986.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.