Search

Funder: Alfréd Rényi Institute of Mathematics, We prove that every countably infinite group with Kazhdan’s property (T) has cost 1, answering a well-known question of Gaboriau. It remains open if they have fixed price 1.

Hermon and Hutchcroft have recently proved the long-standing conjecture that in Bernoulli(p) bond percolation on any nonamenable transitive graph G, at any p > p_c(G), the probability that the cluster of the origin is finite but has a large volume n decays exponentially in n. A corollary is that all infinite clusters have anchored expansion almost surely. They have asked if these results could hold more generally, for any finite energy ergodic invariant percolation. We give a counterexample, an invariant percolation on the 4-regular tree., Comment: 9 pages, 1 figure. Small changes throughout. To appear in Bernoulli

One model of real-life spreading processes is First Passage Percolation (also called SI model) on random graphs. Social interactions often follow bursty patterns, which are usually modelled with i.i.d.~heavy-tailed passage times on edges. On the other hand, random graphs are often locally tree-like, and spreading on trees with leaves might be very slow, because of bottleneck edges with huge passage times. Here we consider the SI model with passage times following a power law distribution $\mathbb{P}(\xi>t)\sim t^{-\alpha}$, with infinite mean. For any finite connected graph $G$ with a root $s$, we find the largest number of vertices $\kappa(G,s)$ that are infected in finite expected time, and prove that for every $k \leq \kappa(G,s)$, the expected time to infect $k$ vertices is at most $O(k^{1/\alpha})$. Then, we show that adding a single edge from $s$ to a random vertex in a random tree $\mathcal{T}$ typically increases $\kappa(\mathcal{T},s)$ from a bounded variable to a fraction of the size of $\mathcal{T}$, thus severely accelerating the process. We examine this acceleration effect on some natural models of random graphs: critical Galton-Watson trees conditioned to be large, uniform spanning trees of the complete graph, and on the largest cluster of near-critical Erd\H{o}s-R\'enyi graphs. In particular, at the upper end of the critical window, the process is already much faster than exactly at criticality., Comment: 35 pages, 4 figures

This work is the first in a series of papers devoted to the construction and study of scaling limits of dynamical and near-critical planar percolation and related objects like invasion percolation and the Minimal Spanning Tree. We show here that the counting measure on the set of pivotal points of critical site percolation on the triangular grid, normalized appropriately, has a scaling limit, which is a function of the scaling limit of the percolation configuration. We also show that this limit measure is conformally covariant, with exponent 3/4. Similar results hold for the counting measure on macroscopic open clusters (the area measure), and for the counting measure on interfaces (length measure). Since the aforementioned processes are very much governed by pivotal sites, the construction and properties of the "local time"-like pivotal measure are key results in this project. Another application is that the existence of the limit length measure on the interface is a key step towards constructing the so-called natural time-parametrization of the SLE(6) curve. The proofs make extensive use of coupling arguments, based on the separation of interfaces phenomenon. This is a very useful tool in planar statistical physics, on which we included a self-contained Appendix. Simple corollaries of our methods include ratio limit theorems for arm probabilities and the rotational invariance of the two-point function., Comment: 99 pages, 18 figures. Minor changes, very close to published version

We investigate generalisations of the classical percolation critical probabilities $p_c$, $p_T$ and the critical probability $\tilde{p_c}$ defined by Duminil-Copin and Tassion (2015) to bounded degree unimodular random graphs. We further examine Schramm's conjecture in the case of unimodular random graphs: does $p_c(G_n)$ converge to $p_c(G)$ if $G_n\to G$ in the local weak sense? Among our results are the following: 1. $p_c=\tilde{p_c}$ holds for bounded degree unimodular graphs. However, there are unimodular graphs with sub-exponential volume growth and $p_T < p_c$; i.e., the classical sharpness of phase transition does not hold. 2. We give conditions which imply $\lim p_c(G_n) = p_c(\lim G_n)$. 3. There are sequences of unimodular graphs such that $G_n\to G$ but $p_c(G)>\lim p_c(G_n)$ or $p_c(G), Comment: 28 pages, 1 figure. The paper is reorganized, the theorem numbering is completely changed

