Id: arxiv/2611.15785 Url: https://arxiv.org/abs/2611.15785 Tags: math.OC Score: 0 Title: The One-Skeleton of Multilinear Polytopes and Their Standard Relaxations Domain: math.OC Source: arxiv Authors: Alberto Del Pia, Zihong Xu Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-11 Page: https://delphi.science/r/arxiv/2611.15785 Edge-following methods, such as the simplex method, move along edges of a polytope. Their behavior depends on which vertices are adjacent and on the diameter. We study both for the two polytopes of binary polynomial optimization: the multilinear polytope and its standard linear relaxation. For quadratic polynomials, Padberg showed that two integral vertices are adjacent in both polytopes if and only if the variables where they differ induce a connected subgraph. For higher degree, we replace this subgraph by a contracted hypergraph on the same variables, built from the monomials whose…