Ehrhart clutters: regularity and max-flow min-cut

MaRDI QIDQ976696zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/0902.1354, https://eudml.org/doc/231516, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r52.html

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

zbMATH Keywords

cluttersEhrhart cluttersEhrhart ringsgraphs

Mathematics Subject Classification ID

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

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.

Cited in

(4)

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

Describes a project that uses

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)