On exact blockers and anti-blockers, ΔΔ-conjecture, and related problems

Let us consider two binary systems of inequalities (i) Cx≥eCx≥e and (ii) Cx≤eCx≤e, where C∈{0,1}m×nC∈{0,1}m×n is an m×nm×n(0,1)(0,1)-matrix, x∈{0,1}nx∈{0,1}n, and ee is the vector of mm ones. The set of all support-minimal (respectively, support-maximal) solutions xx to (i) (respectively, to (ii)) is called the blocker (respectively, anti-blocker).A blocker BB (respectively, anti-blocker AA) is called exact   if Cx=eCx=e for every x∈Bx∈B (respectively, x∈Ax∈A).Exact blockers can be completely characterized. There is a one-to-one correspondence between them and P4P4-free graphs (along with a well-known one-to-one correspondence between the latter and the so-called read-once Boolean functions). However, the class of exact anti-blockers is wider and more sophisticated. We demonstrate that it is closely related to the so-called CIS graphs, more general ℓℓ-CIS dd-graphs, and ΔΔ-conjecture.