Random $2$-SAT: The set of atoms of the limiting empirical marginal distribution

Abstract

We show that the set of atoms of the limiting empirical marginal distribution in the random $2$-SAT model is $\mathbb{Q}\cap (0,1)$, for all clause-to-variable densities up to the satisfiability threshold. While for densities up to $1/2$, the measure is purely discrete, we additionally establish the existence of a nontrivial continuous part for any density in $(1/2,1)$. Our proof is based on the construction of a random variable with the correct distribution as the the root marginal of a multi-type Galton-Watson tree, along with a subsequent analysis of the resulting almost sure recursion.

13 pages, 1 figure