The Scaling Limit of the Incipient Infinite Cluster in High-Dimensional Percolation. I. Critical Exponents

This is the first of two papers on the critical behavior of bond percolation models in high dimensions. In this paper, we obtain strong joint control of the critical exponents and for the nearest neighbor model in very high dimensions d6 and for sufficiently spread-out models in all dimensions d>6. The exponent describes the low-frequency behavior of the Fourier transform of the critical two-point connectivity function, while describes the behavior of the magnetization at the critical point. Our main result is an asymptotic relation showing that, in a joint sense, =0 and =2. The proof uses a major extension of our earlier expansion method for percolation. This result provides evidence that the scaling limit of the incipient infinite cluster is the random probability measure on ^d known as integrated super-Brownian excursion (ISE), in dimensions above 6. In the sequel to this paper, we extend our methods to prove that the scaling limits of the incipient infinite cluster's two-point and three-point functions are those of ISE for the nearest neighbor model in dimensions d6.     

High-Dimensional Incipient Infinite Clusters Revisited

The incipient infinite cluster (IIC) measure is the percolation measure at criticality conditioned on the cluster of the origin to be infinite. Using the lace expansion, we construct the IIC measure for high-dimensional percolation models in three different ways, extending previous work by the second-named author and Járai. We show that each construction yields the same measure, indicating that the IIC is a robust object. Furthermore, our constructions apply to spread-out versions of both finite-range and long-range percolation models. We also get estimates on structural properties of the IIC, such as the volume of the intersection between the IIC and Euclidean balls.     

Invasion Percolation and the Incipient Infinite Cluster in 2D

 We establish two links between two-dimensional invasion percolation and Kesten's incipient infinite cluster (IIC). We first prove that the k ^th moment of the number of invaded sites within the box [−n, n]×[−n, n] is of order (n ²π _n ) ^k , for k≥1, where π _n is the probability that the origin in critical percolation is connected to the boundary of a box of radius n. This improves a result of Y. Zhang. We show that the size of the invaded region, when scaled by n ²π _n , is tight. Secondly, we prove that the invasion cluster looks asymptotically like the IIC, when viewed from an invaded site v, in the limit |v|→∞. We also establish this when an invaded site v is chosen at random from a box of radius n, and n→∞. Received: 3 December 2000 / Accepted: 3 December 2002 Published online: 18 February 2003 RID="⋆" ID="⋆" Present address: CWI, PNA 3, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands. E-mail:jarai@cwi.nl Communicated by M. Aizenman     

Random Walk on the Incipient Infinite Cluster for Oriented Percolation in High Dimensions

We consider simple random walk on the incipient infinite cluster for the spread-out model of oriented percolation on . In dimensions d > 6, we obtain bounds on exit times, transition probabilities, and the range of the random walk, which establish that the spectral dimension of the incipient infinite cluster is , and thereby prove a version of the Alexander–Orbach conjecture in this setting. The proof divides into two parts. One part establishes general estimates for simple random walk on an arbitrary infinite random graph, given suitable bounds on volume and effective resistance for the random graph. A second part then provides these bounds on volume and effective resistance for the incipient infinite cluster in dimensions d > 6, by extending results about critical oriented percolation obtained previously via the lace expansion.     

Existence of a Non-Averaging Regime for the Self-Avoiding Walk on a High-Dimensional Infinite Percolation Cluster

Let $Z_N$ be the number of self-avoiding paths of length $N$ starting from the origin on the infinite cluster obtained after performing Bernoulli percolation on ${\mathbb Z} ^d$ with parameter $p>p_c({\mathbb Z} ^d)$ . The object of this paper is to study the connective constant of the dilute lattice $\limsup _{N\rightarrow \infty } Z_N^{1/N}$ , which is a non-random quantity. We want to investigate if the inequality $\limsup _{N\rightarrow \infty } (Z_N)^{1/N} \le \lim _{N\rightarrow \infty } {\mathbb E} [Z_N]^{1/N}$ obtained with the Borel–Cantelli Lemma is strict or not. In other words, we want to know if the quenched and annealed versions of the connective constant are equal. On a heuristic level, this indicates whether or not localization of the trajectories occurs. We prove that when $d$ is sufficiently large there exists $p^{(2)}_c>p_c$ such that the inequality is strict for $p\in (p_c,p^{(2)}_c)$ .     

