Faculty Digital Archive

Archive@NYU >
Stern School of Business >
IOMS: Statistics Working Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2451/14786

Title: ALMOST PERFECT MATRICES AND GRAPHS
Authors: Padberg, M.
Issue Date: Oct-1998
Publisher: Stern School of Business, New York University
Series/Report no.: SOR-99-5
Abstract: We introduce the notions of w-projection and k-projection that map almost integral polytopes associated with almost perfect graphs G with n nodes from Rn into Rn-w where w is the maximum clique size in G. We show that C. Berge's strong perfect graph conjecture is correct if and only if the projection (of either kind) of such polytopes is again almost integral in Rn-w. Several important properties of w-projections and k-projections are established. We prove that the strong perfect graph conjecture is wrong if an w-projection and a related k-projection of an almost integral polytope with 2 ≤ w ≤ (n - 1)/2 produce different polytopes in Rn-w.
URI: http://hdl.handle.net/2451/14786
Appears in Collections:IOMS: Statistics Working Papers

Files in This Item:

File Description SizeFormat
SOR-99-5.pdf705.55 kBAdobe PDFView/Open

Items in Faculty Digital Archive are protected by copyright, with all rights reserved, unless otherwise indicated.

 

The contents of the FDA may be subject to copyright, be offered under a Creative Commons license, or be in the public domain.
Please check items for rights statements. For information about NYU’s copyright policy, see http://www.nyu.edu/footer/copyright-and-fair-use.html 
Valid XHTML 1.0 | CSS