Arithmetic relations in the set covering polyhedron of circulant clutters

Abstract

We study the structure of the set covering polyhedron of circulant clutters, P (Cnk), especially the properties related to contractions that yield other circulant clutters. Building on work by Cornuéjols and Novick, we show that if Cnk / N is isomorphic to Cn′k′, then certain algebraic relations must hold and N is the union of particular disjoint simple directed cycles. We also show that this property is actually a characterization. Based on a result by Argiroffo and Bianchi, who characterize the set of null coordinates of vertices of P (Cnk) as being one of such N's, we then arrive at other characterizations, one of them being the conditions that hold between the existence of vertices and algebraic relations of certain parameters. With these tools at hand, we show how to obtain by algebraic means some old and new results, without depending on Lehman's work as is traditional in the field.