组合数学中的组合Hirsch猜想 我们先从最直观的几何背景开始。想象一个多面体，例如三维空间中的立方体。这个多面体是由多个面（二维）、边（一维）和顶点（零维）构成的。现在，我们考虑在这个多面体的“骨架图”（即由顶点和边构成的图）上，从一个顶点走到另一个顶点。所需经过的最少边数，就是这两个顶点在图上的距离。而多面体的 直径 ，则定义为所有顶点对之间的最短路径距离的最大值。 第一步：组合凸性与多面体直径 组合数学研究多面体时，常常关注其组合结构而非具体的几何形状。一个凸多面体的组合结构可以由它的面格（face lattice）完全描述。多面体的直径就是一个重要的组合不变量。一个自然的问题是：对于一个d维凸多面体，如果它一共有n个面（facet），那么它的直径最大能有多大？这个问题将多面体的维数（d）、面的数量（n）与其组合性质（直径）联系了起来。 第二步：Hirsch猜想的原始表述 1957年，Warren M. Hirsch提出了一个著名的猜想，后来由Edward H. Spanier进行了推广。这个猜想断言：一个d维凸多面体，若其有n个面，则其组合直径至多是 n - d。例如，一个三维立方体（d=3）有6个面（n=6），其直径是3（从一个顶点出发，沿着空间对角线到达对顶点需要经过3条边），而n-d=3，符合猜想。这个猜想在运筹学，特别是在线性规划的单纯形法分析中具有重要意义，因为单纯形法的迭代次数可能与所对应多面体的直径有关。 第三步：组合Hirsch猜想及其意义 原始的Hirsch猜想关注的是几何多面体。然而，组合数学家将其抽象化，提出了 组合Hirsch猜想 。这个猜想研究的是更一般的组合对象—— 抽象多面体 或 单纯复形 ——的直径。它探讨的是，在满足某些组合凸性条件（例如，是某个单纯复形的边界复形，且具有类似于多面体的连通性）的图（1-骨架）中，图的直径是否也能被类似的不等式（例如，关于维数和面数的线性函数）所界定。这使得问题脱离了具体的几何嵌入，成为一个纯粹的组合极值问题。 第四步：猜想的否定与组合反例 尽管Hirsch猜想在低维情况和许多特殊多面体上都成立，但它在一般情形下是错误的。2010年，Francisco Santos构造出了一个43维、86个面的凸多面体，其直径大于44（=86-43），从而推翻了原始的几何Hirsch猜想。这一突破性工作表明，多面体直径的上界不可能像Hirsch猜想那样，仅仅是关于面数n和维数d的线性函数。这自然引出一个更深层次的组合问题：在组合Hirsch猜想的框架下，对于抽象多面体，直径的上界究竟是多少？ 第五步：多项式Hirsch猜想与当前进展 在原始线性猜想被否定后，研究的焦点转向了 多项式Hirsch猜想 。该猜想提出，是否存在一个多项式P(d, n)，使得任何d维、有n个面的（组合）多面体的直径都不超过P(d, n)？这是组合凸性领域一个非常重要的开放性问题。目前最好的上界结果是指数级的，例如O(n^d)或改进后的形式。寻找一个多项式上界，或者证明这样的上界不存在，是当前研究的核心挑战之一。这个问题的解决将深刻影响组合优化、离散几何和计算复杂性理论。