-
The scaling limit of the Minimal Spanning Tree - a preliminary report. [arXiv:0909.3138 math.PR] With Christophe Garban and Oded Schramm. Preprint, 6 pages.
This is a short (and somewhat informal) contribution to the proceedings of the XVIth International Congress on Mathematical Physics, Prague, 2009, written up by me. I describe how the recent proof of the existence and conformal covariance of the scaling limits of dynamical and near-critical planar percolation implies the existence and several topological properties of the scaling limit of the Minimal Spanning Tree, and that it is invariant under scalings, rotations and translations. However, we do not expect conformal invariance: I explain why not and what is missing for a proof. Of course, there will later be a proper paper on this subject, after we have finished the papers on the scaling limits of dynamical and near-critical percolation.
-
Scale-invariant groups. [arXiv:0811.0220v4 math.GR] With Volodymyr
Nekrashevych. Preprint, 25 pages. Groups, Geometry and Dynamics, to appear.
For statistical mechanics on the Z^d lattice, it is very useful that the lattice can
be tiled by large boxes, because: 1. each box looks locally like the infinite lattice; 2. the tiling graph on the boxes is again the
same lattice. On what other groups are there such scale-invariant tilings? A natural guess is that it should have polynomial
volume growth. This remains open, but we disprove a group-theoretical version of this conjecture, made by Itai Benjamini: we show that there are "scale-invariant groups" of exponential growth (and even non-amenable), e.g, the lamplighter group Z_2 wr Z, and the affine group over Z^d. We use the self-similar actions of these groups to prove this. We also construct scale-invariant tilings in the discrete Heisenberg group, using some particularly nice self-similar actions of the group. On the other hand, we show that torsion-free hyperbolic groups are not scale-invariant.
-
Biased tug-of-war, the biased infinity Laplacian, and comparison with exponential cones.
[arXiv:0811.0208v3 math.AP]
With Yuval Peres and Stephanie Somersille. Preprint, 27 pages. Calculus of Variations and Partial Differential Equations, to appear.
Generalizing recent work of Peres, Schramm, Sheffield and Wilson, we apply the game random tug-of-war, played with a little bit biased coin, to prove existence and uniqueness results for the biased Infinity Laplacian PDE. The main tool to connect the game with the viscosity solutions of this degenerate PDE is comparison with exponential cones. The main difficulty compared to the unbiased case in PSSW comes from the fact that the connection to Absolutely Minimizing Lipschitz Extensions is lost.
-
The Fourier
spectrum of critical percolation. [arXiv:0803.3750v3 math.PR] With
Christophe Garban and Oded Schramm. Preprint, 98 pages. Acta Mathematica, to appear.
Crossing events in critical planar percolation are extremely sensitive to noise. This lets some very exceptional events occur in dynamical percolation. In this paper, we understand the Fourier-Walsh expansion of the characteristic functions of monotone crossing events quite precisely, and, using this, give exact quantitive descriptions of the noise- and dynamical sensitivity of the model. E.g., the set of exceptional times of dynamical critical site percolation on the triangular grid in which the origin percolates has Hausdorff dimension 31/36 a.s.
Probably these are the most complex Boolean functions whose Fourier spectrum have been understood this well.
-
A note on percolation
on Z^d: isoperimetric profile via exponential cluster repulsion. [arXiv:math.PR/0702474v4]
Elect. Comm. Probab. 13 (2008), 377-392.
Paper
in the journal.
Large-scale geometric and random walk properties of the infinite supercritical percolation cluster on Z^d, for any p>p_c(Z^d), are basically the same as on the original lattice itself. Here I give a very simple proof of this important fact, which had been established in different forms in a series of papers by several authors during the past two decades. The main tool is a new large deviation result for supercritical percolation; I was quite surprised that one can still prove new results in such a classical field.
I also prove the survival of anchored isoperimetry in percolation on general graphs: for finitely presented groups with p close enough to 1, and for transient wedges in Z^3. In the latter, the main point is that the transience criterion of Terry Lyons turns out to imply Thomassen's criterion; this proof uses some simple entropy inequalities, similarly to how the Loomis-Whitney isoperimetric inequality can be proved using Shearer's inequality.
-
Corner percolation on
Z^2 and the square root of 17. [arXiv:math.PR/0507457v4].
Annals of Probability 36 (2008), No. 5, 1711-1747.
Paper in the journal.
This is a dependent bond percolation model on Z^2, introduced by Bálint Tóth.
At first sight, the model looks intractable, but I realized that it can be viewed as the set of level lines of a height function, which is just the sum of two independent random walks, hence has the Additive Brownian Motion as a scaling limit. The contour cycles are some strange products of simple random walk excursions. This made it possible to understand the model thoroughly, and find some surprising irrational critical exponents.
Here is a .pdf picture of a cycle of length
17996. It is worth zooming in. The "dimension" of this curve is
(\sqrt{17}+1)/4=1.28..., a value coming from the solution of a singular sixth order ODE.
Corner percolation has inspired the definition of several other dependent percolation models with linear entropy: Itai Benjamini's trixor, Omer Angel's odd-trixor, my quaxor. According to computer simulations, odd-trixor and quaxor have the same scaling limit as independent percolation, hence are conformally invariant!
Here are some colourful slides, summarizing the many exciting open problems:
Corner, trixor, odd-trixor, quaxor: Linear
entropy planar percolation models without and with (conjectured) conformal
invariance. This is a large pdf file (6 MB).
-
Critical percolation
on certain non-unimodular graphs. [arXiv:math.PR/0501532v3] With
Yuval Peres and Ariel Scolnicov.
New York Journal of Mathematics 12 (2006), 1-18.
Paper in the journal.
An important conjecture in percolation theory is that almost surely no
infinite cluster exists in critical percolation on any transitive graph
for which the critical probability is less than 1. Earlier work has
established this for the amenable cases Z^2 and Z^d for large d, as well
as for all non-amenable graphs with unimodular automorphism groups. We
show that the conjecture holds for the basic classes of non-amenable
graphs with non-unimodular automorphism groups: for decorated trees and
the non-unimodular Diestel-Leader graphs. We also show that the connection
probability between two vertices decays exponentially in their distance.
Finally, we prove that critical percolation on the positive part of the
lamplighter group has no infinite clusters.
-
Bootstrap percolation
on infinite trees and non-amenable groups. [arXiv:math.PR/0311125v3] With
József Balogh and Yuval Peres. Combinatorics, Probability
and Computing, 15 (2006), no. 5, 715-730. Paper
in the journal
Bootstrap percolation on an arbitrary graph G has a random Bernoulli(p)
initial configuration of occupied sites 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. The critical probability p(G,k) is the infimum of those values of p for which the
process achieves complete occupation with positive probability. This process is well-studied on Z^d; here we investigate it on
infinite trees and non-amenable Cayley graphs.
On general trees we describe the basic behaviour of the process in terms of the branching number of the tree, and find e.g. a surprising discontinuity: if k>br(T), then the critical probability is 1, while it is 1-1/k on the k-ary tree. On a d-regular tree, the critical probability is approximately k/d. We also prove that on any 2k-regular non-amenable
graph, the critical probability for the k-rule is strictly positive.
An open question: is a group amenable if and only if for every Cayley graph G and spreading rule k, we have that p(G,k) is either 0 or 1? Known for Z^d on one hand, and for non-amenable groups with a free subgroup on two generators on the other.
-
Anchored expansion,
percolation and speed. [arXiv:math.PR/0303321] Main text by Dayue
Chen and Yuval Peres, appendix by myself. Annals of Probability, 32
(2004) no. 4, 2978-2995. Paper
in the journal.
Benjamini, Lyons and Schramm (1999) considered properties of an infinite
graph G, and the simple random walk on it, that are preserved by random
perturbations. In this paper we solve several problems raised by those
authors. The anchored expansion constant is a variant of the Cheeger
constant; its positivity implies positive lower speed for the simple
random walk, as shown by Virág (2000). We prove that if G has a
positive anchored expansion constant then so does every infinite cluster
of independent percolation with parameter p sufficiently close to 1; a
better estimate for the parameters p where this holds is in the appendix.
We also show that positivity of the anchored expansion constant is
preserved under a random stretch if, and only if, the stretching law has
an exponential tail. We then study simple random walk in the infinite
percolation cluster in Cayley graphs of certain amenable groups known as
``lamplighter groups''. We prove that zero speed for random walk on a lamplighter
group implies zero speed for random walk on an infinite cluster, for any
supercritical percolation parameter p. For p large enough, we also
establish the converse.
Variations of the method of the Appendix are very useful in studying
isoperimetric inequalities and random walks on percolation clusters of
general graphs, including the classical case of Z^d. See my paper above on exponential cluster repulsion and
the isoperimetric profile of percolation clusters of Z^d.
- Prime values of
reducible polynomials, II. [arXiv:math.NT/0510357]
With Y-G. Chen, Gábor Kun, Imre Z. Ruzsa and Ádám
Timár. Acta Arithmetica, 104 (2002), no. 2, 117--127.
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 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 statement we give a
counterexample.
-
Random disease on
the square grid. With József Balogh. Random
Structures and Algorithms 13 (1998), 409-422. Also in .pdf.
Occupy each square of an n-by-n board independently with probability p(n),
then take a deterministic spreading rule, the most interesting case being
the following: if a square has at least two occupied neighbors at some time
step, then it becomes occupied in the next step. How big does p(n) have to
be to occupy the whole board with high probability? The main result of the
paper is the almost exact determination of this threshold function.
Further investigations are included about the general random and
deterministic cases.
This model turned out to be already known as bootstrap percolation, and
our main result was already proven by Aizenman and Lebowitz in 1988. Thus,
I recommend looking at the expanded version (my undergrad thesis for the
Bolyai Institute) below.
