Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
复制标题
DOI：
10.4230/lipics.icalp.2018.74
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
R. Gurjar;T. Thierauf;Nisheeth K. Vishnoi
中科院分区：
文献类型：
--
作者：
R. Gurjar;T. Thierauf;Nisheeth K. Vishnoi
我们提出了一个几何方法去随机化的隔离引理Mulmuley，Vazirani和Vazirani。特别是，我们的方法产生一个准多项式家庭的权重，其中每个权重是一个整数和准多项式有界的，可以隔离任何0/1多面体的顶点，每个面位于一个仿射空间定义的一个完全么模矩阵。这包括完全么模约束给出的多面体，并推广了最近针对二部完美匹配和拟阵交集的隔离引理的去随机化。我们证明了我们的结果相关联的一个格的多面体的每个面，并表明，如果有一个完全么模的核心矩阵，这个格，然后在3/2的最短向量的长度向量的数量是多项式有界的。这后一个几何事实的证明是组合的，并遵循一个多项式约束的电路数量的大小在3/2的最短电路在一个经常拟阵。这是本文的技术核心，依赖于西摩分解定理的一个变种。将Karger关于图的最小割数的一个有影响的结果推广到正则拟阵。
We present a geometric approach towards derandomizing the Isolation Lemma by Mulmuley, Vazirani, and Vazirani. In particular, our approach produces a quasi-polynomial family of weights, where each weight is an integer and quasi-polynomially bounded, that can isolate a vertex in any 0/1 polytope for which each face lies in an affine space defined by a totally unimodular matrix. This includes the polytopes given by totally unimodular constraints and generalizes the recent derandomization of the Isolation Lemma for bipartite perfect matching and matroid intersection. We prove our result by associating a lattice to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of vectors of length within 3/2 of the shortest vector in it is polynomially bounded. The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of circuits of size within 3/2 of the shortest circuit in a regular matroid. This is the technical core of the paper and relies on a variant of Seymour's decomposition theorem for regular matroids. It generalizes an influential result by Karger on the number of minimum cuts in a graph to regular matroids.