A local injective proof of log-concavity for increasing spanning forests
Preprint
Abstract
We give an explicit combinatorial proof of a weighted version of strong log-concavity for the generating polynomial of increasing spanning forests of a finite simple graph equipped with a total ordering of the vertices. In contrast to similar proofs in the literature, our injection is local in the sense that it proceeds by moving a single edge from one forest to the other. In the particular case of the complete graph, this gives a new combinatorial proof of log-concavity of unsigned Stirling numbers of the first kind where a pair of permutations is transformed into a new pair by breaking a single cycle in the first permutation and gluing two cycles in the second permutation, while all the other spectator cycles are left untouched.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Increasing spanning forests in graphs and simplicial complexesEuropean Journal of Combinatorics, 2019
- Combinatorial Proof of the Log-Concavity of the Sequence of Matching NumbersJournal of Combinatorial Theory, Series A, 1996
- Inductive proofs of q-log concavityDiscrete Mathematics, 1992
- On the numbers of independent k-sets in a claw free graphJournal of Combinatorial Theory, Series B, 1990
- Reduced matrices and q-log-concavity properties of q-Stirling numbersJournal of Combinatorial Theory, Series A, 1990
- Explicit matchings in the middle levels of the Boolean latticeOrder, 1988
- Inductive and injective proofs of log concavity resultsDiscrete Mathematics, 1988
- Binomial determinants, paths, and hook length formulaeAdvances in Mathematics, 1985
- Strong versions of Sperner's theoremJournal of Combinatorial Theory, Series A, 1976
- Lexicographic matching in Boolean algebrasJournal of Combinatorial Theory, Series B, 1973