Name
Abstract | ||
|---|---|---|
If C is a clutter with n vertices and q edges whose clutter matrix has column vectors A = {v(1),...,v(q)), we call C and Ehrhart clutter if {(v(1),1),..., (v(q),1)} subset of {0, 1}(n+1) is a Hilbert basis. Letting A(P) be the Ehrhart ring of P = conv(A), we are able to show that if C is a uniform unmixed MFMC clutter, then 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-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 related to total dual integrality. |
Year | Venue | Keywords |
|---|---|---|
2010 | ELECTRONIC JOURNAL OF COMBINATORICS | perfect graphs,hilbert bases.,a-invariant,clutters,regularity,max-flow min-cut,edge ideal,. ehrhart ring,perfect graph |
Field | DocType | Volume |
Perfect graph,Hilbert basis,Discrete mathematics,Combinatorics,Clique,Vertex (geometry),Matrix (mathematics),Max-flow min-cut theorem,Total dual integrality,Conjecture,Mathematics | Journal | 17.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 2 |
PageRank | References | Authors |
0.58 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jose Mart ´ õnez-Bernal | 1 | 2 | 0.58 |
| Edwin O'Shea | 2 | 3 | 0.94 |
| Rafael H. Villarreal | 3 | 75 | 15.69 |