Linear singular-index conjecture for unsatisfiable hitting clause-sets

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 kNk \in \mathbb{N} there are aNa \in \mathbb{N} and αR>0\alpha \in \mathbb{R}_{>0} such that, for all FUHIT ⁣δ=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.

Sources & referencesView supporting material

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.