
We study a system of random walks, known as the frog model, starting from a
profile of independent Poisson($\lambda$) particles per site, with one
additional active particle planted at some vertex $\mathbf{o}$ of a finite
connected simple graph $G=(V,E)$. Initially, only the particles occupying
$\mathbf{o}$ are active. Active particles perform $t \in \mathbb{N} \cup
\{\infty \}$ steps of the walk they picked before vanishing and activate all
inactive particles they hit. This system is often taken as a model for the
spread of an epidemic over a population. Let $\mathcal{R}_t$ be the set of
vertices which are visited by the process, when active particles vanish after
$t$ steps. We study the susceptibility of the process on the underlying graph,
defined as the random quantity $\mathcal{S}(G):=\inf \{t:\mathcal{R}_t=V \}$
(essentially, the shortest particles' lifetime required for the entire
population to get infected). We consider the cases that the underlying graph is
either a regular expander or a $d$dimensional torus of side length $n$ (for
all $d \ge 1$) $\mathbb{T}_d(n)$ and determine the asymptotic behavior of
$\mathcal{S} $ up to a constant factor. In fact, throughout we allow the
particle density $\lambda$ to depend on $n$ and for $d \ge 2$ we determine the
asymptotic behavior of $\mathcal{S}(\mathbb{T}_d(n))$ up to smaller order terms
for a wide range of $\lambda=\lambda_n$.

Given a graph $G=(V,E)$, consider Poisson($ V$) walkers performing
independent lazy simple random walks on $G$ simultaneously, where the initial
position of each walker is chosen independently with probability proportional
to the degrees. When two walkers visit the same vertex at the same time they
are declared to be acquainted. The social connectivity time $\mathrm{SC}(G)$ is
defined as the first time in which there is a path of acquaintances between
every pair of walkers. It is shown that when the average degree of $G$ is $d$,
with high probability \[ c\log V \le \mathrm{SC}(G) \le C d^{1+5 \cdot 1_{G
\text{ is not regular}} } \log^3 V.\] When $G$ is regular the lower bound is
improved to $\mathrm{SC}(G) \ge \log V 6 \log \log V $, with high
probability.
We determine $\mathrm{SC}(G)$ up to a constant factor in the cases that $G$
is an expander and when it is the $n$cycle.

We consider first passage percolation (FPP) on T_d x Z, where T_d is the
dregular tree (d>=3). It is shown that for a fixed vertex v in the tree, the
fluctuation of the distance in the FPP metric between the points (v,0) and
(v,n) is of the order of at most log n. We conjecture that the real
fluctuations are of order 1 and explain why.

It is shown that self avoiding walk on the seven regular infinite planar
triangulation has linear expected displacement.

We observe that a ball of radius $1$ in the grandfather graph can not be
realized as a ball of radius $1$ in a finite vertex transitive graph. We remark
on when a ball in a finite vertex transitive graph appears as a ball in an
infinite vertex transitive graph.

We study the properties of finite graphs in which the ball of radius $r$
around each vertex induces a graph isomorphic to the ball of radius $r$ in some
fixed vertextransitive graph $F$. This is a natural extension of the study of
regular graphs. We focus on the case where $F$ is $\mathbb{L}^d$, the graph of
the $d$dimensional square lattice. In a previous work [I. Benjamini, D. Ellis,
On the structure of graphs which are locally indistinguishable from a lattice,
{\em Forum of Mathematics, Sigma} 4 (2016), e31.], the authors obtained a
characterisation of all the $n$vertex graphs in which the ball of radius $r$
around each vertex is isomorphic to the ball of radius $r$ in $\mathbb{L}^d$,
for each pair of integers $d,r$ such that $d \geq 2$ and $r \geq 3$. These
graphs have a very rigidly proscribed global structure, much more so than that
of $(2d)$regular graphs. In this paper, we estimate the number of unlabelled,
$n$vertex graphs which have the above property (in the case where $r$ is at
least linear in $d$). This number grows like a stretchedexponential, again in
contrast with the situation for regular graphs. We use this estimate to obtain
results on the typical properties of a uniform random such graph. In
particular, we show that with high probability, the largest component of this
random graph has size $O(n^{1\epsilon})$ for some fixed $\epsilon>0$ depending
only upon $d$, but that there are only $o(n)$ vertices in boundedsize
components. Our proofs use a mixture of techniques and results from group
theory, topology, analytic number theory and combinatorics.

