On the number of 2-SAT functions

DOI10.1017/S096354830900995XzbMATH Open1200.68125arXiv1005.2863MaRDI QIDQ3552502FDOQ3552502

Authors: L. Ilinca, J. Kahn 

Publication date: 22 April 2010

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

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.

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

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

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)

Cites Work

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

Cited In (5)

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

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)