EUVIMEDEUVIMED entdecken
Crossref

Nearly all $k$-SAT functions are unate

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

Journal of the European Mathematical Society · 14.05.2026

DOI: 10.4171/jems/1791 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the European Mathematical Society, erschienen am 14.05.2026. Verfasst von József Balogh und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Balogh, J., Dong, D., Lidický, B., Mani, N., & Zhao, Y. (2026). Nearly all $k$-SAT functions are unate. Journal of the European Mathematical Society. https://doi.org/10.4171/jems/1791

Vancouver

Balogh J, Dong D, Lidický B, Mani N, Zhao Y. Nearly all $k$-SAT functions are unate. Journal of the European Mathematical Society. 2026. doi:10.4171/jems/1791

BibTeX
@article{Balogh2026,
  author = {Balogh, József and Dong, Dingding and Lidický, Bernard and Mani, Nitya and Zhao, Yufei},
  title = {Nearly all $k$-SAT functions are unate},
  journal = {Journal of the European Mathematical Society},
  year = {2026},
  doi = {10.4171/jems/1791}
}
Kostenlos starten →