It is shown that transient graphs for the simple random walk do not admit a
nearest neighbor transient Markov chain (not necessarily a reversible one),
that crosses all edges with positive probability, while there is such chain for
the square grid $\mathbb{Z}^2$. In particular, the $d$dimensional grid
$\mathbb{Z}^d$ admits such a Markov chain only when $d=2$. For $d=2$ we present
a relevant example due to Gady Kozma, while the general statement for transient
graphs is obtained by proving that for every transient irreducible Markov chain
on a countable state space, its trace is a.s. recurrent for simple random walk.
The case that the Markov chain is reversible is due to GurelGurevich, Lyons
and the first named author. We exploit recent results in potential theory of
nonreversible Markov chains in order to extend their result to the
nonreversible setup.

A question relating the critical probability for percolation, the critical
probability for a unique infinite cluster and graph limits is presented,
together with some partial results.

We study internal diffusionlimited aggregation with random starting points
on Z^d. In this model, each new particle starts from a vertex chosen uniformly
at random on the existing aggregate. We prove that the limiting shape of the
aggregate is a Euclidean ball.

In this paper we introduce the notion of Random Walk in Changing Environment
 a random walk in which each step is performed in a different graph on the
same set of vertices, or more generally, a weighted random walk on the same
vertex and edge sets but with different (possibly 0) weights in each step. This
is a very wide class of RW, which includes some well known types of RW as
special cases (e.g. reinforced RW, true SAW). We define and explore various
possible properties of such walks, and provide criteria for recurrence and
transience when the underlying graph is $\mathbb{N}$ or a tree. We provide an
example of such a process on $\mathbb{Z}^2$ where conductances can only change
from $1$ to $2$ (once for each edge) but nevertheless the walk is transient,
and conjecture that such behaviour cannot happen when the weights are chosen in
advance, that is, do not depend on the location of the RW.

We study the $O(n)$ model on graphs quasiisometric to the hyperbolic plane,
with free boundary conditions. We observe that the pair correlations decay
exponentially with distance, for all temperatures, if and only if $n>1$.

We revisit Kesten's argument for the upper bound on the growth rate of DLA.
We are able to make the argument robust enough so that it applies to many
graphs, where only control of the heat kernel is required. We apply this to
many examples including transitive graphs of polynomial growth, graphs of
exponential growth, nonamenable graphs, supercritical percolation on Z^d,
high dimensional preSierpinski carpets. We also observe that a careful
analysis shows that Kesten's original bound on Z^3 can be improved from t^{2/3}
to (t log t)^{1/2} .

Given invariant percolation on a regular tree, where the probability of an
edge to be open equals $p$, is it always possible to find an infinite
selfavoiding path along which the density of open edges is bigger then $p$?

