Consequences of the packing problem (Q825535)

In this paper, the authors study consequences of the Conforti-Cornuéjols conjecture. They focus on three results that follow from the conjecture and show that these results must hold. More specifically, a square-free monomial ideal \(I\) in a polynomial ring \(R\) is König if its height is equal to its matching number, which is the maximum size of a subset of generators with pairwise disjoint support. The ideal satisfies the packing property if it and all of its minors corresponding to vertex deletion and contraction in the associated hypergraphs (which can be viewed as setting subsets of the variables to \(0\) and \(1\)) satisfy the König property. Conforti-Cornuéjols conjecture that the packing property is equivalent to the max-flow-min-cut property of combinatorial optimization. \textit{I. Gitler} et al. [Beitr. Algebra Geom. 48, No. 1, 141--150 (2007; Zbl 1114.13007)] translated this into algebra by showing that an ideal \(I\) satisfies the max-flow-min-cut property if and only if all of the ordinary and symbolic powers coincide, that is, \(I^n = I^{(n)}\) for all \(n \geq 1\). In this paper, the authors show that three statements that would follow from a proof of the conjecture are all true. Each statement has a different mathematical flavor. Numerically, the authors show that the initial degree of a square-free monomial ideal \(I\) that satisfies the packing property is equal to its Waldschmidt constant, which encodes an asymptotic degree for \(I^{(n)}\). Geometrically, they show that the Newton polyhedron and the symbolic polyhedron of a square-free monomial ideal \(I\) that satisfies the packing property are equal. Regarding linear programming, they show that if the symbolic and Newton polyhedra of a square-free monomial ideal that satisfies the packing property are the feasible sets for two linear programs, then those programs have equal optimal values. The Alexander dual of a square-free monomial ideal is used throughout the paper. Additionally, the authors show that if \(I\) is a square-free monomial ideal such that both \(I\) and its Alexander dual \(I^{\vee}\) are equidimensional, the \(I\) satisfies the packing property if an only if \(I^{\vee}\) does.