The Random-Cluster Model / Geoffrey Grimmett |
Models of First-Passage Percolation / C. Douglas Howard |
Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures / Fabio Martinelli |
Random Walks on Finite Groups / Laurent Saloff-Coste |
Index |
Introduction / 1: |
A Motivating Example: the Assignment Problem / 1.1: |
A Stalking Horse: the Partial Matching Problem / 1.2: |
Organization of the Survey / 1.3: |
Geometric Graphs and Local Weak Convergence / 2: |
Geometric Graphs / 2.1: |
<$>{\cal G}^\ast<$> as a Metric Space / 2.2: |
Local Weak Convergence / 2.3: |
The Standard Construction / 2.4: |
A Prototype: The Limit of Uniform Random Trees / 2.5: |
Maximal Weight Partial Matching on Random Trees / 3: |
Weighted Matchings of Graphs in General / 3.1: |
Our Case: Random Trees with Random Edge Weights / 3.2: |
Two Obvious Guesses: One Right, One Wrong / 3.3: |
Not Your Grandfather's Recursion / 3.4: |
A Direct and Intuitive Plan / 3.5: |
Characterization of the Limit of <$>B(T_n^{small})<$> / 3.6: |
Characterization of the Limit of <$>B(T_n^{big})<$> / 3.7: |
The Limit Theorem for Maximum Weight Partial Matchings / 3.8: |
Closing the Loop: Another Probabilistic Solution of a Fixed-Point Equation / 3.9: |
From Coupling to Stability - Thence to Convergence / 3.10: |
Looking Back: Perspective on a Case Study / 3.11: |
The Mean-Field Model of Distance / 4: |
From Poisson Points in <$>{\op R}^{d}<$> to a Simple Distance Model / 4.1: |
The Poisson Weighted Infinite Tree - or, the PWIT / 4.2: |
The Cut-off Components of a Weighted Graph and a PWIT / 4.3: |
The Minimum Spanning Forests of an Infinite Graph / 4.4: |
The Average Length Per Vertex of the MSF of a PWIT / 4.5: |
The Connection to Frieze's ζ(3) Theorem / 4.6: |
Minimal Cost Perfect Matchings / 5: |
A Natural Heuristic - Which Fails for a Good Reason / 5.1: |
Involution Invariance and the Standard Construction / 5.2: |
Involution Invariance and the Convergence of MSTs / 5.3: |
A Heuristic That Works by Focusing on the Unknown / 5.4: |
A Distributional Identity with a Logistic Solution / 5.5: |
A Stochastic Process that Constructs a Matching / 5.6: |
Calculation of a Limiting Constant: <$>\pi^{2}/6<$> / 5.7: |
Passage from a PWIT Matching to a Kn Matching / 5.8: |
Finally - Living Beyond One's Means / 5.9: |
Problems in Euclidean Space / 6: |
A Motivating Problem / 6.1: |
Far Away Places and Their Influence / 6.2: |
Euclidean Methods and Some Observations in Passing / 6.3: |
Recurrence of Random Walks in Limits of Planar Graphs / 6.4: |
Limitations, Challenges, and Perspectives / 7: |
References |
Potts and random-cluster processes |
Random-cluster measures |
Ising and Potts models |
Random-cluster and Ising-Potts coupled |
The limit as <$>q \downarrow 0<$> |
Rank-generating functions |
Infinite-volume random-cluster measures |
Stochastic ordering |
A differential formula |
Conditional probabilities |
Infinite-volume weak limits |
Random-cluster measures on infinite graphs |
The case q < 1 |
Phase transition, the big picture |
Infinite open clusters |
First- and second-order phase transition |
General results in d (≥ 2) dimensions |
The subcritical phase, p < pc(q) |
The supercritical phase, p > pc(q) |
Near the critical point, p ≃ pc(q) |
In two dimensions |
Graphical duality |
Value of the critical point |
First-order phase transition |
SLE limit when q ≤ 4 |
On complete graphs and trees |
On complete graphs / 7.1: |
On trees and non-amenable graphs / 7.2: |
Time-evolutions of random-cluster models / 8: |
Reversible dynamics / 8.1: |
Coupling from the past / 8.2: |
Swendsen-Wang dynamics / 8.3: |
The Basic Model and Some Fundamental Questions |
Notation |
The Time Constant |
The Fundamental Processes of Hammersley and Welsh |
About μ |
Minimizing Paths |
Asymptotic Shape and Shape Fluctuations |
Shape Theorems for Standard FPP |
About the Asymptotic Shape for Lattice FPP |
FPP Based on Poisson Point Processes |
Upper Bounds on Shape Fluctuations |
Some Related Longitudinal Fluctuation Exponents |
Monotonicity |
Transversal Fluctuations and the Divergence of Shape Fluctuations |
Transversal Fluctuation Exponents |
Upper Bounds on <$>\xi<$> |
Lower Bounds on <$>\chi<$> |
Lower Bounds on <$>\xi<$> |
Fluctuations for Other Related Models |
Infinite Geodesics and Spanning Trees |
Semi-Infinite Geodesics and Spanning Trees |
Coalescence and Another Spanning Tree in 2 Dimensions |
Doubly-Infinite Geodesics |
Summary of Some Open Problems |
Mixing times for reversible, continuous-time Markov chains |
Analytic methods |
Tensorization of the Poincaré and logarithmic Sobolev inequalities |
Geometric tools |
Comparison methods |
Coupling methods and block dynamics |
Statistical mechanics models in <$>{\op Z}^d<$> |
Grand canonical Gibbs measures |
Mixing conditions and absence of long-range order |
Canonical Gibbs measures for lattice gases |
The ferromagnetic Ising and Potts models |
FK representation of Potts models |
Antiferromagnetic models on an arbitrary graph: Potts and hard-core models |
Model with random interactions |
Unbounded spin systems |
Ground states of certain quantum Heisenberg models as classical Gibbs measures |
Glauber dynamics in <$>{\op Z}^d<$> |
The dynamics in a finite volume |
The dynamics in an infinite volume |
Graphical construction |
Uniform ergodicity and logarithmic Sobolev constant |
Mixing property versus logarithmic Sobolev constant in <$>{\op Z}^d<$> |
The auxiliary chain and sweeping out relations method |
The renormalization group approach |
The martingale method |
The recursive analysis |
Rapid mixing for unbounded spin systems |
Torpid mixing in the phase coexistence region |
Torpid mixing for the Ising model in <$>\Lambda \subset {\op Z}^{d}<$> with free boundary conditions |
Interface driven mixing inside one phase |
Torpid mixing for Potts model in <$>{\op Z}^d<$> |
Glauber dynamics for certain random systems in <$>{\op Z}^d<$> |
Combination of torpid and rapid mixing: the dilute Ising model |
Relaxation to equilibrium for spin glasses |
Glauber dynamics for more general structures |
Glauber dynamics on trees and hyperbolic graphs |
Glauber dynamics for the hard-core model |
Cluster algorithms: the Swendsen-Wang dynamics for Potts models |
Mixing time for conservative dynamics / 9: |
Random transposition, Bernoulli-Laplace and symmetric simple exclusion / 9.1: |
The asymmetric simple exclusion / 9.2: |
The Kac model for the Boltzmann equation / 9.3: |
Adsorbing staircase walks / 9.4: |
Kawasaki dynamics for lattice gases / 10: |
Diffusive scaling of the mixing time in the one-phase region / 10.1: |
Background and Notation / 10.2: |
Finite Markov Chains |
Invariant Markov Chains on Finite Groups |
Shuffling Cards and the Cut-off Phenomenon |
Three Examples of Card Shuffling |
Exact Computations |
The Cut-off Phenomenon |
Probabilistic Methods |
Coupling |
Strong Stationary Times |
Spectrum and Singular Values |
General Finite Markov Chains |
The Random Walk Case |
Lower Bounds |
Eigenvalue Bounds Using Paths |
Cayley Graphs |
The Second Largest Eigenvalue |
The Lowest Eigenvalue |
Diameter Bounds, Isoperimetry and Expanders |
Results Involving Volume Growth Conditions |
Moderate Growth |
Nilpotent Groups |
Nilpotent Groups with many Generators / 7.3: |
Representation Theory for Finite Groups |
The General Set-up |
Abelian Examples |
Random Random Walks |
Central Measures and Bi-invariant Walks |
Characters and Bi-invariance |
Random Transposition on the Symmetric Group |
Walks Based on Conjugacy Classes of the Symmetric Group |
Finite Classical Groups |
Fourier Analysis for Non-central Measures / 9.5: |
Comparison Techniques |
The min-max Characterization of Eigenvalues |
Comparing Dirichlet Forms Using Paths |
Comparison for Non-symmetric Walks / 10.3: |
The Random-Cluster Model / Geoffrey Grimmett |
Models of First-Passage Percolation / C. Douglas Howard |
Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures / Fabio Martinelli |