We prove that if \({U\subset \mathbb {R}^n}\) is an open domain whose closure \({\overline U}\) is compact in the path metric, and F is a Lipschitz function on ∂U, then for each \({\beta \in \mathbb {R}}\) there exists a unique viscosity solution to the β-biased infinity Laplacian equation $$\beta |\nabla u| + \Delta_\infty u=0$$ on U that extends F, where \({\Delta_\infty u= |\nabla u|^{-2} \sum_{i,j} u_{x_i}u_{x_ix_j} u_{x_j}}\). In the proof, we extend the tug-of-war ideas of Peres, Schramm, Sheffield and Wilson, and define the β-biased \({\epsilon}\)-game as follows. The starting position is \({x_0 \in U}\). At the kth step the two players toss a suitably biased coin (in our key example, player I wins with odds of \({\exp(\beta\epsilon)}\) to 1), and the winner chooses xk with \({d(x_k,x_{k-1}) < \epsilon}\). The game ends when \({x_k \in \partial U}\), and player II pays the amount F(xk) to player I. We prove that the value \({u^{\epsilon}(x_0)}\) of this game exists, and that \({\|u^\epsilon - u\|_\infty \to 0}\) as \({\epsilon \to 0}\), where u is the unique extension of F to \({\overline{U}}\) that satisfies comparison with β-exponential cones. Comparison with exponential cones is a notion that we introduce here, and generalizing a theorem of Crandall, Evans and Gariepy regarding comparison with linear cones, we show that a continuous function satisfies comparison with β-exponential cones if and only if it is a viscosity solution to the β-biased infinity Laplacian equation.

We construct an aggregation process of chordal SLE(\kappa) excursions in the unit disk, starting from the boundary, growing towards all inner points simultaneously, invariant under all conformal self-maps of the disk. We prove that this conformal growth process of excursions, abbreviated as CGE(\kappa), exists iff \kappa\in [0,4), and that it does not create additional fractalness: the Hausdorff dimension of the closure of all the SLE(\kappa) arcs attached is 1+\kappa/8 almost surely. We determine the dimension of points that are approached by CGE(\kappa) at an atypical rate, and construct conformally invariant random fields on the disk based on CGE(\kappa)., Comment: 27 pages, 5 figure files

The Schinzel hypothesis claims (but it seems hopeless to prove) that any irreducible Q[x] polynomial without a constant factor assumes infinitely many prime values at integer places. On the other hand, it is easy to see that a reducible Q[x] polynomial can have only finitely many such places. In this paper we prove that a reducible Z[x] polynomial of degree n (where n is not 4 or 5) can have at most n+2 such places, and there exist examples with n+1 places. If the Schinzel hypothesis and the k-prime-tuple conjecture are true, then there are also polynomials with n+2 such places. (For n=4 or 5 the maximum possible value is 8.) If a Z[x] polynomial is the product of two non-constant integer-valued Q[x] polynomials, then there are at most 1.87234...n+o(n) such places. Even in this case, the number of integer places with positive prime values is at most n. More generally, if f=gh \in R[x] is a product of two non-constant real polynomials, then the number of real places x such that |g(x)|=1 or |h(x)=1|, while f(x)>1, is at most n. For a natural complex version of this last statement we give a counterexample. Furthermore, we briefly consider the generalized problem of assuming values in a fixed finite set of integers., 12 pages

