Open problems on the combinatorics of conflicts between clauses

Status of open problems from the first report on the subject ("On the conflict matrix of clause-sets", University of Wales Swansea, Computer Science Report Series, CSR 7-2003)

List of problems from Section 8 of the above report, and their status:
  1. Open.
  2. Open.
  3. Open.
  4. Counterexample for Conjecture 5.2 found by Xishun Zhao.
  5. Xishun Zhao proved, that in fact every non-saturated minimally unsatisfiable clause-set with deficiency one is not exact.

    There are non-saturated minimally unsatisfiable clause-set with deficiency one which are not eigensharp.
  6. Xishun Zhao found a counterexample for Conjecture 5.3, an example for an eigensharp and unsatisfiable clause-set which is not linearly lean.
  7. The counterexample for Point 6 is also a counterexample for Conjecture 5.4.
  8. Open.
  9. Counterexample found by Xishun Zhao.
  10. Obviously, there are symmetric distance matrices with more positive than negative eigenvalues, and also with non-integral eigenvalues.
  11. Open.
  12. Open.

Oliver Kullmann
Last modified: Wed Jan 3 19:59:19 GMT 2007