Nearly all $k$-SAT functions are unate

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

doi:10.4171/jems/1791

Nearly all $k$-SAT functions are unate

Journal of the European Mathematical Society 2026 Open access

Read full text

Authors: József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, Yufei Zhao

DOI: 10.4171/jems/1791

Cited by: 0

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.

Fields of Study & Subjects

Coding theory and cryptography

Publication details

Journal / source: Journal of the European Mathematical Society
Publication date: 14 May 2026
Language: EN