Combinatorics, Probability and Computing

Table of Contents - 2009 - Volume 18, Special Issue 05 (New Directions in Algorithms, Combinatorics and Optimization)  

Paper

On the Number of 2-SAT Functions

L. ILINCAa1 and J. KAHNa1†

a1 Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA (e-mail: ilinca@math.rutgers.edu, jkahn@math.rutgers.edu)

Abstract

We give an alternative proof of a conjecture of Bollobás, Brightwell and Leader, first proved by Peter Allen, stating that the number of Boolean functions definable by 2-SAT formulae is $(1+o(1))2^{\binom{n+1}{2}}$. $(1+o(1))2^{\scurvy{n+1}{2}}$. One step in the proof determines the asymptotics of the number of ‘odd-blue-triangle-free’ graphs on n vertices.

(Received May 20 2008)

(Revised February 10 2009)

(Online publication June 01 2009)

Footnotes

† Supported by NSF grant DMS0701175.