Almost every 2-SAT function is unate |
| |
Authors: | Peter Allen |
| |
Affiliation: | (1) Department of Mathematics, London School of Economics, Houghton St., London, WC2A 2AE, UK |
| |
Abstract: | Bollobás, Brightwell and Leader [2] showed that there are at most 2-SAT functions on n variables, and conjectured that in fact the number of 2-SAT functions on n variables is . 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) < n 1/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 for all sufficiently large n. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|