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 $\delta$.
The family of cuboids of degree at most $\delta$ contains a rich source of clutters with the packing property, including all clutters over a ground set of size at most $\delta$. We prove that any minimal counterexample must have dimension at most $\delta$, 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$.
From: Ahmad Abdi [view email]
[v1]
Mon, 15 Jun 2026 10:47:22 UTC (41 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。