\def\StanAU{18}
\def\StanAR{17}
\def\GashAA{6}
\def\StWhAB{19}
\def\StanAQ{16}
\def\SagaAK{15}
\def\SagaAJ{14}
\def\SagaAE{13}
\def\LoPlAA{12}
\def\LeroAA{11}
\def\KratAI{10}
\def\HeLiAA{9}
\def\HaLPAA{8}
\def\HabsAD{7}
\def\ButlAC{5}
\def\BretAH{4}
\def\BretAG{3}
\def\BretAC{2}
\def\BretAA{1}
\input format
\def\x{\bold x}

\topmatter 
\title Combinatorial proof of the log-concavity of the sequence of
matching numbers
\endtitle 
\author C.~Krattenthaler
\endauthor 
\affil 
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4, A-1090 Wien, Austria.\\
e-mail: KRATT\@Pap.Univie.Ac.At
\endaffil
\address Institut f\"ur Mathematik der Universit\"at Wien,
Strudlhofgasse 4, A-1090 Wien, Austria.
\endaddress
%\email KRATT\@Pap.Univie.Ac.At\endemail
%\dedicatory \enddedicatory
%\date \enddate
%\thanks \endthanks
\subjclass Primary 05C70;
 Secondary 05A05, 05A20
\endsubjclass
\keywords matching in graphs, log-concavity, unimodality\endkeywords
\abstract For $k\ge 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\. {\bf 99},
289--306).
\endabstract
\endtopmatter
\document
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\. \cite{\LoPlAA, p.~xxxii, p.~333ff}). It is well-known that the
matching numbers $m_k(G)$ form a log-concave sequence (cf\.
\cite{\LoPlAA, Ex.~8.5.10}), i.e\. that
$$m_{k-1}(G)m_{k+1}(G)\le m_k(G)^2\quad \quad \text {for all }k\ge
1.\tag1.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 \cite{\HeLiAA, Theorem~4.2; \LoPlAA, Cor.~8.5.7}
which basically says that the zeros of the polynomial $\sum _{k\ge0}
^{}m_k(G)x^k$ are all real and nonpositive. (It is well-known
\cite{\HaLPAA} that this implies log-concavity of the coefficients of
the polynomial. For surveys on log-concavity and unimodality see
\cite{\BretAH, \StanAQ}.)

Now, the inequality (1.1) is a statement about {\it combinatorial}
quantities. In view of recent combinatorial work on log-concavity
\cite{\BretAA, \BretAC, \BretAG, \ButlAC, \HabsAD, \KratAI, \LeroAA,
\SagaAE, \SagaAJ, \SagaAK} one is tempted to ask for a {\it
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
\cite{\SagaAJ}) % 295/296
which does not follow from the Heilmann--Lieb result (see Theorem~2
below).

