<p>For arbitrarily large number <span class="math-container">$n$</span> of variables, the following CNF formula <span class="math-container">$\phi$</span> is not satisfiable, has only three clauses, and a <span class="math-container">$2K_2$</span>-free clause-variable incidence graph:</p>
<p><span class="math-container">$C_1=(x_1)$</span>, <span class="math-container">$C_2=(\neg x_1)$</span>, <span class="math-container">$C_3=(x_1,\ldots,x_n)$</span>.</p>
<p>Thus, to get more interesting lower bounds one needs to make assumption about the minimum clause size or about the size of classes of clauses that contain the same variables (i.e. that have identical neighborhoods in the clause-variable incidence graph).</p>
<p>Observe that when the minimum clause size is <span class="math-container">$k$</span>, then the example above can be adapted to give formulas with <span class="math-container">$2^k+1$</span> clauses and arbitrarily large number of variables <span class="math-container">$n$</span> that are not satisfiable. Moreover, when the number of clauses is <span class="math-container">$m&lt;2^k+1$</span>, then the formula is satisfiable even for arbitrarily large <span class="math-container">$n&gt;k$</span>: Let <span class="math-container">$C_m$</span> be the clause that has is incident with the largest set of variables. Since <span class="math-container">$n&gt;k$</span>, there is a variable <span class="math-container">$y$</span> that is not contained in the variable set of <span class="math-container">$C_1$</span>, the clause with the smallest set of incident variables. Now, as for <span class="math-container">$k$</span>-CNF formulas, the clauses <span class="math-container">$C_1,\ldots,C_{m-1}$</span> can be satisfied via an assignment of the first <span class="math-container">$k$</span> variables (which they all contain) and <span class="math-container">$C_m$</span> can be satisfied via the appropriate assignment of <span class="math-container">$y$</span>.</p>

CC BY-SA 4.0
2020-10-26T12:50:08.317Z
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
CC BY-SA 4.0
2020-10-26T12:36:06.823Z
2020-10-26T12:36:06.823Z
Christian Komusiewicz
<p>I am interested in generalisations of the following observation:</p>
<p><strong>An unsatisfiable <span class="math-container">$k$</span>-CNF has at least <span class="math-container">$2^k$</span> clauses.</strong></p>
<p>A special case of the observation is when <span class="math-container">$k=n$</span>, where <span class="math-container">$n$</span> is the number of variables. In this case, the clause-variable incidence graph is a complete bipartite graph.</p>
<p>I am particularly interested in the question:</p>
<p><strong>Is there a lower bound on the number of clauses in a CNF <span class="math-container">$\phi$</span>, in terms of the number of variables of <span class="math-container">$\phi$</span>, when the clause-variable incidence graph of <span class="math-container">$\phi$</span> is <span class="math-container">$2K_2$</span>-free (i.e. is a bipartite chain graph)?</strong></p>
<p>But I am also interested in any generalisation of that question, or references to papers on questions about CNFs with this extremal flavour.</p>
<p>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.</p>

CC BY-SA 4.0
2020-10-26T08:31:11.700Z
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
CC BY-SA 4.0
2020-10-26T10:31:01.507Z
@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
<reference-request><graph-theory><sat>
The number of clauses in an unsatisfiable CNF
Christopher Purcell
# The number of clauses in an unsatisfiable CNF

(Asked by: username_0 on 2020-10-25)

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 username_1 for highlighting that my question was ambiguous. The lower bound I'm after should be a function of the number of variables.

**Tags:** reference-request, graph-theory, sat

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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!  

---

## 1 answers

### Answer by username_1 on 2020-10-26. Score: 4 | Accepted answer

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)$.

Thus, to get more interesting lower bounds one needs to make assumption about the minimum clause size or about the size of classes of clauses that contain the same variables (i.e. that have identical neighborhoods in the clause-variable incidence graph).

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$.

> **Comments:**
> **username_0**: 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.  

---

