• ### On an epidemic model on finite graphs(1610.04301)

May 21, 2019 math.PR
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$.
• ### Rapid social connectivity(1608.07621)

March 10, 2019 math.PR
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.
• ### Point-to-point distance in first passage percolation on (tree) x Z(1310.4018)

June 19, 2018 math.PR, math.MG
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.
• ### Self avoiding walk on the seven regular triangulation(1612.04169)

April 27, 2018 math.PR, math.MG
It is shown that self avoiding walk on the seven regular infinite planar triangulation has linear expected displacement.
• ### Two comments on balls in vertex transitive graphs(1803.03805)

March 13, 2018 math.CO, math.GR
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.
• ### On the structure of random graphs that are locally indistinguishable from a lattice(1802.02002)

Feb. 14, 2018 math.CO, math.PR, math.GR
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.
• ### Recurrence of Markov chain traces(1711.03479)

Jan. 11, 2018 math.PR
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.
• ### $p_c$, $p_u$ and graph limits(1707.08544)

Dec. 26, 2017 math.PR
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.
• ### Internal Diffusion-Limited aggregation with uniform starting points(1707.03241)

July 11, 2017 math.PR
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.
• ### Random Walk in Changing Environment(1504.04870)

July 4, 2017 math.PR
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.
• ### Continuous vs discrete spins in the hyperbolic plane(1609.09040)

June 16, 2017 math.PR
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$.
• ### Upper bounds on the growth rate of Diffusion Limited Aggregation(1705.06095)

May 17, 2017 math-ph, math.MP, math.PR
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} .
• ### A density version for H\"aggstr\"om's theorem(1702.04688)

Feb. 15, 2017 math.PR
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$?
• ### On the structure of graphs which are locally indistinguishable from a lattice(1409.7587)

Dec. 20, 2016 math.CO
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.
• ### First Passage percolation on a hyperbolic graph admits bi-infinite geodesics(1606.02449)

Nov. 17, 2016 math.PR
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.
• ### Where does a random process hit a fractal barrier?(1608.00505)

Aug. 4, 2016 math.PR
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.
• ### The mixing time of the giant component of a random graph(math/0610459)

July 31, 2016 math.CO, math.PR
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.
• ### Minimal growth harmonic functions on lamplighter groups(1607.00753)

July 4, 2016 math.PR, math.GR
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.
• ### An isoperimetric inequality for planar triangulations(1604.05863)

April 20, 2016 math.CO, math.MG
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.
• ### Percolation and coarse conformal uniformization(1510.05196)

Dec. 21, 2015 math.PR
We formulate conjectures regarding percolation on planar triangulations suggested by assuming (quasi) invariance under coarse conformal uniformization.
• ### Disorder, entropy and harmonic functions(1111.4853)

Oct. 28, 2015 math.PR
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.
• ### Site recurrence for coalescing random walk(1510.04721)

Oct. 15, 2015 math.PR
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.
• ### Bi-Lipschitz bijections of $\mathbb{Z}$(1509.07670)

Sept. 25, 2015 math.MG
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.
• ### Juntas in the $\ell^{1}$-grid and Lipschitz maps between discrete tori(1311.6958)

Aug. 17, 2015 math.CO
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.
• ### An Upper bound on the growth of Dirichlet tilings of hyperbolic spaces(1504.05873)

June 2, 2015 math.MG, math.GR
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$?