TitleAsymptotic enumeration of 2- and 3-SAT functions
NameIlinca, Liviu (author), Kahn, Jeffry (chair), Beck, Jozsef (internal member), Szemeredi, Endre (internal member), Steger, Angelika (outside member), Rutgers University, Graduate School - New Brunswick,
DescriptionWe 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).
NoteIncludes bibliographical references
Noteby Liviu Vasile Ilinca
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.