The Anti-join Composition and Polyhedra

In this paper we describe a binary composition operation, the anti-join, which combines a pair of clutters L1 and L2 to give a new clutter L. The anti-join operation is, in some sense, the ''dual'' of the join operation, introduced by Cunningham [10]. In fact, it has the property that the blocker of the clutter L obtained by joining two clutters L1 and L2, is the anti-join of the blockers of L1 and L2. For such an operation we show how the linear descriptions of the polyhedra Q(L1) and Q(L2) have to be combined to produce a linear description of the polyhedron Q(L). Moreover, given a set F subset-or-equal-to {lambda: 0 less-than-or-equal-to lambda less-than-or-equal-to 1} such that {0, 1} subset-or-equal-to F and a is-an-element-o F if and only if (1-a) is-an-element-of F, we define the F-property for covering polyhedra as a proper generalization of the Fulkerson property, to which it reduces for F = {0, 1}. We prove that the anti-join operation preserves the F-property. This implies the characterization of the coefficients of the facet-defining inequalities for the cycle and cocycle polyhedra associated with graphs noncontractible to the four-wheel W4.