# Blog

Back to main | List of entries |

## Nearly all k-SAT functions are unate

September 19, 2022

The Boolean satisfiability problem, specifically *k*-SAT, occupies a central place in theoretical computer science.
Here is a question that had been open until just now:
what does a typical *k*-SAT function look like?
Bollobás, Brightwell, and Leader (2003) initiated the study of this question, and they conjectured that a typical *k*-SAT function is unate (meaning monotone up to first negating some variables; more on this below.)

In a new preprint with the above coauthors (Dingding and Nitya are PhD students), we completely settle the Bollobás–Brightwell–Leader conjecture.

**Theorem.** Fix *k*. A $1-o(1)$ proportion of all *k*-SAT functions on *n* Boolean variables are unate, as $n \to \infty$.

Some special cases were known earlier: $k=2$ by Allen (2007) and $k=3$ by Ilinca and Kahn (2012).

As a reminder, a *k*-SAT function is a function
\(f \colon \{ 0, 1 \}^n \to \{0,1\}\)
that is expressible as a formula of the form

(here $\land$ = AND) where each “clause” $C_i$ is an OR of at most $k$ literals (each “literal” is some $x_i$ or its negation $\overline{x_i}$).
Such a function or formula is called *monotone* if the negatives literals $\overline{x_i}$ do not appear.
Furthermore, the function/formula is called *unate* if each variable $x_i$ either appears only in its positive form or only in its negative form, but not both simultaneously.

Here is an example of a unate 3-SAT function:

\[(x_1 \lor \overline{x_2} \lor x_3) \land (x_1 \lor \overline{x_2} \lor \overline{x_4}) \land \cdots \land (x_3 \lor \overline{x_4} \lor x_5)\](the variables $x_1$, $x_3$, $x_5$ appear only in their positive form, and the variables $x_2$, $x_4$ only appear in their negative form).

Our new paper is the second half of a two-part work proving the Bollobás-Brightwell-Leader conjecture.

The first part, by Dingding Dong, Nitya Mani, and myself (reported earlier on this blog) reduces the Bollobás–Brightwell–Leader conjecture to a Turán problem on partially directed hypergraphs. The reduction applies the hypergraph container method, a major recent development in combinatorics.

I presented the first part in an Oberwolfach meeting earlier this year, which led to a successful collaboration with József Balogh and Bernard Lidický that resulted in a complete solution to the problem.

In this short new paper we solve the relevant Turán problem. Our solution is partly inspired by the method of flag algebras introduced by Razborov.

We actually prove a stronger statement. A *k*-SAT formula is said to be *minimal* if deleting any clause changes the function. We prove:

**Theorem.** Fix *k*. A $1−o(1)$ proportion of all minimal *k*-SAT formulae on *n* Boolean variables are unate, as $n \to \infty$.

As suggested by Bollobás, Brightwell, and Leader, these results open doors to a *theory of random k-SAT functions*. For example, we now know the following.

**Corollary.** A typical *k*-SAT function admits a unique minimal *k*-SAT formula, and furthermore the formula has $(1/2 + o(1)) \binom{n}{k}$ clauses.

This model is very different from that of random *k*-SAT formulae where clauses are added at random (e.g., the recent breakthrough of Ding–Sun–Sly on the satisfiability conjecture).
Rather, our result concerns a random *k*-SAT formula conditioned on minimality. In this light, our results are analogous to the theory of Erdős–Rényi random graphs $G(n, p)$ with constant edge probability $p$.
It would be interesting to further study the behavior of sparser random *k*-SAT formulae conditioned on minimality.
This potentially leads to a rich source of problems on thresholds and typical structures.

Back to main | List of entries |

More posts:

- Mehtaab Sawhney wins Clay Research Fellowship 1/25/2024
- Papers by MIT combinatorialists—Fall 2023 12/22/2023
- Schildkraut: Equiangular lines and large multiplicity of fixed second eigenvalue 3/6/2023
- Nearly all k-SAT functions are unate 9/19/2022
- Kwan–Sah–Sawhney–Simkin: High-girth Steiner triple systems 1/13/2022
- Graphs with high second eigenvalue multiplicity 9/28/2021
- Enumerating k-SAT functions 7/21/2021
- Mathematical tools for large graphs 7/12/2021
- How I manage my BibTeX references, and why I prefer not initializing first names 7/4/2021
- The cylindrical width of transitive sets 1/28/2021
- Ashwin Sah and Mehtaab Sawhney win the Morgan Prize 10/29/2020
- Jain–Sah–Sawhney: Singularity of discrete random matrices 10/13/2020
- Gunby: Upper tails for random regular graphs 10/5/2020
- Joints of varieties 9/12/2020
- Ashwin Sah's new diagonal Ramsey number upper bound 5/20/2020
- Joints tightened 11/21/2019
- Equiangular lines with a fixed angle 7/30/2019
- Impartial digraphs 6/27/2019
- A reverse Sidorenko inequality 9/26/2018
- The number of independent sets in an irregular graph 5/12/2018