Recent progress on the combinatorial diameter of polytopes and simplicial complexes
Recent progress on the combinatorial diameter of polytopes and simplicial complexes
复制标题
多胞体和单纯复形组合直径的最新进展
DOI：
10.1007/s11750-013-0295-7
复制
发表时间：
2013
期刊：
影响因子：
1.7
通讯作者：
F. Santos
中科院分区：
文献类型：
--
作者：
F. Santos
1957年提出的赫希猜想（英语：Hirsch Conjecture）指出，d维多面体或有n个小平面的多面体的图的直径不能大于n-d。这个猜想本身已被证明是错误的，但我们对这个潜在问题的了解却相当少。最值得注意的是，没有多项式上限是已知的直径被证明是线性的。与此相反，目前还没有发现任何一个多面体违反了这个猜想25%以上。有些工作是在多面体或（更常见的）有界多面体的世界，但有些人试图通过将其推广到单纯复形来阐明这个问题。特别是，我们在这里包括我们最近和以前未发表的证明，即任意单纯复形的最大直径是nΘ（d），我们总结了polymath 3项目中的主要思想，这是一个基于网络的集体努力，试图证明多面体和更一般物体（包括，例如，单形流形）。
The Hirsch Conjecture, posed in 1957, stated that the graph of a d-dimensional polytope or polyhedron with n facets cannot have diameter greater than n−d. The conjecture itself has been disproved, but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the conjecture by more than 25 % is known.This paper reviews several recent attempts and progress on the question. Some work is in the world of polyhedra or (more often) bounded polytopes, but some try to shed light on the question by generalizing it to simplicial complexes. In particular, we include here our recent and previously unpublished proof that the maximum diameter of arbitrary simplicial complexes is in nΘ(d), and we summarize the main ideas in the polymath 3 project, a web-based collective effort trying to prove an upper bound of type nd for the diameters of polyhedra and of more general objects (including, e.g., simplicial manifolds).
赫希猜想适用于正常旗形复合体
DOI：
10.1287/moor.2014.0661
发表时间：
2014
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Karim Adiprasito;Bruno Benedetti
通讯作者：
Bruno Benedetti
DOI：
10.1007/978-3-642-20807-2_16
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
Oliver Friedmann
通讯作者：
Oliver Friedmann