Lectures on 0/1-Polytopes
Lectures on 0/1-Polytopes
复制标题
0/1-多面体讲座
DOI：
10.1007/978-3-0348-8438-9_1
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
G. Ziegler
中科院分区：
文献类型：
--
作者：
G. Ziegler
这些讲座的组合学和几何的0/1-多面体是作为一个介绍和邀请。而不是标题为广泛的调查0/1多面体，我提出了一些有趣的方面，这些对象，所有这些都涉及到一些相当近期的工作和进展。0/1-多面体有一个非常简单的定义和明确的描述;我们可以在计算机中明确地枚举和分析小例子（例如，G.使用polymake）。然而，任何从“低维”例子分析中得出的直觉都会错过0/1-多面体的真正复杂性。因此，在下文中，我们将研究高维0/1-多面体复杂性的几个方面：组合类型的双指数数，可能很大的面数，以及有时会变得非常大的定义不等式的系数。在这些讲座中，一些效应和结果将得到证明的支持;我们也将能够在明确的例子中验证其中一些，这些例子可以作为polymake数据库访问。
These lectures on the combinatorics and geometry of 0/1-polytopes are meant as an introduction and invitation. Rather than heading for an extensive survey on 0/1polytopes I present some interesting aspects of these objects; all of them are related to some quite recent work and progress. 0/1-polytopes have a very simple definition and explicit descriptions; we can enumerate and analyze small examples explicitly in the computer (e. g. using polymake). However, any intuition that is derived from the analysis of examples in “low dimensions” will miss the true complexity of 0/1-polytopes. Thus, in the following we will study several aspects of the complexity of higher-dimensional 0/1-polytopes: the doubly-exponential number of combinatorial types, the number of facets which can be huge, and the coefficients of defining inequalities which sometimes turn out to be extremely large. Some of the effects and results will be backed by proofs in the course of these lectures; we will also be able to verify some of them on explicit examples, which are accessible as a polymake database.