The unreasonable effectiveness of martingales

ABSTRACT

1 Three questions.

• Let G be a d-regular graph on n vertices where 3 ≤ d < n. Perform bond percolation with p = 1/d-1 and let C₁ be the largest open cluster. Is E|C₁| = O(n^2/3)? (This is well known, and sharp, for d = n - 1, the Erdös-Renyi random graph.)

• Let G be an infinite connected graph with maximal degree d. Does simple RW on G always satisfy p^t(x, y) ≤ C(d)/√ t?

• Simple RW on {0, 1}^k, started uniformly, is a stationary, reversible Markov chain that for t < k/4, escapes at a positive speed (in the l¹ metric) from its starting point.

Is there a chain with these properties in the l² metric? And on a tree?

REFERENCES

• 1: Nachmias A. and Peres Y. (2006), Critical percolation on random regular graphs, preprint. Available at http://www.arxiv.org/abs/0707.2839.
• 2: Naor A., Peres Y., Schramm O. and Sheffield S., Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math. J. 134 (2006), no. 1, 165--197
• 3: Morris B. and Peres Y., Evolving sets, mixing and heat kernel bounds. Probab. Theory Related Fields 133 (2005), no. 2, 245--266.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory