Ehrhart clutters: Regularity and Max-Flow Min-Cut

Details Ehrhart clutters: Regularity and Max-Flow Min-Cut Ehrhart clutters: Regularity and Max-Flow Min-Cut

2009-02-09

arxiv.org/abs/0902.1354v3

Electron. J.Combin. 17 (2010), no. 1, R52

Mathematics

Commutative Algebra

Electronic Journal of Combinatorics, to appear

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Ehrhart clutters: Regularity and Max-Flow Min-Cut does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ehrhart clutters: Regularity and Max-Flow Min-Cut, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ehrhart clutters: Regularity and Max-Flow Min-Cut will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-175972