Showing 2025Show all
3 papers · 1 filter
math.CO2025
The rainbow covering number of clean tangled clutters
Ahmad Abdi, Gérard Cornuéjols
In this brief note, we prove a min-min equality for a clean tangled clutter, that the rainbow covering number is equal to the connectivity of its setcore.
math.CO2025
Lower bounds for cube-ideal set-systems
Ahmad Abdi, Gérard Cornuéjols, Daniel Dadush +1
A set-system is cube-ideal if its convex hull can be described by capacity and generalized set covering inequalities. In this paper, we use combinatorics, co…
math.CO2025
A Min-Max Relation on Dicuts and Dijoins in Weighted Chordal Digraphs
Gérard Cornuéjols, Siyue Liu, R. Ravi
In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles conjectured that in a weighted…