Sách Ehrhart clutters: Regularity and Max-Flow Min-Cut

Thảo luận trong 'Sách Ngoại Ngữ' bắt đầu bởi Thúy Viết Bài, 5/12/13.

  1. Thúy Viết Bài

    Thành viên vàng

    Bài viết:
    198,891
    Được thích:
    173
    Điểm thành tích:
    0
    Xu:
    0Xu
    If C is a clutter with n vertices and q edges whose clutter matrix has column vectors A = {v1, . , vq}, we call C an Ehrhart clutter if {(v1, 1), . , (vq, 1)} ⊂ {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 ainvariant of A(P). Motivated by the Conforti-Cornu´ejols 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.
     

    Các file đính kèm: