The Combinatorics of Conflicts between Clauses

摘要

We study the symmetric conflict matrix of a multi-clause-set, where the entry at position (i, j) is the number of clashes between clauses i and j. The conflict matrix of a multi-clause-set, either interpreted as a multi-graph or a distance matrix, yields a new link between investigations on the satisfiability problem (in a wider sense) and investigations on the bicligue partition number and on the addressing problem (introduced by Graham and Poltak) in graph theory and combinatorics. An application is given by the well-known class of what are called l-uniform hitting clause-sets in this article, where each pair of (different) clauses clash in exactly one literal. Endre Boros conjectured at the SAT'98 workshop that each l-uniform hitting clause-set of deficiency 1 contains a literal occurring only once. Kleine Buning and Zhao showed, that under this assumption every l-uniform hitting clause-set must have deficiency at most 1. We show that the conjecture is false (there are known starfree biclique decompositions of every complete graph with at least nine vertices), but the conclusion is right (a special case of the Graham-Pollak theorem, attributed to Witsenhausen). A basic notion for investigations on the combinatorics of clause-sets is the deficiency of multi-clause-sets (the difference of the number of clauses and the number of variables). We introduce the related notion of hermitian defect, based on the notion of the hermitian rank of a hermitian matrix introduced by Gregory, Watts and Shader. The notion of hermitian defect makes it possible to combine eigenvalue techniques (especially Cauchy's interlacing inequalities) with matching techniques, and can be seen as the underlying subject of our introduction into the subject.