Almost every 2-SAT function is unate
Allen, P.
(2007).
Almost every 2-SAT function is unate.
Israel Journal of Mathematics,
161(1), 311-346.
https://doi.org/10.1007/s11856-007-0081-z
Bollob´as, Brightwell and Leader showed that there are at most 2^(n 2)+o(n2) 2-SAT functions on n variables, and conjectured that in fact the number of 2-SAT functions on n variables is 2^(n 2)+n(1 + o(1)). We prove their conjecture. As a corollary of this, we also find the expected number of satisfying assignments of a random 2-SAT function on n variables. We also find the next largest class of 2-SAT functions and show that if k = k(n) is any function with k(n) < n1/4 for all sufficiently large n, then the class of 2-SAT functions on n variables which cannot be made unate by removing 25k variables is smaller than 2(n 2)+n−kn for all sufficiently large n.
| Item Type | Article |
|---|---|
| Copyright holders | © 2007 Springer |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1007/s11856-007-0081-z |
| Date Deposited | 28 May 2012 |
| URI | https://researchonline.lse.ac.uk/id/eprint/44103 |
Explore Further
- http://www.lse.ac.uk/Mathematics/people/Peter-Allen.aspx (Author)
- https://www.scopus.com/pages/publications/58449135458 (Scopus publication)
- http://www.springerlink.com/content/0021-2172/ (Official URL)
ORCID: https://orcid.org/0000-0001-6555-3501