Nearly all $k$-SAT functions are unate

We prove that $1-o(1)$ fraction of all $k$-SAT functions on $n$ Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer $k$ and as $n \to \infty$. This resolves a conjecture by Bollob\'as, Brightwell, and Leader from 2003.

• Publication year

  2022

• Venue

  Unknown venue

• Publication date

  2022-09-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2209.04894
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An efficient container lemma

  2019cited by this paper
• THE METHOD OF HYPERGRAPH CONTAINERS

  2018cited by this paper
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs

  2014influential reference
• Proof of the Satisfiability Conjecture for Large k

  2014cited by this paper
• The typical structure of graphs with no large cliques

  2014influential reference
• The typical structure of sparse $K_{r+1}$-free graphs

  2013cited by this paper
• Independent sets in hypergraphs

  2012influential reference
• Hypergraph containers

  2012cited by this paper
• The number of 3-SAT functions

  2010influential reference
• On the Number of 2-SAT Functions

  2009cited by this paper
• Almost every 2-SAT function is unate

  2007cited by this paper
• Flag algebras

  2007cited by this paper
• On Triple Systems with Independent Neighbourhoods

  2005cited by this paper
• ASYMPTOTIC ENUMERATION OF Kn-FREE GRAPHS

  2004cited by this paper
• The number of k‐SAT functions

  2003cited by this paper
• The number of 2-sat functions

  2003influential reference
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs

  2001cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• The maximum number of edges in a minimal graph of diameter 2

  1992influential reference
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent

  1986cited by this paper
• Some intersection theorems for ordered sets and graphs

  1986influential reference
• Regular Partitions of Graphs

  1975cited by this paper
• On the degrees of the vertices of a directed graph

  1965cited by this paper

• Counting Independent Sets in Percolated Graphs via the Ising Model

  2025cites this paper
• Lower and Upper Bounds for Small Canonical and Ordered Ramsey Numbers

  2025cites this paper
• A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization

  2025cites this paper
• Bridging abstract dialectical argumentation and Boolean gene regulation

  2024cites this paper
• Counting unate and balanced monotone Boolean functions

  2023cites this paper