Home
Resource
Asymptotic enumeration of 2- and 3-SAT functions
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(426.44 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Ilinca, Liviu. Asymptotic enumeration of 2- and 3-SAT functions. Retrieved from https://doi.org/doi:10.7282/T3DR2VJP

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

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
Date Created2010
Other Date2010 (degree)
SubjectMathematics, Combinatorial analysis, Graph theory, Hypergraphs
Extentvi, 84 p. : ill.
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, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3DR2VJP
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.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024