首页 | 本学科首页   官方微博 | 高级检索  
     


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^{left( begin{subarray}{l}   n    2 end{subarray}  right) + o(n^2 )} $$
2-SAT functions on n variables, and conjectured that in fact the number of 2-SAT functions on n variables is 
$$2^{left( begin{subarray}{l}   n    2 end{subarray}  right) + 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) < 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 
$$2^{left( begin{subarray}{l}   n    2 end{subarray}  right) + n_kn} $$
for all sufficiently large n.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号