Article contents
On the Number of 2-SAT Functions
Published online by Cambridge University Press: 01 September 2009
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 . One step in the proof determines the asymptotics of the number of ‘odd-blue-triangle-free’ graphs on n vertices.
- Type
- Paper
- Information
- Combinatorics, Probability and Computing , Volume 18 , Issue 5: New Directions in Algorithms, Combinatorics and Optimization , September 2009 , pp. 749 - 764
- Copyright
- Copyright © Cambridge University Press 2009
References
- 2
- Cited by