Gábor Pete

I am a postdoc researcher at the Theory Group of Microsoft Research. My main interest is in probability, e.g. geometric properties of random walks and percolation on infinite graphs. I am interested in many things, usually in the interface of discrete and continuous mathematics: geometric group theory, conformal invariance of scaling limits, noise sensitivity, PDE, game theory, combinatorial number theory, quasicrystals, Morse theory.

I am Hungarian, did my undergrad there at the Bolyai Institute, Szeged, also spent a year at the University of Cambridge, England, and got my PhD from the Dept of Statistics at UC Berkeley, under the guidance of Yuval Peres.

I am also a dancer, doing mainly improvisation. Here is (will be) an explanation why I consider mathematics and improvisation to be the most important things to do.

And here you can find some of my photos and drawings.

For my contact info in Seattle, Budapest, Szeged, click here.

With Kati, where the Land ends and the Pacific begins. (Joaquin's photo.)

Mathematical contents: Research papers. Thesis works. Book reviews. Some classwork. Earlier geometry teaching and small papers in Hungarian. Homepages of my co-authors and favourite mathematicians. Some lecture notes I like. SLE seminar (Berkeley 2005/2006). AIM workshop: Percolation on Transitive Graphs (May 5-9, 2008).

 

Research papers

  • The Fourier spectrum of critical percolation. With Christophe Garban and Oded Schramm. Preprint, [arXiv:0803.3750 math.PR].

    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.

  • A note on percolation on Z^d: isoperimetric profile via exponential cluster repulsion. Preprint, [arXiv:math.PR/0702474v3].

    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.

  • Corner percolation on Z^2 and the square root of 17. [arXiv:math.PR/0507457v4]. Annals of Probability, to appear.
    A cycle of length 17996.
    We consider a four-vertex model introduced by Bálint Tóth: a dependent bond percolation model on 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 \Pr(diameter of the cycle of the origin > n) \approx n^{-\gamma}, and the expectation \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 the solution of 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, e.g. on the conformal invariance of certain linear entropy models.

    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...

    Some colourful slides, summarizing the 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/0501532] 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/0311125] 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 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. 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 descendents, 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}. 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.
     
  • 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.
    tuz
    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.

 

Thesis workskor

  • My PhD thesis at UC Berkeley had the not very elegant title Dependent percolation, critical exponents, anchored isoperimetry and random walks. Since it is not very different from my already written (or just being written) papers, I don’t put it here.

My previous degrees (kind of Masters) are from the Bolyai Institute, University of Szeged, Hungary, and from the University of Cambridge, UK (this was the so-called Part III).

  • An improved version of my essay written in Cambridge: Morse theory. (50 pages. Also in .pdf.) The original aim was to understand Edward Witten's supersymmetric approach to Morse theory and Killing vector fields. Then it grew into a somewhat heroic attempt to give a detailed introduction to modern geometry from the point of view of this beautiful and deep theory. From Gauss-Bonnet through Hodge decomposition to supersymmetry and Yang-Mills.

  • My thesis for diploma at the Bolyai Institute, József Attila University, Szeged: Disease processes and bootstrap percolation, Contents, Introduction, References,  Deterministic disease on the k-dimensional board,  Random disease and bootstrap percolation,  Addenda and errata. (30 pages. Also in .pdf: intro, determ, random, added.) This is based on my papers in Polygon (Szeged), 1997, see below, and in Random Structures and Algorithms, 1998, with József Balogh, see above. For the latest news and nice pictures about bootstrap percolation on Z^2, go to Ander Holroyd's webpage.

 

Book reviews for Acta Math. Sci. (Szeged)

H. Bass - A. Lubotzky: Tree lattices. B. Bollobás: Random graphs, 2nd edition. G. Davidoff - P. Sarnak - A. Valette: Elementary number theory, group theory, and Ramanujan graphs. G. Grimmett: Percolation, 2nd edition. E.Kleinert: Units in skew fields. W. Woess: Random walks on infinite graphs and groups

 

Some classwork 

 

In Hungarian

From courses I taught:

  • Chapters from algebraic geometry. Course notes and problems.

    Fejezetek az algebrai geometriából - bõséges osszefoglaló és feladatsor.
     
  • Problems in geometry. First set: Geometry of lattices and the discrete Fourier transform. Second set: Fundamental group, covering spaces, geometric group theory. Third set: Konvex polyhedrons, by János Kincses.

    Geometria feladatmegoldó szeminárium - az I. feladatsor (Rácsgeometria és diszkrét Fourier-transzformált); a  II. feladatsor (Fundamentális csoport, fedõfelületek, geometriai csoportelmélet); a III. feladatsor (Konvex poliéderek, Kincses Jánostól).
     
  • Picard's small and big theorems, via covering surfaces. Picard-tételek.

Small papers I wrote:

  • Hogyan gyepesitsunk kockat? Polygon (Szeged)
  • A haromszogek Euler-egyeneserol, Dotsch Andrassal. Polygon (Szeged)
  • Szita-formula, Balogh Jozseffel. Polygon (Szeged)

 

Homepages of my co-authors and favourite mathematicians

Noga Alon (algebraic and probabilistic combinatorics), Michael Baake (quasicrystals), József Balogh (graph theory and probability), Itai Benjamini (mostly probability) Vitaly Bergelson (ergodic Ramsey theory), György Elekes (combinatorial geometry), Benson Farb (geometric group theory), Christophe Garban (probability), Tim Gowers (combinatorics, number theory, Banach spaces), Péter Hajnal (combinatorics - former advisor in Szeged), Alan Hammond (probability), András Krámli (probability and stat. physics), Russell Lyons (probability), Péter Major (probability and Bolyai kollégium anno), John Milnor (geometry, complex dynamical systems, complexity), Tibor Ódor (geometry), Yuval Peres  (probability theory, Hausdorff dimension - former advisor in Berkeley), Imre Ruzsa (combinatorial number theory), Oded Schramm (probability and conformal invariance),  Nándor Simányi (biliard dynamical systems),  Joel Spencer (probabilistic combinatorics), Terence Tao (harmonic analysis, combinatorics, PDE), Ádám Timár (probability), Bálint Tóth (probability and hydrodynamic limits),  Bálint Virág (probability),  Shmuel Weinberger (geometry, complexity), ...

 

Further links

Some lecture notes I like: