• 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 d-regular 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 vertex-transitive 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 stretched-exponential, 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 bounded-size 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 Gurel-Gurevich, Lyons and the first named author. We exploit recent results in potential theory of non-reversible Markov chains in order to extend their result to the non-reversible 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 diffusion-limited 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 quasi-isometric 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, non-amenable graphs, super-critical percolation on Z^d, high dimensional pre-Sierpinski 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 self-avoiding 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 two-sided 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 non-elementary Gromov hyperbolic), then almost surely, there exists a bi-infinite 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 Erdos-Renyi 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 Derriennic-Kaimanovich-Vershik theorem.
  • We prove a discrete analogue to a classical isoperimetric theorem of Weil for surfaces with non-positive 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 Galton-Watson trees whose offspring distribution has exponential tail. We prove bounds on the occupation probability of a site, as well as a general 0-1 law. Similar conclusions hold for a coalescing process on trees where particles do not backtrack.
  • It is shown that every bi-Lipschitz 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 group-theoretic properties of the action of bi-Lipschitz 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^{n-1}\epsilon)))$ coordinates, where $\partial A$ denotes the edge-boundary 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), 27-35], or as a characterization of large subsets of the $\ell^1$-grid whose edge-boundary 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 $k-1-\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 $k-1-\epsilon_u$ upperbounds the growth rate for any $k$-regular tiling, when $ d > 2$?