We study the properties of finite graphs in which the ball of radius $r$
around each vertex induces a graph isomorphic to some fixed graph $F$. This is
a natural extension of the study of regular graphs, and of the study of graphs
of constant link. We focus on the case where $F$ is $\mathbb{L}^d$, the
$d$dimensional square lattice. We obtain a characterisation of all the finite
graphs in which the ball of radius $3$ around each vertex is isomorphic to the
ball of radius $3$ in $\mathbb{L}^d$, for each integer $d \geq 3$. These graphs
have a very rigidly proscribed global structure, much more so than that of
$(2d)$regular graphs. (They may be viewed as quotient lattices of
$\mathbb{L}^d$ in various compact orbifolds.) In the $d=2$ case, our methods
yield new proofs of structure theorems of Thomassen and of M\'arquez, de Mier,
Noy and Revuelta, and also yield short, `algebraic' restatements of these
theorems. Our proofs use a mixture of techniques and results from
combinatorics, algebraic topology and group theory.

Given an infinite connected graph, a way to randomly perturb its metric is to
assign random i.i.d. lengths to the edges. An open question attributed to
Furstenberg is whether there exists a twosided infinite geodesic in first
passage percolation on Z^2, and more generally on Z^n for n>1. Although the
answer is generally conjectured to be negative, we give a positive answer for
graphs satisfying some negative curvature assumption. Assuming only strict
positivity and finite expectation of the random lengths, we prove that if a
graph X has bounded degree and contains a Morse geodesic (e.g. is
nonelementary Gromov hyperbolic), then almost surely, there exists a
biinfinite geodesic in first passage percolation on X.

Given a Brownian path $\beta(t)$ on $\mathbb{R}$, starting at $1$, a.s. there
is a singular time set $T_{\beta}$, such that the first hitting time of $\beta$
by an independent Brownian motion, starting at $0$, is in $T_{\beta}$ with
probability one. A couple of problems regarding hitting measure for random
processes are presented.

We show that the total variation mixing time of the simple random walk on the
giant component of supercritical ErdosRenyi graphs is log^2 n. This statement
was only recently proved, independently, by Fountoulakis and Reed. Our proof
follows from a structure result for these graphs which is interesting in its
own right. We show that these graphs are "decorated expanders"  an expander
glued to graphs whose size has constant expectation and exponential tail, and
such that each vertex in the expander is glued to no more than a constant
number of decorations.

We study the minimal possible growth of harmonic functions on lamplighters.
We find that $(\mathbb{Z}/2)\wr \mathbb{Z}$ has no sublinear harmonic
functions, $(\mathbb{Z}/2)\wr \mathbb{Z}^2$ has no sublogarithmic harmonic
functions, and neither has the repeated wreath product
$(\dotsb(\mathbb{Z}/2\wr\mathbb{Z}^2)\wr\mathbb{Z}^2)\wr\dotsb\wr\mathbb{Z}^2$.
These results have implications on attempts to quantify the
DerriennicKaimanovichVershik theorem.

We prove a discrete analogue to a classical isoperimetric theorem of Weil for
surfaces with nonpositive curvature. It is shown that hexagons in the
triangular lattice have maximal volume among all sets of a given boundary in
any triangulation with minimal degree 6.

We formulate conjectures regarding percolation on planar triangulations
suggested by assuming (quasi) invariance under coarse conformal uniformization.

We study harmonic functions on random environments with particular emphasis
on the case of the infinite cluster of supercritical percolation on
$\mathbb{Z}^d$. We prove that the vector space of harmonic functions growing at
most linearly is $(d+1)$dimensional almost surely. Further, there are no
nonconstant sublinear harmonic functions (thus implying the uniqueness of the
corrector). A main ingredient of the proof is a quantitative, annealed version
of the Avez entropy argument. This also provides bounds on the derivative of
the heat kernel, simplifying and generalizing existing results. The argument
applies to many different environments; even reversibility is not necessary.

Begin continuous time random walks from every vertex of a graph and have
particles coalesce when they collide. We use a duality relation with the voter
model to prove the process is site recurrent on bounded degree graphs, and for
GaltonWatson trees whose offspring distribution has exponential tail. We prove
bounds on the occupation probability of a site, as well as a general 01 law.
Similar conclusions hold for a coalescing process on trees where particles do
not backtrack.

It is shown that every biLipschitz bijection from $\mathbb{Z}$ to itself is
at a bounded $L_{\infty}$ distance from either the identity or the reflection.
We then comment on the grouptheoretic properties of the action of biLipschitz
bijections.

We show that if $A \subset [k]^n$, then $A$ is $\epsilon$close to a junta
depending upon at most $\exp(O(\partial A/(k^{n1}\epsilon)))$ coordinates,
where $\partial A$ denotes the edgeboundary of $A$ in the $\ell^1$grid. This
is sharp up to the value of the absolute constant in the exponent. This result
can be seen as a generalisation of the Junta theorem for the discrete cube,
from [E. Friedgut, Boolean functions with low average sensitivity depend on few
coordinates, Combinatorica 18 (1998), 2735], or as a characterization of large
subsets of the $\ell^1$grid whose edgeboundary is small. We use it to prove a
result on the structure of Lipschitz functions between two discrete tori; this
can be seen as a discrete, quantitative analogue of a recent result of Austin
[T. Austin, On the failure of concentration for the $\ell^{\infty}$ball,
preprint]. We also prove a refined version of our junta theorem, which is sharp
in a wider range of cases.

It is shown that the growth rate $(\lim_r B(r)^{1/r})$ of any $k$ faces
Dirichlet tiling of the real hyperbolic space $\mathbb{H}^d, d>2,$ is at most
$k1\epsilon$, for an $\epsilon > 0$, depending only on $k$ and $d$. We don't
know if there is a universal $\epsilon_u > 0$, such that $k1\epsilon_u$
upperbounds the growth rate for any $k$regular tiling, when $ d > 2$?