The anti-join composition and polyhedra (Q688264)

Given a clutter \(\mathcal L\), i.e. a collection of pairwise incomparable finite sets, \(Q({\mathcal L})\) the associated covering polytope is defined as the dominant of the convex hull of all covers of \(\mathcal L\). A cover \(C\) of \(\mathcal L\) is by definition a set having nonempty intersection with every element of \(\mathcal L\) and every cover is silently identified with the corresponding incidence vector. A binary operation between clutters \({\mathcal L}:= L_ 1\circ L_ 2\), called anti-join, is defined. In the special case of all trees or cotrees of a graph, the anti-join reduces to the known merge operation. It is shown that a linear description of the polytope \(Q({\mathcal L}_ 1\circ {\mathcal L}_ 2)\) can be obtained from linear descriptions of polytopes \(Q({\mathcal L}_ 1)\) and \(Q({\mathcal L}_ 2)\). A so-called \({\mathcal F}\)-property, generalizing the Fulkerson property for covering polyhedra, is found to be preserved by the anti-join operation.