Random 2-SAT: The set of atoms of the limiting empirical marginal distribution
classification
🧮 math.PR
math.CO
keywords
distributionmarginalrandomatomsdensitiesempiricallimitingadditionally
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.