Random $2$-SAT: The set of atoms of the limiting empirical marginal distribution
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914985699966976 |
|---|---|
| author | Müller, Noela Neininger, Ralph Zhu, Haodong |
| author_facet | Müller, Noela Neininger, Ralph Zhu, Haodong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17749 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Random $2$-SAT: The set of atoms of the limiting empirical marginal distribution Müller, Noela Neininger, Ralph Zhu, Haodong Probability Combinatorics 05C80, 60C05, 68Q87 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. |
| title | Random $2$-SAT: The set of atoms of the limiting empirical marginal distribution |
| topic | Probability Combinatorics 05C80, 60C05, 68Q87 |
| url | https://arxiv.org/abs/2410.17749 |