BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Nicholas Crawford appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Let $G$ be an $n$-vertex graph with the maximum degree $Δ$ and the minimum degree $δ$. We give algorithms with complexity $O(1.3158^{n-0.7~Δ(G)})$ and $O(1.32^{n-0.73~Δ(G)})$ that determines if $G$ is 3-colorable, when $δ(G)\geq 8$ and $δ(G)\geq 7$, respectively.
We present rigorous upper and lower bounds on the emptiness formation probability for the ground state of a spin-$1/2$ Heisenberg XXZ quantum spin system. For a $d$-dimensional system we find a rate of decay of the order $\exp(-c L^{d+1})$ where $L$ is the sidelength of the box in which we ask for the emptiness formation event to occur. In the $d=1$ case this confirms previous predictions made in the integrable systems community, though our bounds do not achieve the precision predicted by Bethe ansatz calculations. On the other hand, our bounds in the case $d \geq 2$ are new. The main tools we use are reflection positivity and a rigorous path integral expansion which is a variation on those previously introduced by Toth, Aizenman-Nachtergaele and Ueltschi.
We consider a lattice of weakly interacting quantum Markov processes. Without interaction, the dynamics at each site is relaxing exponentially to a unique stationary state. With interaction, we show that there remains a unique stationary state in the thermodynamic limit, i.e. absence of phase coexistence, and the relaxation towards it is exponentially fast for local observables. We do not assume that the quantum Markov process is reversible (detailed balance) w.r.t. a local Hamiltonian.
We prove that the linearly edge reinforced random walk (LRRW) on any graph with bounded degrees is recurrent for sufficiently small initial weights. In contrast, we show that for non-amenable graphs the LRRW is transient for sufficiently large initial weights, thereby establishing a phase transition for the LRRW on non-amenable graphs. While we rely on the description of the LRRW as a mixture of Markov chains, the proof does not use the magic formula. We also derive analogous results for the vertex reinforced jump process.
Consider the behavior of a classical O(n) model in a weak random external field acting along some $k$-dimensional subspace in $\R^n$ with $k<n$. We show rigorously that if $k=n-1$, for the model defined on $\Z^d$, $d ={2, 3}$ there is residual magnetic order perpendicular to the subspace which supports the distribution of the random field only. Furthermore, when $k\leq n-1$ and $d\geq 2$ we show in general that the magnitude of spin projections onto this subspace are small.
Consider the classical XY model in a weak random external field pointing along the Y axis with strength $ε$. We prove that the model defined on $\Z^3$ with nearest neighbor coupling exhibits residual magnetic order in the horizontal direction for arbitrarily weak random field strengths and, depending on field strength, sufficiently low temperature.
We consider continuous-spin models on the $d$-dimensional hypercubic lattice with the spins $σ_x$ \emph{a priori} uniformly distributed over the unit sphere in $\R^n$ (with $n\ge2$) and the interaction energy having two parts: a short-range part, represented by a potential $Φ$, and a long-range antiferromagnetic part $λ|x-y|^{-s}σ_x\cdotσ_y$ for some exponent $s>d$ and $λ\ge0$. We assume that $Φ$ is twice continuously differentiable, finite range and invariant under rigid rotations of all spins. For $d\ge1$, $s\in(d,d+2]$ and any $λ>0$, we then show that the expectation of each $σ_x$ vanishes in all translation-invariant Gibbs states. In particular, the spontaneous magnetization is zero and block-spin averages vanish in all (translation invariant or not) Gibbs states. This contrasts the situation of $λ=0$ where the ferromagnetic nearest-neighbor systems in $d\ge3$ exhibit strong magnetic order at sufficiently low temperatures. Our theorem extends an earlier result of A. van Enter ruling out magnetized states with uniformly positive two-point correlation functions.
Consider the classical XY model in a weak random external field pointing along the $Y$ axis with strength $ε$. We study the behavior of this model as the range of the interaction is varied. We prove that in any dimension $d \geq 2$ and for all $ε$ sufficiently small, there is a range $L=L(ε)$ so that whenever the inverse temperature $β$ is larger than some $β(ε)$, there is strong residual ordering along the $X$ direction.
We study limit laws for simple random walks on supercritical long range percolation clusters on $\Z^d, d \geq 1$. For the long range percolation model, the probability that two vertices $x, y$ are connected behaves asymptotically as $\|x-y\|_2^{-s}$. When $s\in(d, d+1)$, we prove that the scaling limit of simple random walk on the infinite component converges to an $α$-stable Lévy process with $α= s-d$ establishing a conjecture of Berger and Biskup. The convergence holds in both the quenched and annealed senses. In the case where $d=1$ and $s>2$ we show that the simple random walk converges to a Brownian motion. The proof combines heat kernel bounds from our companion paper, ergodic theory estimates and an involved coupling constructed through the exploration of a large number of walks on the cluster.