✦ LIBER ✦

Combinatorial Proof of the Log-Concavity of the Sequence of Matching Numbers

✍ Scribed by C. Krattenthaler

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 145 KB
Volume: 74
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1996.0058

No coin nor oath required. For personal study only.

✦ Synopsis

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).

📜 SIMILAR VOLUMES

A Combinatorial Proof of the Log-Concavi

A Combinatorial Proof of the Log-Concavity of the Numbers of Permutations with k Runs

✍ Miklós Bóna; Richard Ehrenborg 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 178 KB

The Numbers of Dependent k-Sets in a Gra

The Numbers of Dependent k-Sets in a Graph Are Log Concave

✍ David G.C. Horrocks 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 69 KB

The fractional matching numbers of graph

The fractional matching numbers of graphs

✍ Yan Liu; Guizhen Liu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB

A Combinatorial Proof of the Effective N

A Combinatorial Proof of the Effective Nullstellensatz

✍ Thomas W. Dubé 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 481 KB

Let \(I\) be an ideal in the affine multi-variate polynomial ring \(\mathcal{A}=K\left[x_{1}, \ldots, x_{n}\right]\). Beginning with the work of Brownawell, there has been renewed interest in recent years in using the degrees of polynomials which generate \(I\) to bound the degree \(D\) such that:

A Combinatorial Interpretation of the Ge

A Combinatorial Interpretation of the Generalized Fibonacci Numbers

✍ Emanuele Munarini 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 181 KB

In this paper the generalized Fibonacci numbers of order k are combinatorially interpreted, in the context of the theory of linear species of Joyal, as the linear species of k-filtering partitions.

The Proof of a Conjecture of Additive Nu

The Proof of a Conjecture of Additive Number Theory

✍ Alexandru Gica 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 94 KB

The aim of this paper is to show that for any n ¥ N, n > 3, there exist a, b ¥ N\* such that n=a+b, the ''lengths'' of a and b having the same parity (see the text for the definition of the ''length'' of a natural number). Also we will show that for any n ¥ N, n > 2, n ] 5, 10, there exist a, b ¥ N\