Consider a monotone Boolean function $f:\{0,1\}^n\to\{0,1\}$ and the canonical monotone coupling $\{\eta_p:p\in[0,1]\}$ of an element in $\{0,1\}^n$ chosen according to product measure with intensity $p\in[0,1]$. The random point $p\in[0,1]$ where $f(\eta_p)$ flips from $0$ to $1$ is often concentrated near a particular point, thus exhibiting a threshold phenomenon. For a sequence of such Boolean functions, we peer closely into this threshold window and consider, for large $n$, the limiting distribution (properly normalized to be nondegenerate) of this random point where the Boolean function switches from being 0 to 1. We determine this distribution for a number of the Boolean functions which are typically studied and pay particular attention to the functions corresponding to iterated majority and percolation crossings. It turns out that these limiting distributions have quite varying behavior. In fact, we show that any nondegenerate probability measure on $\mathbb{R}$ arises in this way for some sequence of Boolean functions., Comment: 33 pages, 3 figure. A paper by Daniel Ahlberg and Jeffery E. Steif, with an appendix by G\'abor Pete. Added to the second version is the appendix (earlier published as arXiv:1507.05522) and a significant strengthening of Theorem 3, obtained jointly with Anders Martinsson. The third version updates the conjecture of the appendix

We study the near-critical FK-Ising model. First, a determination of the correlation length defined via crossing probabilities is provided. Second, a phenomenon about the near-critical behavior of FK-Ising is highlighted, which is completely missing from the case of standard percolation: in any monotone coupling of FK configurations $\omega_p$ (e.g., in the one introduced in [Gri95]), as one raises $p$ near $p_c$, the new edges arrive in a self-organized way, so that the correlation length is not governed anymore by the number of pivotal edges at criticality., Comment: 34 pages, 8 figures. This is a streamlined version; the previous one contains more explanations and additional material on exceptional times in FK models with general $q$. Furthermore, the statement and proof of Theorem 1.2 have slightly changed

We prove that the Minimal Spanning Tree and the Invasion Percolation Tree on a version of the triangular lattice in the complex plane have unique scaling limits, which are invariant under rotations, scalings, and, in the case of the MST, also under translations. However, they are not expected to be conformally invariant. We also prove some geometric properties of the limiting MST. The topology of convergence is the space of spanning trees introduced by Aizenman, Burchard, Newman & Wilson (1999), and the proof relies on the existence and conformal covariance of the scaling limit of the near-critical percolation ensemble, established in our earlier works., 56 pages, 21 figures. A thoroughly revised version

In dynamical critical site percolation on the triangular lattice or bond percolation on \Z^2, we define and study a local time measure on the exceptional times at which the origin is in an infinite cluster. We show that at a typical time with respect to this measure, the percolation configuration has the law of Kesten's Incipient Infinite Cluster. In the most technical result of this paper, we show that, on the other hand, at the first exceptional time, the law of the configuration is different. We also study the collapse of the infinite cluster near typical exceptional times, and establish a relation between static and dynamic exponents, analogous to Kesten's near-critical relation., 56 pages, 7 figures. In this version, we prove convergence only for one of our local time constructions. Consequently, some arguments are slightly changed in Sections 2 and 3

Motivated by the renormalization method in statistical physics, Itai Benjamini defined a finitely generated infinite group G to be scale-invariant if there is a nested sequence of finite index subgroups G_n that are all isomorphic to G and whose intersection is a finite group. He conjectured that every scale-invariant group has polynomial growth, hence is virtually nilpotent. We disprove his conjecture by showing that the following groups (mostly finite-state self-similar groups) are scale-invariant: the lamplighter groups F\wr\Z, where F is any finite Abelian group; the solvable Baumslag-Solitar groups BS(1,m); the affine groups A\ltimes\Z^d, for any A\leq GL(\Z,d). However, the conjecture remains open with some natural stronger notions of scale-invariance for groups and transitive graphs. We construct scale-invariant tilings of certain Cayley graphs of the discrete Heisenberg group, whose existence is not immediate just from the scale-invariance of the group. We also note that torsion-free non-elementary hyperbolic groups are not scale-invariant., Comment: 25 pages. The paper is reorganized, with more details in several arguments. To appear in Groups, Geometry and Dynamics

