Testing the max-flow min-cut property and the replication conjecture
2026-06-15 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a mathematical idea called the replication conjecture, which connects two properties of special set collections called clutters. They focus on a specific type of clutter related to something called the cuboid, where a graph structure has limited connections (degree at most δ). They show that any smallest counterexample to the conjecture must be within a certain size, making it possible to check all cases using a computer solver. Using this method, they confirmed the conjecture for cuboids with degree up to 9 and for clutters with up to 10 elements. Their approach also improves previous work by reducing the number of cases that need to be checked to verify the conjecture.
replication conjectureclutterpacking propertyMFMC propertycuboidHamming graphSAT solverinteger programmingcombinatorial optimizationweight vectors
Authors
Ahmad Abdi, Tamás Schwarcz
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 $δ$. The family of cuboids of degree at most $δ$ contains a rich source of clutters with the packing property, including all clutters over a ground set of size at most $δ$. We prove that any minimal counterexample must have dimension at most $δ$, 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,\ldots,t\right\}^n$ where $t\leq\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$.