TY - JOUR
TI - Asymptotic enumeration of 2- and 3-SAT functions
DO - https://doi.org/doi:10.7282/T3DR2VJP
PY - 2010
AB - We are interested in the number, G(k,n), of Boolean functions of n variables definable by k-SAT formulae. First, in Chapter 2, we give an alternate proof of a conjecture of Bollobas, Brightwell and Leader, first proved by P. Allen, giving the asymptotics for G(2,n). One step in the proof determines the asymptotics of the number of "odd-blue-triangle-free" graphs on n vertices. Then, in Chapter 3, we prove asymptotics for G(3,n). This is a strong form of the case k=3 of a conjecture of Bollobas et al., that for fixed k asks for the asymptotics of the logarithm of G(k,n).
KW - Mathematics
KW - Combinatorial analysis
KW - Graph theory
KW - Hypergraphs
LA - eng
ER -