| We are interested in the number, Gk( 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, stating that G 2(n) is asymptotic to 2n+12 . 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 that G3( n) is asymptotic to 2n+n3 . This is a strong form of the case k = 3 of a conjecture of Bollobas et al. stating that for fixed k, log2 Gk(n) &sim ( nk ). |
