Conforti-Cornuéjols conjecture on the MFMC property
From Egres Open
(Redirected from Clutters with the MFMC property)
Is it true that a clutter has the MFMC property if and only if it has the packing property?
Remarks
This was conjectured by Conforti and Cornuéjols [1]. Some classes where the conjecture is known to hold:
- A clutter is binary if every member of its blocker intersects each member of the clutter in an odd number of elements. Seymour[2] proved that an ideal binary clutter has the MFMC propery if and only if it does not have a [math]{\mathcal Q}_6[/math] minor (one way to define [math]{\mathcal Q}_6[/math] is that the ground set is the edge set of [math]K_4[/math], and the hyperedges are the triangles). This implies the conjecture for binary clutters because [math]{\mathcal Q}_6[/math] does not have the packing property.
- A clutter is diadic if every member of its blocker intersects each member of the clutter in at most 2 elements. It is shown in [3] that a diadic clutter is ideal if and only if it has the MFMC property. This implies the conjecture because every clutter with the packing property is ideal.
