Nearly all $k$-SAT functions are unate

József Balogh; Dingding Dong; Bernard Lidický; Nitya Mani; Yufei Zhao

doi:10.4171/jems/1791

JournalsjemsOnline First

Nearly all $k$ -SAT functions are unate

József Balogh
University of Illinois Urbana-Champaign, USA
Dingding Dong
Harvard University, Cambridge, USA
Bernard Lidický
Iowa State University, Ames, USA
Nitya Mani
Massachusetts Institute of Technology, Cambridge, USA
Yufei Zhao
Massachusetts Institute of Technology, Cambridge, USA

A subscription is required to access this article.

Abstract

We prove that a $1 - o (1)$ fraction of all $k$ -SAT functions of $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.

Cite this article

József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, Yufei Zhao, Nearly all $k$ -SAT functions are unate. J. Eur. Math. Soc. (2026), published online first

DOI 10.4171/JEMS/1791