Inhomogeneous random 2-SAT

Abstract

We introduce an inhomogeneous variant of random 2-SAT. Each variable $v_1,\dots ,v_n$ is assigned a type from a state space $\hat{I}›$, independently at random. Clause inclusion is governed by a symmetric measurable kernel $W$ on $(\hat{I}›\times \{+,-\}{)}^2$, in analogy with the inhomogeneous random graph model of Bollobás, Janson, and Riordan: given literals ${\ell }_i\in \{v_i,\neg v_i\}$ and ${\ell }_j\in \{v_j,\neg v_j\}$, the clause $\{{\ell }_i,{\ell }_j\}$ appears with probability $W(\mathrm{type}({\ell }_i),\mathrm{type}({\ell }_j))/(2n)$. In particular, for a variable $v_i$ of type $x\in \hat{I}›$, the slices $W((+,x),\cdot )$ and $W((-,x),\cdot )$ describe how $v_i$ and $\neg v_i$ interact with other literals. We identify a parameter $\ddot{I}{}^{\ast }(W)$, defined as the spectral radius of an integral operator derived from $W$, and show that $\ddot{I}{}^{\ast }(W)<1$ and $\ddot{I}{}^{\ast }(W)>1$ correspond to asymptotically almost surely satisfiable and unsatisfiable instances, respectively. The satisfiability threshold for homogeneous random 2-SAT is well-established, occurring when the ratio of clauses to variables is $1$. This corresponds to a weight function of $W\equiv 1$ and a clause density of $1/(2n)$. Our result extends this classical result to a broad class of models controlled by types of variables.

42 pages, 3 figures