Additive Augmentation Gaps Do Not Force Log-Concavity
Overview
A relaxed rule for extending independent sets does not ensure log-concavity of the counts by size. A 13-element example of rank four has counts 1, 13, 25, 7, 2, disproving Xie and Xu’s rank-dependent conjecture; further families retain the same augmentation parameter while their log-concavity ratios tend to zero.
Original public questions
Xie–Xu Conjecture 4.8: relaxed augmentation and log-concavity
Yan-Ting Xie and Shou-Jun Xu: Ultra log-concavity and real-rootedness of dependence polynomials — Conjecture 4.8: rank-dependent log-concavity for independence systems with relaxed augmentation. This is not the classical matroid log-concavity theorem.
Original abstract (English)
We construct independence systems satisfying a fixed additive relaxation of the matroid augmentation axiom whose independence sequences fail log-concavity. This disproves the rank-dependent extension of Mason's conjecture proposed by Xie and Xu. The construction has two ingredients: the largest gap in a failed augmentation is additive under direct sums, and a tunable low-degree term can survive multiplication by any fixed matroid independence polynomial as a log-concavity obstruction. A thirteen-element example has rank four and independence sequence 1,13,25,7,2. More generally, the augmentation parameter can remain three while the rank tends to infinity. We also construct systems whose rank divided by their ground-set size tends to one, while a consecutive log-concavity ratio tends to zero. All singletons are independent, yet no element can be added to every independent set.
Mathematical review
The principal conclusions have a public kernel-checked proof package and reviewed correspondence with the paper. This is distinct from external peer review.
Review standard