# The number of clauses in an unsatisfiable CNF

I am interested in generalisations of the following observation:

An unsatisfiable $$k$$-CNF has at least $$2^k$$ clauses.

A special case of the observation is when $$k=n$$, where $$n$$ is the number of variables. In this case, the clause-variable incidence graph is a complete bipartite graph.

I am particularly interested in the question:

Is there a lower bound on the number of clauses in a CNF $$\phi$$, in terms of the number of variables of $$\phi$$, when the clause-variable incidence graph of $$\phi$$ is $$2K_2$$-free (i.e. is a bipartite chain graph)?

But I am also interested in any generalisation of that question, or references to papers on questions about CNFs with this extremal flavour.

EDIT: Thanks to Christian Komusiewicz for highlighting that my question was ambiguous. The lower bound I'm after should be a function of the number of variables.

• I am assuming the lower bound should be again for insatisfiable clauses? In what quantity should the lower bound be measured? The number of variables? Or some property of the clause-variable incidence graph? – Christian Komusiewicz Oct 26 at 8:31
• @ChristianKomusiewicz sorry my question was indeed ambiguous. I am interested in a lower bound in terms of the number of variables. I have edited now, thanks! – Christopher Purcell Oct 26 at 10:31

For arbitrarily large number $$n$$ of variables, the following CNF formula $$\phi$$ is not satisfiable, has only three clauses, and a $$2K_2$$-free clause-variable incidence graph:
$$C_1=(x_1)$$, $$C_2=(\neg x_1)$$, $$C_3=(x_1,\ldots,x_n)$$.
Observe that when the minimum clause size is $$k$$, then the example above can be adapted to give formulas with $$2^k+1$$ clauses and arbitrarily large number of variables $$n$$ that are not satisfiable. Moreover, when the number of clauses is $$m<2^k+1$$, then the formula is satisfiable even for arbitrarily large $$n>k$$: Let $$C_m$$ be the clause that has is incident with the largest set of variables. Since $$n>k$$, there is a variable $$y$$ that is not contained in the variable set of $$C_1$$, the clause with the smallest set of incident variables. Now, as for $$k$$-CNF formulas, the clauses $$C_1,\ldots,C_{m-1}$$ can be satisfied via an assignment of the first $$k$$ variables (which they all contain) and $$C_m$$ can be satisfied via the appropriate assignment of $$y$$.
• That's very helpful thank you. A follow up comment: what if we know something about the number or size of the classes of clauses (having identical neighbourhoods)? Say there are $j$ classes, or that we know the size of a class is super-constant in the number of variables or something like that. – Christopher Purcell Oct 26 at 12:50