## View abstract

### Session I.3 - Graph Theory and Combinatorics

Tuesday, June 13, 14:00 ~ 15:00

## Nearly all k-SAT functions are unate

### Jozsef Balogh

#### University of Illinois, United States   -   This email address is being protected from spambots. You need JavaScript enabled to view it. document.getElementById('cloak6970ff2343af206edde0f420301ba5e6').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addy6970ff2343af206edde0f420301ba5e6 = 'j&#111;b&#97;l' + '&#64;'; addy6970ff2343af206edde0f420301ba5e6 = addy6970ff2343af206edde0f420301ba5e6 + '&#105;ll&#105;n&#111;&#105;s' + '&#46;' + '&#101;d&#117;'; var addy_text6970ff2343af206edde0f420301ba5e6 = 'j&#111;b&#97;l' + '&#64;' + '&#105;ll&#105;n&#111;&#105;s' + '&#46;' + '&#101;d&#117;';document.getElementById('cloak6970ff2343af206edde0f420301ba5e6').innerHTML += '<a ' + path + '\'' + prefix + ':' + addy6970ff2343af206edde0f420301ba5e6 + '\'>'+addy_text6970ff2343af206edde0f420301ba5e6+'<\/a>';

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 tends to infinity. This resolves a conjecture by Bollobas, Brightwell, and Leader. The proof uses among others the container method and the method of (computer-free) flag algebras.

Joint work with Dingding Dong (Harvard), Bernard Lidicky (Iowa State University), Nitya Mani (MIT) and Yufei Zhao (MIT).