We consider a four-vertex model introduced by B\'{a}lint T\'{o}th: a dependent bond percolation model on $\mathbb{Z}^2$ in which every edge is present with probability 1/2 and each vertex has exactly two incident edges, perpendicular to each other. We prove that all components are finite cycles almost surely, but the expected diameter of the cycle containing the origin is infinite. Moreover, we derive the following critical exponents: the tail probability $\mathbb{P}$(diameter of the cycle of the origin $>$$n$) $\approx$ $n^{-\gamma}$ and the expectation $\mathbb{E}$(length of a typical cycle with diameter $n)\approx n^{\delta}$, with $\gamma=(5-\sqrt{17})/4=0.219...$ and $\delta=(\sqrt{17}+1)/4=1.28....$ The value of $\delta$ comes from a singular sixth order ODE, while the relation $\gamma+\delta=3/2$ corresponds to the fact that the scaling limit of the natural height function in the model is the additive Brownian motion, whose level sets have Hausdorff dimension 3/2. We also include many open problems, for example, on the conformal invariance of certain linear entropy models.

We show that the entropy of the sum of independent random variables can greatly differ from the entropy of their difference. The gap between the two entropies can be arbitrarily large. This holds for regular entropies as well as differential entropies. Our results rely heavily on a result of Ruzsa, who studied sums and differences of finite sets.

Consider the indicator function $f$ of a two-dimensional percolation crossing event. In this paper, the Fourier transform of $f$ is studied and sharp bounds are obtained for its lower tail in several situations. Various applications of these bounds are derived. In particular, we show that the set of exceptional times of dynamical critical site percolation on the triangular grid in which the origin percolates has dimension 31/36 a.s., and the corresponding dimension in the half-plane is 5/9. It is also proved that critical bond percolation on the square grid has exceptional times a.s. Also, the asymptotics of the number of sites that need to be resampled in order to significantly perturb the global percolation configuration in a large square is determined., Comment: 99 pages. In Section 4.4 of the published version, MathSciNet reviewer Antal J\'arai discovered some mistakes, which are corrected in this version

We show that for all p>p_c(\Z^d) percolation parameters, the probability that the cluster of the origin is finite but has at least t vertices at distance one from the infinite cluster is exponentially small in t. We use this to give a short proof of the strongest version of the important fact that the isoperimetric profile of the infinite cluster basically coincides with the profile of the original lattice. This implies, e.g., that simple random walk on the largest cluster of a finite box [-n,n]^d with high probability has L^\infty-mixing time \Theta(n^2), and that the heat kernel (return probability) on the infinite cluster a.s. decays like p_n(o,o)=O(n^{-d/2}). Versions of these results have been proven by Benjamini and Mossel (2003), Mathieu and Remy (2004), Barlow (2004) and Rau (2006). For general infinite graphs, we prove that anchored isoperimetric properties survive supercritical percolation, provided that the probability of the cluster of the origin being finite with large boundary decays rapidly; this is the case for a large class of graphs when $p$ is close to 1. As an application (with the help of some entropy inequalities), we give a short conceptual proof of a theorem of Angel, Benjamini, Berger and Peres (2006): the infinite percolation cluster of a wedge in \Z^3 is a.s. transient whenever the wedge itself is transient., Comment: 15 pages, 2 figures. A small mistake in the proof of Theorem 1.2, pointed out by Yuval Peres and Perla Sousi, is corrected

Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability p, independently of each other, and a deterministic spreading rule with a fixed parameter k: if a vacant site has at least k occupied neighbors at a certain time step, then it becomes occupied in the next step. This process is well-studied on Z^d; here we investigate it on regular and general infinite trees and on non-amenable Cayley graphs. The critical probability is the infimum of those values of p for which the process achieves complete occupation with positive probability. On general trees, we find the following discontinuity: if the branching number of a tree is strictly smaller than k, then the critical probability is 1, while it is 1-1/k on the k-ary tree. A related result is that in any rooted tree T, there is a way of erasing k children of the root, together with all their descendants, and repeating this for all remaining children, and so on, such that the remaining tree T' has branching number \br(T') \leq \max (\br(T)-k, 0). We also prove that on any 2k-regular non-amenable graph, the critical probability for the k-rule is strictly positive., Comment: 17 pages, 2 figures. This is the final version, for the journal Combinatorics, Probability and Computing. Proposition 1.5 is new, proving the "intuitively clear statement" left open in the previous versions