Testing the max-flow min-cut property and the replication conjecture

Abstract

The replication conjecture [Conforti and Cornuéjols, 1993] states that every clutter with the packing property has the MFMC property. If true, this conjecture would have far-reaching consequences from integer programming and combinatorial optimization to commutative algebra. In this paper, we set out to verify the conjecture for the cuboid of a set-system in which the Hamming graph induced on the infeasible points has degree at most $\hat{I}´$. The family of cuboids of degree at most $\hat{I}´$ contains a rich source of clutters with the packing property, including all clutters over a ground set of size at most $\hat{I}´$. We prove that any minimal counterexample must have dimension at most $\hat{I}´$, thus making the target search space finite. We then use a state-of-the-art SAT solver to verify the replication conjecture for cuboids of degree at most $9$, and for clutters over at most $10$ elements. Our computational verification relies crucially on another theoretical result, that to verify the MFMC property of a clutter over $n$ elements, it suffices to check finitely many weight vectors, namely $w\in {\left\{0,1,\dots ,t\right\}}^n$ where $t\le \max \{\lceil n/2\rceil ,\lfloor n-\sqrt{4n+1}+1\rfloor \}$. The upper bound of $t$ improves the previous best upper bound by algebraists, which could be exponential in $n$.

31 pages, 1 figure. (Added a subsection in the introduction focussing on applications to commutative algebra.)