Nearly all $k$-SAT functions are unate

Abstract

We prove that $1-o(1)$ fraction of all $k$-SAT functions on $n$ Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer $k$ and as $n\to \infty$. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.

arXiv comment43 pages. v2 merges arXiv:2107.09233 (SODA22) and arXiv:2209.04894v1 (STOC23) along with expository improvements. This combined version is intended for journal submission