On the number of 2-SAT functions

DOI10.1017/S096354830900995XMaRDI QIDQ3552502zbMATHFDO

Authors L. Ilinca, J. Kahn

Publication date 22 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.2863

zbMATH Keywords

2-SAT formulae`odd-blue-triangle-free' graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Boolean functions (06E30)

Abstract: We give an alternative proof of a conjecture of Bollob'as, 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.

Recommendations

• The number of 2-SAT functions
• The number of satisfying assignments of random 2‐SAT formulas
• Almost every 2-SAT function is unate
• The number of 3-SAT functions
• The number of k‐SAT functions

Cites work

• A note on triangle-free and bipartite graphs
• Almost every 2-SAT function is unate
• Asymptotic Enumeration of Partial Orders on a Finite Set
• The number of 2-SAT functions

Cited in

(5)

• An enumerative algorithm for \#2SAT
• Almost every 2-SAT function is unate
• The number of k‐SAT functions
• The number of 2-SAT functions
• The number of 3-SAT functions

This page was built for publication: On the number of 2-SAT functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3552502)