RUcore Resource Object
RUcore Resource Object
PDF-1(426.44 KB)
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,
Degree Date2010
Date Created2010
SubjectMathematics,
Combinatorial analysis,
Graph theory,
Hypergraphs
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).
NotePh.D.
NoteIncludes abstract
NoteVita
NoteIncludes bibliographical references
Noteby Liviu Vasile Ilinca
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000053609
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Statistical Profile