Construction of the Incipient Infinite Cluster for Spread-out Oriented Percolation Above 4 + 1 Dimensions

 We construct the incipient infinite cluster measure (IIC) for sufficiently spread-out oriented percolation on ℤ ^d × ℤ₊, for d +1 > 4+1. We consider two different constructions. For the first construction, we define ℙ ⁿ (E) by taking the probability of the intersection of an event E with the event that the origin is connected to (x,n)  ℤ ^d × ℤ₊, summing this probability over x  ℤ ^d , and normalising the sum to get a probability measure. We let n → ∞ and prove existence of a limiting measure ℙ_∞, the IIC. For the second construction, we condition the connected cluster of the origin in critical oriented percolation to survive to time n, and let n → ∞. Under the assumption that the critical survival probability is asymptotic to a multiple of n ⁻¹, we prove existence of a limiting measure ℚ_∞, with ℚ_∞ = ℙ_∞. In addition, we study the asymptotic behaviour of the size of the level set of the cluster of the origin, and the dimension of the cluster of the origin, under ℙ_∞. Our methods involve minor extensions of the lace expansion methods used in a previous paper to relate critical oriented percolation to super-Brownian motion, for d+1 > 4+1. Received: 13 December 2001 / Accepted: 11 July 2002 Published online: 29 October 2002 RID="*" ID="*" Present address: Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands. E-mail: rhofstad@win.tue.nl     

An Infinite Number of Effectively Infinite Clusters in Critical Percolation

An infinite number of effectively infinite clusters are predicted at the percolation threshold, if effectively infinite means that a cluster's mass increases with a positive power of the lattice size L. All these cluster masses increase as L _D with the fractal dimension D = d – /v, while the mass of the rth largest cluster for fixed L decreases as 1/r , with = D/d in d dimensions. These predictions are confirmed by computer simulations for the square lattice, where D = 91/48 and = 91/96.     

Efficient Construction of High-Dimensional Cluster State

We present a scheme for efficiently constructing high-dimensional cluster state using probabilistic entangling quantum gates. It is shown that the required computational overhead scales efficiently both with lip and n even if all the entangling quantum gates only succeed with an arbitrary small probability, where p is the success probability of the entangling quantum gate and n is the number of qubits in the computation.     

Percolation on Infinite Graphs and Isoperimetric Inequalities

We consider the Bernoulli bond percolation process (with parameter p) on infinite graphs and we give a general criterion for bounded degree graphs to exhibit a non-trivial percolation threshold based either on a single isoperimetric inequality if the graph has a bi-infinite geodesic, or two isoperimetric inequalities if the graph has not a bi-infinite geodesic. This new criterion extends previous criteria and brings together a large class of amenable graphs (such as regular lattices) and non-amenable graphs (such trees). We also study the finite connectivity in graphs satisfying the new general criterion and show that graphs in this class with a bi-infinite geodesic always have finite connectivity functions with exponential decay when p is sufficiently close to one. On the other hand, we show that there are graphs in the same class with no bi-infinite geodesic for which the finite connectivity decays sub-exponentially (down to polynomially) in the highly supercritical phase even for p arbitrarily close to one.     

Non-coexistence of Infinite Clusters in Two-Dimensional Dependent Site Percolation

This paper presents three results on dependent site percolation on the square lattice. First, there exists no positively associated probability measure on {0,1}^{mathbb Z2}{0,1}^{mathbb {Z}^{2}} with the following properties: (a) a single infinite 0cluster exists almost surely, (b) at most one infinite 1∗cluster exists almost surely, (c) certain probabilities regarding 1∗clusters are bounded away from zero. Second, the coexistence of an infinite 1∗cluster and an infinite 0cluster has probability zero when the underlying probability measure is ergodic with respect to translations, positively associated, and satisfies the finite energy condition. The third result analyzes the typical structure of infinite clusters of both types in the absence of positive association. Namely, under a slightly sharpened finite energy condition, the existence of infinitely many disjoint infinite self-avoiding 1∗paths follows from the existence of an infinite 1∗cluster. The same holds with respect to 0paths and 0clusters.     

Busemann Functions and Infinite Geodesics in Two-Dimensional First-Passage Percolation

We study first-passage percolation on ${\mathbb{Z}^2}$ , where the edge weights are given by a translation-ergodic distribution, addressing questions related to existence and coalescence of infinite geodesics. Some of these were studied in the late 1990s by C. Newman and collaborators under strong assumptions on the limiting shape and weight distribution. In this paper we develop a framework for working with distributional limits of Busemann functions and use it to prove forms of Newman’s results under minimal assumptions. For instance, we show a form of coalescence of long finite geodesics in any deterministic direction. We also introduce a purely directional condition which replaces Newman’s global curvature condition and whose assumption we show implies the existence of directional geodesics. Without this condition, we prove existence of infinite geodesics which are directed in sectors. Last, we analyze distributional limits of geodesic graphs, proving almost-sure coalescence and nonexistence of infinite backward paths. This result relates to the conjecture of nonexistence of “bigeodesics.”     

Percolation of the Loss of Tension in an Infinite Triangular Lattice

