Abstract:
Reconstruction problems have been studied in a number of contexts including biology, information theory and and statistical physics. We consider the reconstruction problem for random $k$-colourings on the $\Delta$-ary tree for large $k$. Bhatnagar et. al. showed non-reconstruction when $\Delta \leq \frac12 k\log k - o(k\log k)$ and reconstruction when $\Delta \geq k\log k + o(k\log k)$. We tighten this result and show non-reconstruction when $\Delta \leq k[\log k + \log \log k + 1 - \ln 2 -o(1)]$ and reconstruction when $\Delta \geq k[\log k + \log \log k + 1+o(1)]$.

Abstract:
The reconstruction problem on the tree has been studied in numerous contexts including statistical physics, information theory and computational biology. However, rigorous reconstruction thresholds have only been established in a small number of models. We prove the first exact reconstruction threshold in a non-binary model establishing the Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree. We further establish that the Kesten-Stigum bound is not tight for the $q$-state Potts model when $q \geq 5$. Moreover, we determine asymptotics for the reconstruction thresholds.

Abstract:
Counter to the general notion that the regular tree is the worst case for decay of correlation between sets and nodes, we produce an example of a multi-spin interacting system which has uniqueness on the $d$-regular tree but does not have uniqueness on some infinite $d$-regular graphs.

Abstract:
The hardcore model is a model of lattice gas systems which has received much attention in statistical physics, probability theory and theoretical computer science. It is the probability distribution over independent sets $I$ of a graph weighted proportionally to $\lambda^{|I|}$ with fugacity parameter $\lambda$. We prove that at the uniqueness threshold of the hardcore model on the $d$-regular tree, approximating the partition function becomes computationally hard on graphs of maximum degree $d$. Specifically, we show that unless NP$=$RP there is no polynomial time approximation scheme for the partition function (the sum of such weighted independent sets) on graphs of maximum degree $d$ for fugacity $\lambda_c(d) < \lambda < \lambda_c(d) + \epsilon(d)$ where $\lambda_c = \frac{(d-1)^{d-1}}{(d-2)^d}$ is the uniqueness threshold on the $d$-regular tree and $\epsilon(d)>0$. Weitz produced an FPTAS for approximating the partition function when $0<\lambda < \lambda_c(d)$ so this result demonstrates that the computational threshold exactly coincides with the statistical physics phase transition thus confirming the main conjecture of [28]. We further analyze the special case of $\lambda=1, d=6$ and show there is no polynomial time algorithm for approximately counting independent sets on graphs of maximum degree $d= 6$ which is optimal. Our proof is based on specially constructed random bi-partite graphs which act as gadgets in a reduction to MAX-CUT. Building on the second moment method analysis of [28] and combined with an analysis of the reconstruction problem on the tree our proof establishes a strong version of 'replica' method heuristics developed by theoretical physicists. The result establishes the first rigorous correspondence between the hardness of approximate counting and sampling with statistical physics phase transitions.

Abstract:
Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd\H{o}s-R\'enyi random graph G(n,d/n). While the average degree in G(n,d/n) is d(1-o(1)), it contains many nodes of degree of order $\log n / \log \log n$. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring or the Ising model, the mixing time of Gibbs sampling is at least $n^{1 + \Omega(1 / \log \log n)}$. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. In this work consider sampling q-colorings and show that for every $d < \infty$ there exists $q(d) < \infty$ such that for all $q \geq q(d)$ the mixing time of Gibbs sampling on G(n,d/n) is polynomial in $n$ with high probability. Our results are the first polynomial time mixing results proven for the coloring model on G(n,d/n) for d > 1 where the number of colors does not depend on n. They extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.

Abstract:
We consider functionals of long-range dependent Gaussian sequences with infinite variance and obtain nonstandard limit theorems. When the long-range dependence is strong enough, the limit is a Hermite process, while for weaker long-range dependence, the limit is $\alpha$-stable L\'{e}vy motion. For the critical value of the long-range dependence parameter, the limit is a sum of a Hermite process and $\alpha$-stable L\'{e}vy motion.

Abstract:
For a bivariate L\'evy process $(\xi_t,\eta_t)_{t\geq 0}$ the generalised Ornstein-Uhlenbeck (GOU) process is defined as V_t:=e^{\xi_t}(z+\int_0^t e^{-\xi_{s-}}d\eta_s), t\ge0, where $z\in\mathbb{R}.$ We define necessary and sufficient conditions under which the infinite horizon ruin probability for the process is zero. These conditions are stated in terms of the canonical characteristics of the L\'evy process and reveal the effect of the dependence relationship between $\xi$ and $\eta.$ We also present technical results which explain the structure of the lower bound of the GOU.

Abstract:
In this paper, we derive upper bounds for the heat kernel of the simple random walk on the infinite cluster of a supercritical long range percolation process. For any $d \geq 1$ and for any exponent $s \in (d, (d+2) \wedge 2d)$ giving the rate of decay of the percolation process, we show that the return probability decays like $t^{-\ffrac{d}{s-d}}$ up to logarithmic corrections, where $t$ denotes the time the walk is run. Moreover, our methods also yield generalized bounds on the spectral gap of the dynamics and on the diameter of the largest component in a box. Besides its intrinsic interest, the main result is needed for a companion paper studying the scaling limit of simple random walk on the infinite cluster.

Abstract:
We establish tight results for rapid mixing of Gibbs samplers for the Ferromagnetic Ising model on general graphs. We show that if \[(d-1)\tanh\beta<1,\] then there exists a constant C such that the discrete time mixing time of Gibbs samplers for the ferromagnetic Ising model on any graph of n vertices and maximal degree d, where all interactions are bounded by $\beta$, and arbitrary external fields are bounded by $Cn\log n$. Moreover, the spectral gap is uniformly bounded away from 0 for all such graphs, as well as for infinite graphs of maximal degree d. We further show that when $d\tanh\beta<1$, with high probability over the Erdos-Renyi random graph $G(n,d/n)$, it holds that the mixing time of Gibbs samplers is \[n^{1+\Theta({1}/{\log\log n})}.\] Both results are tight, as it is known that the mixing time for random regular and Erdos-Renyi random graphs is, with high probability, exponential in n when $(d-1)\tanh\beta>1$, and $d\tanh\beta>1$, respectively. To our knowledge our results give the first tight sufficient conditions for rapid mixing of spin systems on general graphs. Moreover, our results are the first rigorous results establishing exact thresholds for dynamics on random graphs in terms of spatial thresholds on trees.

Abstract:
We study the long range percolation model on $\mathbb{Z}$ where sites $i$ and $j$ are connected with probability $\beta |i-j|^{-s}$. Graph distances are now well understood for all exponents $s$ except in the case $s=2$ where the model exhibits non-trivial self-similar scaling. Establishing a conjecture of Benjamini and Berger \cite{BenBer:01}, we prove that the typical distance from site 0 to $n$ grows as a power law $n^{\theta(\beta)}$ up to a multiplicative constant for some exponent $0<\theta(\beta)<1$ as does the diameter of the graph on a box of length $n$.