We present an all-pairs shortest path algorithm whose running time on a
complete directed graph on $n$ vertices whose edge weights are chosen
independently and uniformly at random from $[0,1]$ is $O(n^2)$, in expectation
and with high probability. This resolves a long standing open problem. The
algorithm is a variant of the dynamic all-pairs shortest paths algorithm of
Demetrescu and Italiano. The analysis relies on a proof that the number of
\emph{locally shortest paths} in such randomly weighted graphs is $O(n^2)$, in
expectation and with high probability.
Let $(\xi(s))_{s\geq 0}$ be a standard Brownian motion in $d\geq 1$
dimensions and let $(D_s)_{s \geq 0}$ be a collection of open sets in $\R^d$.
For each $s$, let $B_s$ be a ball centered at 0 with $\vol(B_s) = \vol(D_s)$.
We show that $\E[\vol(\cup_{s \leq t}(\xi(s) + D_s))] \geq \E[\vol(\cup_{s \leq
t}(\xi(s) + B_s))]$, for all $t$. In particular, this implies that the expected
volume of the Wiener sausage increases when a drift is added to the Brownian
motion.
We consider subsets of the (symbolic) sequence space that are invariant under
the action of the semigroup of multiplicative integers. A representative
example is the collection of all 0-1 sequences $(x_k)$ such that $x_k x_{2k}=0$
for all $k$. We compute the Hausdorff and Minkowski dimensions of these sets
and show that they are typically different. The proof proceeds via a
variational principle for multiplicative subshifts.
We consider the following dynamic Boolean model introduced by van den Berg,
Meester and White (1997). At time 0, let the nodes of the graph be a Poisson
point process in R^d with constant intensity and let each node move
independently according to Brownian motion. At any time t, we put an edge
between every pair of nodes if their distance is at most r.
A recurrent graph $G$ has the infinite collision property if two independent
random walks on $G$, started at the same point, collide infinitely often a.s.
We give a simple criterion in terms of Green functions for a graph to have this
property, and use it to prove that a critical Galton-Watson tree with finite
variance conditioned to survive, the incipient infinite cluster in $\Z^d$ with
$d \ge 19$ and the uniform spanning tree in $\Z^2$ all have the infinite
collision property.
For $d \geq 2$ let $B$ be standard $d$-dimensional Brownian motion. For any
$\alpha < 1/d$ we construct an $\alpha$-H\"{o}lder continuous function $f
\colon [0,1] \to \mathbb{R}^d$ so that the range of $B-f$ covers an open set.
This strengthens a result of Graversen (1982) and answers a question of Le Gall
(1988).
We prove that on any infinite, connected, locally finite, transitive graph G,
the probability of the random walk being within $\eps \sqrt{t}$ of the origin
after t steps is at most $O(\eps)$. A similar statement holds for finite
graphs, up to the relaxation time of the walk. Our approach uses non-constant
equivariant harmonic mappings taking values in a Hilbert space. For the special
case of discrete, amenable groups, we present a more explicit proof of the
Mok-Korevaar-Schoen theorem on existence of such harmonic maps by constructing
them from the heat flow on a Folner set.
Let $U \subseteq \C$ be a bounded domain with smooth boundary and let $F$ be
an instance of the continuum Gaussian free field on $U$ with respect to the
Dirichlet inner product $\int_U \nabla f(x) \cdot \nabla g(x) dx$. The set
$T(a;U)$ of $a$-thick points of $F$ consists of those $z \in U$ such that the
average of $F$ on a disk of radius $r$ centered at $z$ has growth $\sqrt{a/\pi}
\log \tfrac{1}{r}$ as $r \to 0$.
Consider Glauber dynamics for the Ising model on a graph of $n$ vertices.
Hayes and Sinclair showed that the mixing time for this dynamics is at least
$n\log n/f(\Delta)$, where $\Delta$ is the maximum degree and $f(\Delta) =
\Theta(\Delta \log^2 \Delta)$. Their result applies to more general spin
systems, and in that generality, they showed that some dependence on $\Delta$
is necessary. In this paper, we focus on the ferromagnetic Ising model and
prove that the mixing time of Glauber dynamics on any $n$-vertex graph is at
least $(1/4+o(1))n \log n$.
Consider Glauber dynamics for the Ising model on a graph of $n$ vertices.
Hayes and Sinclair showed that the mixing time for this dynamics is at least
$n\log n/f(\Delta)$, where $\Delta$ is the maximum degree and $f(\Delta) =
\Theta(\Delta \log^2 \Delta)$. Their result applies to more general spin
systems, and in that generality, they showed that some dependence on $\Delta$
is necessary. In this paper, we focus on the ferromagnetic Ising model and
prove that the mixing time of Glauber dynamics on any $n$-vertex graph is at
least $(1/4+o(1))n \log n$.
Let $C_1$ be the largest component of the Erd\H{o}s-R\'enyi random graph
$G(n,p)$. The mixing time of random walk on $C_1$ in the strictly supercritical
regime, $p=c/n$ with fixed $c>1$, was shown to have order $\log^2 n$ by
Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In
the critical window, $p=(1+\epsilon)/n$ where $\lambda=\epsilon^3 n$ is
bounded, Nachmias and Peres proved that the mixing time on $C_1$ is of order
$n$.
Let $C_1$ be the largest component of the Erd\H{o}s-R\'enyi random graph
$G(n,p)$. The mixing time of random walk on $C_1$ in the strictly supercritical
regime, $p=c/n$ with fixed $c>1$, was shown to have order $\log^2 n$ by
Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In
the critical window, $p=(1+\epsilon)/n$ where $\lambda=\epsilon^3 n$ is
bounded, Nachmias and Peres proved that the mixing time on $C_1$ is of order
$n$.
Consider a Markov chain $(\xi_v)_{v \in V} \in [k]^V$ on the infinite $b$-ary
tree $T = (V,E)$ with irreducible edge transition matrix $M$, where $b \geq 2$,
$k \geq 2$ and $[k] = \{1,...,k\}$. We denote by $L_n$ the level-$n$ vertices
of $T$. Assume $M$ has a real second-largest (in absolute value) eigenvalue
$\lambda$ with corresponding real eigenvector $\nu \neq 0$.