We introduce a new class of bootstrap percolation models where the local rules are of a geometric nature as opposed to simple counts of standard bootstrap percolation. Our geometric bootstrap percolation comes from rigidity theory and convex geometry. We outline two percolation models: a Poisson model and a lattice model. Our Poisson model describes how defects--holes is one of the possible interpretations of these defects--imposed on a tensed membrane result in a redistribution or loss of tension in this membrane; the lattice model is motivated by applications of Hooke spring networks to problems in material sciences. An analysis of the Poisson model is given by Menshikov et al. ⁽⁴⁾ In the discrete set-up we consider regular and generic triangular lattices on the plane where each bond is removed with probability 1–p. The problem of the existence of tension on such lattice is solved by reducing it to a bootstrap percolation model where the set of local rules follows from the geometry of stresses. We show that both regular and perturbed lattices cannot support tension for any p<1. Moreover, the complete relaxation of tension--as defined in Section 4--occurs in a finite time almost surely. Furthermore, we underline striking similarities in the properties of the Poisson and lattice models.     

On the Anisotropic Walk on the Supercritical Percolation Cluster

We investigate in this work the asymptotic behavior of an anisotropic random walk on the supercritical cluster for bond percolation on ^d, d2. In particular we show that for small anisotropy the walk behaves in a ballistic fashion, whereas for strong anisotropy the walk is sub-diffusive. For arbitrary anisotropy, we also prove the directional transience of the walk and construct a renewal structure.     

Infinite Graphs with a Nontrivial Bond Percolation Threshold: Some Sufficient Conditions

We consider Bernoulli bond percolation on infinite graphs and we identify a class of graphs for which the critical percolation probability is strictly less than 1. The graphs in this class have to fulfill conditions stated in terms of a minimal cut set property and a logarithmic isoperimetric inequality. For the particular case of planar graphs the condition on minimal cut sets can be be replaced by the assumption that the dual of the graph is bounded degree.     

The Diameter of a Long-Range Percolation Cluster on Generalized Pre-Sierpinski Carpet and Regular Tree

Journal of Statistical Physics - We consider some kinds of graphs obtained by generalizing the pre-Sierpinski carpet, which is one of well known fractal lattices. Here, we deal with not only some...     

Four Types of Percolation Transitions in the Cluster Aggregation Network Model

We study the percolation transition in a one-species cluster aggregation network model, in which the parameter α describes the suppression on the cluster sizes. It is found that the model can exhibit four types of percolation transitions, two continuous percolation transitions and two discontinuous ones. Continuous and discontinuous percolation transitions can be distinguished from each other by the largest single jump. Two types of continuous percolation transitions show different behaviors in the time gap. Two types of discontinuous percolation transitions are different in the time evolution of the cluster size distribution. Moreover, we also find that the time gap may also be a measure to distinguish different discontinuous percolations in this model.     

Sharpness of the Phase Transition and Exponential Decay of the Subcritical Cluster Size for Percolation on Quasi-Transitive Graphs

We study homogeneous, independent percolation on general quasi-transitive graphs. We prove that in the disorder regime where all clusters are finite almost surely, in fact the expectation of the cluster size is finite. This extends a well-known theorem by Menshikov and Aizenman & Barsky to all quasi-transitive graphs. Moreover we deduce that in this disorder regime the cluster size distribution decays exponentially, extending a result of Aizenman & Newman. Our results apply to both edge and site percolation, as well as long range (edge) percolation. The proof is based on a modification of the Aizenman & Barsky method.     

High-Dimensional Separability for One- and Few-Shot Learning

This work is driven by a practical question: corrections of Artificial Intelligence (AI) errors. These corrections should be quick and non-iterative. To solve this problem without modification of a legacy AI system, we propose special ‘external’ devices, correctors. Elementary correctors consist of two parts, a classifier that separates the situations with high risk of error from the situations in which the legacy AI system works well and a new decision that should be recommended for situations with potential errors. Input signals for the correctors can be the inputs of the legacy AI system, its internal signals, and outputs. If the intrinsic dimensionality of data is high enough then the classifiers for correction of small number of errors can be very simple. According to the blessing of dimensionality effects, even simple and robust Fisher’s discriminants can be used for one-shot learning of AI correctors. Stochastic separation theorems provide the mathematical basis for this one-short learning. However, as the number of correctors needed grows, the cluster structure of data becomes important and a new family of stochastic separation theorems is required. We refuse the classical hypothesis of the regularity of the data distribution and assume that the data can have a rich fine-grained structure with many clusters and corresponding peaks in the probability density. New stochastic separation theorems for data with fine-grained structure are formulated and proved. On the basis of these theorems, the multi-correctors for granular data are proposed. The advantages of the multi-corrector technology were demonstrated by examples of correcting errors and learning new classes of objects by a deep convolutional neural network on the CIFAR-10 dataset. The key problems of the non-classical high-dimensional data analysis are reviewed together with the basic preprocessing steps including the correlation transformation, supervised Principal Component Analysis (PCA), semi-supervised PCA, transfer component analysis, and new domain adaptation PCA.