# Pyramidal Width Can Increase Under Vertex Insertion

arXiv: https://arxiv.org/abs/2607.29555 · HTML: https://mlsanity.com/paper/2607.29555/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 7 references that are in the map.
- First posted on arXiv 31 Jul 2026.

## Builds on (most cited first, 3 of 3)

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Polytope conditioning and linear convergence of the Frank-Wolfe algorithm](https://mlsanity.com/paper/1512.06142/) (2015)
- [Efficient Learning in Polyhedral Games via Best Response Oracles](https://mlsanity.com/paper/2312.03696/) (2023)

## Abstract (arXiv)

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 R3. For [ P=convv0,ldots,v4,qquad Q=convv0,ldots,v5, ] where [ beginaligned v0&=(-1,-3,-1), & v1&=(3,2,-2), & v2&=(0,2,1), v3&=(-1,-3,3), & v4&=(-2,0,1), & v5&=(-1,0,-2), endaligned ] all five vertices of P remain vertices of Q, but [ PWidth(P)2=frac48353 quadandquad PWidth(Q)2=frac36133. ] Thus vertex insertion increases pyramidal width by the factor √1059/532≈ 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.