Linear singular-index conjecture for unsatisfiable hitting clause-sets

About 14 years old · traced to

Let UHIT ⁣δ=k\mathcal{U}\mathcal{HIT}_{\!\delta=k} be the class of unsatisfiable hitting clause-sets of deficiency kk. Let singind⁡(F)\operatorname{singind}(F) denote the singular index of FF, and let varsing⁡(F)\operatorname{varsing}(F) be the set of singular variables of FF. Linear singular-index conjecture. For every k∈Nk \in \mathbb{N} there are a∈Na \in \mathbb{N} and α∈R>0\alpha \in \mathbb{R}_{>0} such that, for all F∈UHIT ⁣δ=kF \in \mathcal{U}\mathcal{HIT}_{\!\delta=k} with singind⁡(F)≥a\operatorname{singind}(F) \geq a,

∣varsing⁡(F)∣≥α⋅singind⁡(F).\lvert\operatorname{varsing}(F)\rvert \geq \alpha \cdot \operatorname{singind}(F).

The conjecture asks for a quantitative relation between the singular index and the number of singular variables. The source presents it as an open question in its discussion of singular tuples; no resolution is supplied.

References

Primary source

Oliver Kullmann and Xishun Zhao, “On Davis-Putnam reductions for minimally unsatisfiable clause-sets”, arXiv:1202.2600 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.