Note on Lift-and-Project Ranks and Antiblocker Duality

In [Aguilera N., Escalante M. and Nasini G. A generalization of the perfect graph theorem under the disjunctive index, Mathematics of Operations Research 27 (3) (2002) 460–469], it was studied the behavior of the disjunctive operator defined by Balas et al. [Balas E., Cornuéjols G. and Ceria S. A lift-and-project cutting plane algorithm for mixed 0-1 programs, Mathematical Programming 58 (1993) 295–324], in the context of the “antiblocker duality diagram” associated with the clique relaxation of the stable set polytope of a graph and its complement. A generalization of the Perfect Graph Theorem was obtained from the proof of the commutativity of the diagram in any number of iterations of the disjunctive operator. and Tunçel [Lipták L. and Tunçel L. Lift-and-Project Ranks and Antiblocker Duality, Operation Research Letters, to appear, Research Report: CORR 2003-16, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Canada(2003)] study, in the same context, the behavior of the lift-and-project operators N0, N and N+ defined by Lovász and Schrijver [Lovász L. and Schrijver A. Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optimization 1 (1991) 166–190]. They find a graph for which the diagram does not commute in one iteration of the N0– and N–operator. In connection with N+, the authors implicitly suggest a similar result proving that if the diagram commutes in k = O ( 1 ) iterations, P = NP . in purpose of this work is to show that the non commutativity of the diagram can be explicitly proved in any number of iterations of the N+–operator.