Ehrhart clutters: regularity and max-flow min-cut

zbMATH Open1189.13021arXiv0902.1354MaRDI QIDQ976696FDOQ976696

Authors: José Martínez-Bernal, Edwin O'Shea, Rafael H. Villarreal 

Publication date: 16 June 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: If C is a clutter with n vertices and q edges whose clutter matrix has column vectors V={v1,...,vq}, we call C an Ehrhart clutter if {(v1,1),...,(vq,1)} is a Hilbert basis. Letting A(P) be the Ehrhart ring of P=conv(V), we are able to show that if A is the clutter matrix of a uniform, unmixed MFMC clutter C, then C is an Ehrhart clutter and in this case we provide sharp bounds on the Castelnuovo-Mumford regularity of A(P). Motivated by the Conforti-Cornuejols conjecture on packing problems, we conjecture that if C is both ideal and the clique clutter of a perfect graph, then 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 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.

Full work available at URL: https://arxiv.org/abs/0902.1354

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graphscluttersEhrhart cluttersEhrhart rings

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Hypergraphs (05C65) Syzygies, resolutions, complexes and commutative rings (13D02) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Perfect graphs (05C17) Special types (Cohen-Macaulay, Gorenstein, Buchsbaum, etc.) (13H10)

Cited In (4)

• Implosive graphs: square-free monomials on symbolic Rees algebras
• Algebraic methods for parameterized codes and invariants of vanishing ideals over finite fields
• On ideal clutters, metrics and multiflows
• Minimizing clutter using absence in Venn-\(\text i^{\text e}\)

Uses Software

• polymake

This page was built for publication: Ehrhart clutters: regularity and max-flow min-cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976696)