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

Download PDF

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