\bigskip
What we shall actually prove combinatorially is the {\it strong}
log-concavity of the numbers $m_k(G)$. Recall \cite{\SagaAE, \SagaAJ}
that this means
$$m_{l-1}(G)m_{k+1}(G)\le m_l(G)m_k(G)\quad \quad \text {for all }k\ge
l\ge 1.\tag1.2$$
In fact, strong log-concavity is equivalent to log-concavity, but
this is not true for the weighted version.
\proclaim{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$.
\endproclaim
\demo{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 \dots
-blue-red-blue-red-\dots. 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 {\it blue chain} if the
number of blue edges is one more than the number of red edges, and a
{\it 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,\dots,b+r\}$, one of cardinality $b$, the
other of cardinality $r$, the union of both being the complete set 
$\{1,2,\dots,b+r\}$. Because of $k\ge l$ and $r-b=k-l+2$ we may
deduce $b\le \frac {b+r} {2}-1$. Trivially, under this assumption
there is an injection from all $b$-element subsets of $\{1,2,\dots,b+r\}$
into all $(b+1)$-subsets of $\{1,2,\dots,b+r\}$ (see e.g\. \cite{\StWhAB} 
for an explicit one). Thus our $b$-element subset of $\{1,2,\dots,b+r\}$
that corresponds to the set of all blue chains is mapped to a
$(b+1)$-subset of $\{1,2,\dots,b+r\}$. Let
$c_1,c_2,\dots,c_{b+1}$ denote the chains that correspond to this
subset, and let $d_1,d_2,\dots,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-\dots-red-blue and
$d_i$ is coloured red-blue-\dots-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.
\quad \quad \qed
\enddemo
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)=\sum _{M} ^{}\prod _{e\in 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
\cite{\HeLiAA} 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.
\proclaim{Theorem 2}The sequence $(m_k(G,\x))$ is strongly
$\x$-log-concave in $k$ \cite{\SagaAJ,\linebreak pp.~295/296}, 
i.e\. for $k\ge l\ge 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. 
\quad \quad \qed
\endproclaim


\remark{Remark} A generalization of this Theorem in connection with
Stanley's symmetric function generalization \cite{\StanAR, \StanAU}
of the chromatic polynomial has been recently found by Gasharov
\cite{\GashAA, Theorem~1.1}.
\endremark



\Refs

\ref\no \BretAA\by F.    Brenti \yr 1989 
\book Unimodal, log-concave and P\'olya frequency sequences in combinatorics
\publ Mem\. Amer\. Math\. Soc\., no.~413, Amer\. Math\. Soc\.
\publaddr Providence, R.~I\endref

\ref\no \BretAC\by F.    Brenti \yr 1991 
\paper Log-concavity and combinatorial properties of Fibonacci lattices
\jour Europ\. J. Combin\.\vol 12
\pages 459--476\endref

\ref\no \BretAG\by F.    Brenti \yr 19?? 
\paper Combinatorics and total positivity
\paperinfo preprint\vol 
\pages \endref

\ref\no \BretAH\by F.    Brenti \yr 19?? 
\paper Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update
\paperinfo preprint\vol 
\pages \endref

\ref\no \ButlAC\by L. M. Butler \yr 1990 
\paper The $q$-log concavity of $q$-binomial coefficients
\jour J. Combin\. Theory Ser.~A\vol 54
\pages 54--63\endref

\ref\no \GashAA\by V.    Gasharov \yr 19?? 
\paper On Stanley's chromatic symmetric function and stable set polynomials
\paperinfo preprint\vol 
\pages \endref

\ref\no \HabsAD\by L.    Habsieger \yr 1993 
\paper Inequalities between elementary symmetric functions 
--- application to log-con\-cav\-ity problems
\jour Discrete Math\.\vol 115
\pages 167--174\endref

\ref\no \HaLPAA\by G. H. Hardy, J. E. Littlewood and G. P\'olya \yr 1952 
\book Inequalities
\bookinfo 2nd edition
\publ Cambridge University Press
\publaddr Cambridge\endref

\ref\no \HeLiAA\by O. J. Heilmann and E. H. Lieb \yr 1972 
\paper Theory of momomer-dimer systems
\jour Comm\. Math\. Phys\.\vol 25
\pages 190--243\endref

\ref\no \KratAI\by C.    Krattenthaler \yr 1989 
\paper On the $q$-log-concavity of Gaussian binomial coefficients
\jour Monatshefte Math\. \vol 107
\pages 333--339\endref

\ref\no \LeroAA\by P.    Leroux \yr 1990 
\paper Reduced matrices and $q$-log concavity properties of $q$-Stirling numbers
\jour J. Combin\. Theory Ser.~A\vol 54
\pages 64--84\endref

\ref\no \LoPlAA\by L.    Lov\'asz and M. D. Plummer \yr 1986 
\book Matching theory
\bookinfo Ann\. Discrete Math\., vol.~29
\publ North--Holland
\publaddr Amsterdam, New York\endref

\ref\no \SagaAE\by B. E. Sagan \yr 1988 
\paper Inductive and injective proofs of log concavity results
\jour Discrete Math\.\vol 68
\pages 281--292\endref

\ref\no \SagaAJ\by B. E. Sagan \yr 1992 
\paper Inductive proofs of $q$-log concavity
\jour Discrete Math\.\vol 99
\pages 289--306\endref

\ref\no \SagaAK\by B. E. Sagan \yr 1992 
\paper Log concave sequences of symmetric functions and analogs of the Jacobi--Trudi determinants
\jour Trans\. Amer\. Math\. Soc\.\vol 329
\pages 795--811\endref

\ref\no \StanAQ\by R. P. Stanley \yr 1989 
\paper Log-concave and unimodal sequences in  algebra, combinatorics, and geometry
\jour Ann\. New York Acad\. Sci\.\vol 576
\pages 500--534\endref

\ref\no \StanAR\by R. P. Stanley 
\paper A symmetric function generalization of the chromatic polynomial of a graph
\jour Adv\. in Math\.\vol 
\pages \toappear\endref

\ref\no \StanAU\by R. P. Stanley \yr 19?? 
\paper Graph colorings and related symmetric functions: Ideas and applications
\paperinfo preprint\vol 
\pages \endref

\ref\no \StWhAB\by D.    Stanton and D. White \yr 1986 
\book Constructive Combinatorics
\bookinfo Undergraduate Texts in Math\.
\publ Sprin\-ger--Ver\-lag
\publaddr New York, Berlin Heidelberg, Tokyo\endref

\endRefs
\enddocument
