Ehrhart Clutters: Regularity and Max-Flow Min-Cut

Abstract

If $\mathcal{C}$ is a clutter with $n$ vertices and $q$ edges whose clutter matrix has column vectors ${\mathcal A} = \{v_1, \ldots, v_q\}$, we call $\mathcal{C}$ an Ehrhart clutter if $\{(v_1,1),\ldots,(v_q,1)\} \subset \{ 0,1 \}^{n+1}$ is a Hilbert basis. Letting $A(P)$ be the Ehrhart ring of $P={\rm conv}(\mathcal{A})$, we are able to show that if $\mathcal{C}$ is a uniform unmixed MFMC clutter, then $\mathcal{C}$ is an Ehrhart clutter and in this case we provide sharp upper bounds on the Castelnuovo-Mumford regularity and the $a$-invariant of $A(P)$. Motivated by the Conforti-Cornuéjols conjecture on packing problems, we conjecture that if $\mathcal{C}$ is both ideal and the clique clutter of a perfect graph, then $\mathcal{C}$ has the MFMC property. We prove this conjecture for Meyniel graphs by showing that the clique clutters of Meyniel graphs are Ehrhart clutters. In much the same spirit, we provide a simple proof of our conjecture when $\mathcal{C}$ is a uniform clique clutter of a perfect graph. We close with a generalization of Ehrhart clutters as it relates to total dual integrality.