RANDOM WALKS |
||||
|
Title: Diffusive
estimates for random walks on stationary random graphs
of polynomial growth Then there is an infinite sequence of times ${t_n}$ at which the random walk ${X_t}$ on $(G,\rho)$ is at most diffusive: Almost surely (over the choice of $(G,\rho)$), there is a number $C > 0$ such that \[ \mathbb{E} \left[\mathrm{dist}_G(X_0, X_{t_n})^2 \mid X_0 = \rho, (G,\rho)\right]\leq C t_n\qquad \forall n \geq 1\,. \] This result is new even in the case when $G$ is a stationary random subgraph of $\mathbb{Z}^d$. Combined with the work of Benjamini, Duminil-Copin, Kozma, and Yadin (2015), it implies that $G$ almost surely does not admit a non-constant harmonic function of sublinear growth. To complement this, we argue that passing to a subsequence of times ${t_n}$ is necessary, as there are stationary random graphs of (almost sure) polynomial growth where the random walk is almost surely superdiffusive at an infinite subset of times. |
arXiv |
Geom. Funct. Anal. 27 (2017), no. 3, 596–630. | ||
|
Title: Recurrence of
planar graph limits |
arXiv | Ann. of Math. (2) 177 (2013), no. 2, 761–781. | ||
|
Title: Cover
times, blanket times, and majorizing measures Abstract: We exhibit
a strong connection between cover times of graphs,
Gaussian processes, and Talagrand's theory of majorizing
measures. In particular, we show that the cover time of
any graph $G$ is equivalent, up to universal constants,
to the square of the expected maximum of the Gaussian
free field on $G$, scaled by the number of edges in $G$.
This allows us to resolve a number of open questions. We
give a deterministic polynomial-time algorithm that
computes the cover time to within an O(1) factor for any
graph, answering a question of Aldous and Fill (1994).
We also positively resolve the blanket time conjectures
of Winkler and Zuckerman (1996), showing that for any
graph, the blanket and cover times are within an O(1)
factor. The best previous approximation factor for both
these problems was $O((\log \log n)^2)$ for $n$-vertex
graphs, due to Kahn, Kim, Lovasz, and Vu (2000).
|
arXiv | Ann. of Math. (2) 175 (2012), no. 3, 1409–1471. |
||
|
Title: Non-backtracking
random walks mix faster Abstract: We compute
the mixing rate of a non-backtracking random walk on a
regular expander. Using some properties of Chebyshev
polynomials of the second kind, we show that this rate
may be up to twice as fast as the mixing rate of the
simple random walk. The closer the expander is to a
Ramanujan graph, the higher the ratio between the above
two mixing rates is.
As an application, we show that if $G$ is a high-girth regular expander on $n$ vertices, then a typical non-backtracking random walk of length $n$ on $G$ does not visit a vertex more than $(1+o(1))\frac{\log n}{\log\log n}$ times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing $n$ balls to $n$ bins uniformly, in contrast to the simple random walk on $G$, which almost surely visits some vertex $\Omega(\log n)$ times. |
arXiv |
Commun. Contemp.
Math. 9 (2007), no. 4, 585–603. |
||
| PERCOLATION |
||||
|
Title: Percolation on
hyperbolic graphs |
arXiv | |||
|
Title: Non-amenable
Cayley graphs of high girth have p_c < p_u and
mean-field exponents |
arXiv | Electron. Commun. Probab. 17 (2012), no. 57, 8 pp. | ||
|
Title: Is the critical
percolation probability local? |
arXiv | Probab. Theory Related Fields 149 (2011), no. 1-2, 261–269. | ||
|
Title: The
Alexander-Orbach conjecture holds in high dimensions |
arXiv | Invent. Math. 178 (2009), no. 3, 635–654. |
||
|
Title: Critical
percolation on any quasi-transitive graph of
exponential growth has no infinite clusters Abstract: We prove
that critical percolation on any quasi-transitive graph
of exponential volume growth does not have a unique
infinite cluster. This allows us to deduce from earlier
results that critical percolation on any graph in this
class does not have any infinite clusters. The result is
new when the graph in question is either amenable or
nonunimodular.
|
arXiv |
|||
|
Title: Locality
of the critical probability for transitive graphs of
exponential growth Abstract: Around
2008, Schramm conjectured that the critical
probabilities for Bernoulli bond percolation satisfy the
following continuity property: If $(G_n)_{n\geq 1}$ is a
sequence of transitive graphs converging locally to a
transitive graph $G$ and $\limsup_{n\to\infty} p_c(G_n)
< 1$, then $ p_c(G_n)\to p_c(G)$ as $n\to\infty$. We
verify this conjecture under the additional hypothesis
that there is a uniform exponential lower bound on the
volume growth of the graphs in question. The result is
new even in the case that the sequence of graphs is
uniformly nonamenable.
In the unimodular case, this result is obtained as a corollary to the following theorem of independent interest: For every $g>1$ and $M<\infty$, there exist positive constants $C=C(g,M)$ and $\delta=\delta(g,M)$ such that if $G$ is a transitive unimodular graph with degree at most $M$ and growth $\operatorname{gr}(G) := \inf_{r\geq 1} |B(o,r)|^{1/r}\geq g$, then \[ \mathbf{P}_{p_c} \bigl(|K_o|\geq n\bigr) \leq C n^{-\delta} \] for every $n\geq 1$, where $K_o$ is the cluster of the root vertex $o$. The proof of this inequality makes use of new universal bounds on the probabilities of certain two-arm events, which hold for every unimodular transitive graph. |
arXiv |
|||
| RANDOM SPANNING FORESTS |
||||
|
Title:
Indistinguishability of Trees in Uniform Spanning
Forests |
arXiv | Probab. Theory
Related Fields 168 (2017), no. 1-2, 113–152. |
||
| Miscellaneous |
||||
| Evans, William; Kenyon, Claire; Peres, Yuval; Schulman, Leonard J. Broadcasting
on trees and the Ising model. Ann. Appl. Probab. 10 (2000), no. 2, 410–433. Consider a process in which information is transmitted from a given root node on a noisy tree network .We start with an unbiased random bit at the root of the tree and send it down the edges of .On every edge the bit can be reversed with probability , and these errors occur independently. The goal is to reconstruct from the values which arrive at the th level of the tree. This model has been studied in information theory,genetics and statistical mechanics.We bound the reconstruction probability from above, using the maximum flow on viewed as a capacitated network, and from below using the electrical conductance of . For general infinite trees, we establish a sharp threshold: the probability of correct reconstruction tends to 1/2 as if , but the reconstruction probability stays bounded away from ½ if the opposite inequality holds. Here is the critical probability for percolation on ; in particular for the -regular tree. The asymptotic reconstruction problem is equivalent to purity of the “free boundary” Gibbs state for the Ising model on a tree. The special case of regular trees was solved in 1995 by Bleher, Ruiz and Zagrebnov; our extension to general trees depends on a coupling argument and on a reconstruction algorighm that weights the input bits by the electrical current flow from the root to the leaves. |
link
to published version |
|||
|
Title: A new
proof of Friedman's second eigenvalue Theorem and its
extension to random lifts Abstract: It was
conjectured by Alon and proved by Friedman that a random
$d$-regular graph has nearly the largest possible
spectral gap, more precisely, the largest absolute value
of the non-trivial eigenvalues of its adjacency matrix
is at most $2\sqrt{d-1} +o(1)$ with probability tending
to one as the size of the graph tends to infinity. We
give a new proof of this statement. We also study
related questions on random $n$-lifts of graphs and
improve a recent result by Friedman and Kohler.
|
arXiv |
|||
|
Title: Vacant Set of
Random Interlacements and Percolation |
arXiv | Ann. of Math. (2) 171 (2010), no. 3 | ||
| Berger, Noam; Kenyon, Claire; Mossel, Elchanan; Peres, Yuval Glauber
dynamics on trees and
hyperbolic graphs. Probab. Theory Related Fields 131 (2005), no. 3, 311–340. We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap |λ1−λ2|) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that for general graphs, if the relaxation time τ2 satisfies τ2=O(1), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp. |
link
to published version |
|||
|
Title: Determinantal
Probability: Basic Properties and Conjectures Abstract: We describe
the fundamental constructions and properties of
determinantal probability measures and point processes,
giving streamlined proofs. We illustrate these with some
important examples. We pose several general questions
and conjectures.
|
arXiv |
|||
| Choose a chapter from the Lyons-Peres book
to present. Do not choose chapters 2-10 since we'll cover
those in class. Recommended chapters are: 12, 13, 15 since
those only depend on the stuff we'll cover in class. |
||||