2025/05/20 by Ahmad Abdi, Gérard Cornuéjols, Abdi, Ahmad +4
Computer Science · Mathematics · #03-XX #05Cxx #05Dxx #52-XX #90Cxx #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2505.14497
openalex publication_date 2025/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set-system S⊆ \0,1\n is cube-ideal if its convex hull can be described by capacity and generalized set covering inequalities. In this paper, we use combinatorics, convex geometry, and polyhedral theory to give exponential lower bounds on the size of cube-ideal set-systems, and linear lower bounds on their VC dimension. We then provide applications to graph theory and combinatorial optimization, specifically to strong orientations, perfect matchings, dijoins, and ideal clutters, including the Lovász-Plummer conjecture.