顶点插入可增加棱锥宽度

Pyramidal Width Can Increase Under Vertex Insertion

精选理由

数学家们把一个2015年的猜想推翻了,用六个整数点就让棱锥宽度变大,差41%呢。

AI 摘要

2015年Lacoste-Julien和Jaggi猜想,多胞体添加一个顶点且所有旧顶点仍是顶点时,其棱锥宽度不会增大。本文在三维空间中用六个整数点构造了精确反例:P由五个顶点构成,Q加入第六个顶点后五个旧顶点仍为顶点。但P和Q的棱锥宽度平方分别为48/353和36/133,比值约为1.410886779。证明利用棱锥宽度与面距离的等价性,并用整数支撑超平面验证面格。论文附带了无依赖的精确验证器。

原文 · arXiv cs.LG

Pyramidal Width Can Increase Under Vertex Insertion

Lacoste-Julien and Jaggi conjectured in 2015 that the pyramidal width of a polytope cannot increase when a vertex is added, provided that every old point remains a vertex. We give an exact counterexample with six integer points in $\R^3$. For \[ P=\conv\{v_0,\ldots,v_4\},\qquad Q=\conv\{v_0,\ldots,v_5\}, \] where \[ \begin{aligned} v_0&=(-1,-3,-1), & v_1&=(3,2,-2), & v_2&=(0,2,1),\\ v_3&=(-1,-3,3), & v_4&=(-2,0,1), & v_5&=(-1,0,-2), \end{aligned} \] all five vertices of $P$ remain vertices of $Q$, but \[ \PWidth(P)^2=\frac{48}{353} \quad\text{and}\quad \PWidth(Q)^2=\frac{36}{133}. \] Thus vertex insertion increases pyramidal width by the factor $\sqrt{1059/532}\approx 1.410886779$. The proof uses the equivalence between pyramidal width and facial distance, certifies both face lattices by integer supporting hyperplanes, and evaluates every facial distance by a finite rational calculation. A dependency-free exact verifier accompanies the paper.