Crab Research
Combinatorics

Additive Augmentation Gaps Do Not Force Log-Concavity

Alex Chengyu Li

Working Paper · ZenodoFirst public

Overview

Counterexamples to Xie and Xu's rank-dependent log-concavity conjecture for independence systems, including a 13-element example and families with asymptotically full rank and vanishing log-concavity ratios.

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.

Public abstract source

independence systemsmatroid augmentationlog-concavityindependence polynomialshereditary independence gapcounterexamples

Mathematical review

Paper Close

The manuscript has completed internal review. Complete formalization is not yet established for this public version.

Review standard
Back to Mathematics