标题： 关于拟阵非断基的优化与计数 显示英文标题

标题： On Optimization and Counting of Non-Broken Bases of Matroids

摘要： 给定一个拟阵$M=(E,{\cal I})$，以及元素上的全序关系$E$，断裂环是一个电路，其中最小的元素被移除，而一个无断裂环的独立集是在${\cal I}$中没有断裂环的独立集。 任何拟阵$M$的无断裂环独立集的集合定义了一个称为断裂环复形的单纯复形，这在组合学中一直受到深入研究。 最近，Adiprasito、Huh 和 Katz 表明任何断裂环复形的面数形成一个对数凹序列，证明了 Rota 的一个长期存在的猜想。 我们研究了一般拟阵的无断裂环基上的计数和优化问题。 我们发现与独立集复形有若干基本差异：例如，我们证明找到拟阵的最大权重无断裂环基是 NP 难的，或者拟阵的无断裂环基的凸包具有任意大的长度的边。 我们还提供了证据表明，在拟阵的无断裂环基空间上的自然下上行走可能不会快速混合，这是通过证明对于某些拟阵族，在某些条件之后计数无断裂环基的数量是 NP 难的。 显示英文摘要

摘要： Given a matroid $M=(E,{\cal I})$, and a total ordering over the elements $E$, a broken circuit is a circuit where the smallest element is removed and an NBC independent set is an independent set in ${\cal I}$ with no broken circuit. The set of NBC independent sets of any matroid $M$ define a simplicial complex called the broken circuit complex which has been the subject of intense study in combinatorics. Recently, Adiprasito, Huh and Katz showed that the face of numbers of any broken circuit complex form a log-concave sequence, proving a long-standing conjecture of Rota. We study counting and optimization problems on NBC bases of a generic matroid. We find several fundamental differences with the independent set complex: for example, we show that it is NP-hard to find the max-weight NBC base of a matroid or that the convex hull of NBC bases of a matroid has edges of arbitrary large length. We also give evidence that the natural down-up walk on the space of NBC bases of a matroid may not mix rapidly by showing that for some family of matroids it is NP-hard to count the number of NBC bases after certain conditionings.