Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T15:11:41.135Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Number of 2-SAT Functions

Published online by Cambridge University Press:  01 September 2009

L. ILINCA  and
J. KAHN
L. ILINCA
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA (e-mail: ilinca@math.rutgers.edu, jkahn@math.rutgers.edu)
J. KAHN
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA (e-mail: ilinca@math.rutgers.edu, jkahn@math.rutgers.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

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

[1]Allen, P. (2007) Almost every 2-SAT function is unate. Israel J. Math. 161 311–346.CrossRefGoogle Scholar
[2]Bollobás, B., Brightwell, G. and Leader, I. (2003) The number of 2-SAT functions. Israel J. Math. 133 45–60.CrossRefGoogle Scholar
[3]Brightwell, G. (2008) Personal communication.Google Scholar
[4]Erdős, P., Kleitman, D. J. and Rothschild, B. L. (1976) Asymptotic enumeration of Kn-free graphs. In Colloquio Internazionale sulle Teorie Combinatorie (Rome 1973), Vol. II, Accad. Naz. Lincei, Rome, pp. 19–27.Google Scholar
[5]Kleitman, D. J. and Rothschild, B. L. (1975) Asymptotic enumeration of partial orders on a finite set. Trans. Amer. Math. Soc. 205 205–220.CrossRefGoogle Scholar
[6]Prömel, H. J., Schickinger, T. and Steger, A. (2002) A note on triangle-free and bipartite graphs. Discrete Math. 257 531–540.CrossRefGoogle Scholar
[7]Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Orsay 1976), CNRS, Paris, pp. 399–401.Google Scholar