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:
- Open.
- Open.
- Open.
- Counterexample for Conjecture 5.2 found by Xishun Zhao.
- 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.
- Xishun Zhao found a counterexample for Conjecture 5.3, an example for an eigensharp and unsatisfiable clause-set which is not linearly lean.
- The counterexample for Point 6 is also a counterexample for Conjecture 5.4.
- Open.
- Counterexample found by Xishun Zhao.
- Obviously, there are symmetric distance matrices with more positive than negative eigenvalues, and also with non-integral eigenvalues.
- Open.
- Open.
Oliver Kullmann
Last modified: Wed Jan 3 19:59:19 GMT 2007