The number of 2-SAT functions
From MaRDI portal
Publication:1870908
DOI10.1007/BF02773060zbMath1024.68044MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C30: Enumeration in graph theory
05C15: Coloring of graphs and hypergraphs
06E30: Boolean functions
Related Items
The number of k‐SAT functions, Combinatorics. Abstracts from the workshop held January 1--7, 2023, Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022, The number of 3-SAT functions, Almost every 2-SAT function is unate, On the Number of 2-SAT Functions
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