Search for: All records

Continuing our earlier work in Nam et al. (One-step replica symmetry breaking of random regular NAE-SAT I,arXiv:2011.14270, 2020), we study the random regulark-nae-satmodel in the condensation regime. In Nam et al. (2020), the (1rsb) properties of the model were established with positive probability. In this paper, we improve the result to probability arbitrarily close to one. To do so, we introduce a new framework which is the synthesis of two approaches: the small subgraph conditioning and a variance decomposition technique using Doob martingales and discrete Fourier analysis. The main challenge is a delicate integration of the two methods to overcome the difficulty arising from applying the moment method to an unbounded state space.

 

Recent progress in the study of the contact process (see Shankar Bhamidi, Danny Nam, Oanh Nguyen, and Allan Sly [Ann. Probab. 49 (2021), pp. 244–286]) has verified that the extinction-survival threshold λ 1 \lambda _1 on a Galton-Watson tree is strictly positive if and only if the offspring distribution ξ \xi has an exponential tail. In this paper, we derive the first-order asymptotics of λ 1 \lambda _1 for the contact process on Galton-Watson trees and its corresponding analog for random graphs. In particular, if ξ \xi is appropriately concentrated around its mean, we demonstrate that λ 1 ( ξ ) ∼ 1 / E ξ \lambda _1(\xi ) \sim 1/\mathbb {E} \xi as E ξ → ∞ \mathbb {E}\xi \rightarrow \infty , which matches with the known asymptotics on d d -regular trees. The same results for the short-long survival threshold on the Erdős-Rényi and other random graphs are shown as well.