Ehrhart clutters: regularity and max-flow min-cut

José Martínez-Bernal ; Edwin O'Shea ; Rafael H. Villarreal

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

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.

Détail

DOI : 10.37236/324

Classification : 13H10, 52B20, 13D02, 13F55, 05C17, 05C65, 90C47
Mots-clés : graphs, clutters, Ehrhart clutters, Ehrhart rings