Nearly all k-SAT Functions are Unate

on YouTube ↗01h 05m

" summary

Proves that for every fixed k a 1-o(1) fraction of k-SAT Boolean functions on n variables are unate, resolving the Bollobás–Brightwell–Leader conjecture. The proof reduces counting minimal k-SAT DNFs to an extremal problem on partially directed k‑uniform hypergraphs, uses the hypergraph container method to get containers that are semisimple formulae, and completes the Turán-style bound with a short computer‑guided flag algebras (sum‑of‑squares) certificate. Outcome: almost all k‑SAT functions are unate and most have a unique minimal formula; the argument currently requires k fixed.

AI-written summary · about

" chapters (9)

1. 0:00Introduction
2. 2:38Main theorem on k-SAT functions
3. 6:30Problem and historical context
4. 14:45Combinatorial enumeration techniques
5. 25:05k-SAT functions and forbidden subgraphs
6. 31:57Container method and semisimple formulae
7. 44:57Extremal problem for hypergraphs
8. 51:23Future directions in k-SAT theory
9. 1:04:00Question and answer session