A proof for Padberg's conjecture on rank of matching polytope

2013/09/05 by Ashwin Arulselvan, Arulselvan, Ashwin, Daniel Karch +1
Computer Science · Mathematics · #90C10 #90C57 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Point processes and geometric inequalities #cs.DS #math.CO #msc:90C10 #msc:90C57

paper · pdf · doi:10.48550/arxiv.1309.1347

arxiv created 2013/09/05 · openalex publication_date 2013/09/05 · arxiv updated 2013/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Padberg introduced a geometric notion of ranks for (mixed) integer rational polyhedrons and conjectured that the geometric rank of the matching polytope is one. In this work, we prove that this conjecture is true.

Related

• Every rational polyhedron has finite split rank: new proof
• A "Challenging Question" of Björner from 1976: Every Infinite Geometric Lattice of Finite Rank Has a Matching
• Reverse Chvátal-Gomory rank
• Reverse Split Rank
• On the rank of Suzuki polytopes: an answer to Hubard and Leemans