Prescribed and simultaneous failures of log-concavity in trees with perfect matchings
Abstract
We construct trees with perfect matchings and independence sequences that fail log-concavity near the independence number α. For every integer k≥1, one family fails at α−k and has a witness of order O(k2log(k+2)). For every integer t≥2, a single tree has simultaneous failures at α−1,α−3,…,α−(2t−1), with a witness of order O(t3). All these trees satisfy α=N/2, where N is the number of vertices, and contradict Conjecture 4.2 of Ramos and Sun. A sufficient condition uses a fixed tree and the numbers of attached leaves. For fixed k or t, explicit bounds give geometric decay of aj2/(aj−1aj+1) at these indices as the trees grow; aj counts independent j-sets. The proofs count independent sets by empty matching pairs. The Lean proof assistant checks formal proofs of the parameterized results and their quantitative bounds; exact 90- and 180-vertex examples illustrate the constructions.
Related
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- A simplified proof of the FPRAS for counting perfect matchings
- Perfect matchings in hypergraphs and Feige's inequality
- Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
- The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
BibTeX
@misc{fan2026prescribed,
title = {{Prescribed and simultaneous failures of log-concavity in trees with perfect matchings}},
author = {Heshun Fan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18340},
eprint = {2610.18340},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18340},
}
RIS
TY - UNPB
TI - Prescribed and simultaneous failures of log-concavity in trees with perfect matchings
AU - Heshun Fan
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18340
UR - https://arxiv.org/abs/2610.18340
AB - We construct trees with perfect matchings and independence sequences that fail log-concavity near the independence number α. For every integer k≥1, one family fails at α−k and has a witness of order O(k^2log(k+2)). For every integer t≥2, a single tree has simultaneous failures at α−1,α−3,…,α−(2t−1), with a witness of order O(t^3). All these trees satisfy α=N/2, where N is the number of vertices, and contradict Conjecture 4.2 of Ramos and Sun. A sufficient condition uses a fixed tree and the numbers of attached leaves. For fixed k or t, explicit bounds give geometric decay of a_j^2/(a_j−1a_j+1) at these indices as the trees grow; a_j counts independent j-sets. The proofs count independent sets by empty matching pairs. The Lean proof assistant checks formal proofs of the parameterized results and their quantitative bounds; exact 90- and 180-vertex examples illustrate the constructions.
ER -