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 -