The number of 2-SAT functions

DOI10.1007/BF02773060zbMath1024.68044OpenAlexW2072137480MaRDI QIDQ1870908

Imre Leader, Graham R. Brightwell, Béla Bollobás

Publication date: 20 November 2003

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02773060

zbMATH Keywords

2-SAT formulae2-SAT functions

Mathematics Subject Classification ID

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

Related Items

The number of k‐SAT functions, Combinatorics. Abstracts from the workshop held January 1--7, 2023, The number of 3-SAT functions, Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022, On the Number of 2-SAT Functions, Almost every 2-SAT function is unate

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some intersection theorems for ordered sets and graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The average number of linear extensions of a partial order
• The scaling window of the 2-SAT transition
• The maximum number of edges in a minimal graph of diameter 2
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Almost all Berge Graphs are Perfect
• The number of k‐SAT functions
• Projections of Bodies and Hereditary Properties of Hypergraphs