Crab Research
返回结果列表
组合数学

加性增广间隙不能保证对数凹性

Additive Augmentation Gaps Do Not Force Log-Concavity

工作论文 · SSRN首次公开 修订

形式化是机器可检查的证明。证明助手的逻辑核心称为内核;它仅从已列明的基本逻辑原则出发,检查全部承重定理,不额外假设未经证明的定理。这称为 Kernel-Only 验证。

研究概述

对独立集的增广规则作固定的加性放宽,并不能保证各个大小的独立集数量呈对数凹性。一个含 13 个元素、秩为 4 的例子给出计数 1、13、25、7、2,反驳了 Xie 与 Xu 的秩相关猜想;进一步的反例族保持同一增广参数,而对数凹性比值趋于零。

原始公开问题

Xie–Xu 猜想 4.8:放宽增广条件与对数凹性

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.

原文摘要(英文)

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.

公开摘要来源

independence systemsmatroid augmentationlog-concavityindependence polynomialshereditary independence gapcounterexamples

数学审核

Kernel-Only

主要结论拥有公开的内核检查证明包,并已审核其与论文的对应关系。这与外部同行评审是不同的验证。

审核标准
返回结果列表
返回 数学