# Blog

Back to main | List of entries |

## Enumerating k-SAT functions

July 21, 2021

In a new paper coauthored with graduate students Dingding Dong and Nitya Mani titled *Enumerating k-SAT functions*, we study these fundamental questions about *k*-SAT functions:

- How many
*k*-SAT functions on*n*boolean variables are there? - What does a typical such function look like?

These questions about *k*-SAT functions were first studied by Bollobás, Brightwell, and Leader (2003), who made the following conjecture.

**Conjecture.** Fix $k \ge 2$. Almost all *k*-SAT functions are unate.

Here an *unate* *k*-SAT function is one that can be turned monotone by first negating some subset of variables.

More precisely, the conjecture says that, as $n \to \infty$, $1-o(1)$ fraction of all *k*-SAT functions on *n* boolean variables are unate.

An easy argument shows that there are $(1+o(1))2^{\binom{n}{k} + n}$ unate functions. So the above conjecture can be equivalently restated as:

**Conjecture.** Fix $k \ge 2$. The number of *k*-SAT functions on n boolean variables is $(1+o(1))2^{\binom{n}{k} + n}$.

The conjecture was previously proved for $k=2$ (Allen 2007) and $k=3$ (Ilinca and Kahn 2012) using the (hyper)graph regularity method.

In our new paper, using the hypergraph container method, we show that the *k*-SAT conjecture is essentially equivalent to a variant of an extremal hypergraph problem. Such extremal problems are related to hypergraph Turán density problems, which are notoriously difficult to solve in general, and for which there are lots of open problems and very few answers.

We solved our Turán problem for all $k \le 4$, thereby confirming the conjecture for a new value $k=4$.

Our solution to the Turán problem for $k=4$ uses a recent result in extremal graph theory by Füredi and Maleki (2017) determining the minimum density of triangular edges in a graph of given edge density.

Here is a Turán density conjecture whose resolution would imply the above conjecture for $k=5$, which is still open.

**Definition.** A *5-PDG* (*partially directed 5-graph*) is obtained from a 5-uniform hypergraph by “directing” some subset of its edges. Here every directed edge is “directed towards” one of its vertices.

**Conjecture.** There exists a constant $\theta > \log_2 3$ such that for every *n*-vertex 5-PDG with *A* undirected edges and *B* directed edges, if there do not exist three edges of the form

```
12345
1234 6
123 56
```

with at least one of these three edges directed towards 4, 5, or 6, then

\[A + \theta B \le (1+o(1))\binom{n}{5}.\]There are actually additional patterns that one could forbid as well for the purpose solving the *k*-SAT enumeration problem. In the paper we give an explicit description of all forbidden patterns. But the above single forbidden pattern might just be enough (it is enough for $k \le 4$).

Back to main | List of entries |

More posts:

- 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