Markovian protocols and an upper bound on the extension complexity of the matching polytope

2026/02/11 by M. Szusterman · 1 voice · 1 citation
Computer Science · #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.2602.11382

Abstract

This paper investigates the extension complexity of polytopes by exploiting the correspondence between non-negative factorizations of slack matrices and randomized communication protocols. We introduce a geometric characterization of extension complexity based on the width of Markovian protocols, as a variant of the framework introduced by Faenza et al. This enables us to derive a new upper bound of O(n³⋅ 1.5ⁿ) for the extension complexity of the matching polytope P_match(n), improving upon the standard 2ⁿ-bound given by Edmonds' description. Additionally, we recover Goemans' compact formulation for the permutahedron using a one-round protocol based on sorting networks.

Citations

• A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially
• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
• Extended formulations for polygons
• On the ratio of optimal integral and fractional covers
• Maximum matching and a polyhedron with 0,1-vertices

Discussions

• M. Szusterman: Markovian protocols and an upper bound on the extension complexity of the matching polytope https://arxiv.org/abs/2602.11382 https://arxiv.org/pdf/2602.11382 https://arxiv.org/html/2602 [bsky, 0 points, 0 comments]

Related

• The matching polytope has exponential extension complexity
• Extended formulations, non-negative factorizations and randomized communication protocols
• On the extension complexity of combinatorial polytopes
• Limitations of the Hyperplane Separation Technique for Bounding the Extension Complexity of Polytopes
• Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations