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.     

Multiplicity of Phase Transitions and Mean-Field Criticality on Highly Non-Amenable Graphs

We consider independent percolation, Ising and Potts models, and the contact process, on infinite, locally finite, connected graphs. It is shown that on graphs with edge-isoperimetric Cheeger constant sufficiently large, in terms of the degrees of the vertices of the graph, each of the models exhibits more than one critical point, separating qualitatively distinct regimes. For unimodular transitive graphs of this type, the critical behaviour in independent percolation, the Ising model and the contact process are shown to be mean-field type. For Potts models on unimodular transitive graphs, we prove the monotonicity in the temperature of the property that the free Gibbs measure is extremal in the set of automorphism invariant Gibbs measures, and show that the corresponding critical temperature is positive if and only if the threshold for uniqueness of the infinite cluster in independent bond percolation on the graph is less than 1. We establish conditions which imply the finite-island property for independent percolation at large densities, and use those to show that for a large class of graphs the q-state Potts model has a low temperature regime in which the free Gibbs measure decomposes as the uniform mixture of the q ordered phases. In the case of non-amenable transitive planar graphs with one end, we show that the q-state Potts model has a critical point separating a regime of high temperatures in which the free Gibbs measure is extremal in the set of automorphism-invariant Gibbs measures from a regime of low temperatures in which the free Gibbs measure decomposes as the uniform mixture of the q ordered phases. Received: 27 March 2000 / Accepted: 7 December 2000     

Large-deviation properties of largest component for random graphs

Distributions of the size of the largest component, in particular the large-deviationtail, are studied numerically for two graph ensembles, for Erdös-Rényi random graphs withfinite connectivity and for two-dimensional bond percolation. Probabilities as small as10^-180 are accessed using an artificial finite-temperature (Boltzmann)ensemble. The distributions for the Erdös-Rényi ensemble agree well with previouslyobtained analytical results. The results for the percolation problem, where no analyticalresults are available, are qualitatively similar, but the shapes of the distributions aresomehow different and the finite-size corrections are sometimes much larger. Furthermore,for both problems, a first-order phase transition at low temperatures Twithin the artificial ensemble is found in the percolating regime, respectively.     

Connectivity Patterns in Loop Percolation I: the Rationality Phenomenon and Constant Term Identities

Loop percolation, also known as the dense O(1) loop model, is a variant of critical bond percolation in the square lattice \({\mathbb{Z}^2}\) whose graph structure consists of a disjoint union of cycles. We study its connectivity pattern, which is a random noncrossing matching associated with a loop percolation configuration. These connectivity patterns exhibit a striking rationality property whereby probabilities of naturally-occurring events are dyadic rational numbers or rational functions of a size parameter n, but the reasons for this are not completely understood. We prove the rationality phenomenon in a few cases and prove an explicit formula expressing the probabilities in the “cylindrical geometry” as coefficients in certain multivariate polynomials. This reduces the rationality problem in the general case to that of proving a family of conjectural constant term identities generalizing an identity due to Di Francesco and Zinn-Justin. Our results make use of, and extend, algebraic techniques related to the quantum Knizhnik-Zamolodchikov equation.     

Investigation of continuous-time quantum walk via spectral distribution associated with adjacency matrix

Using the spectral distribution associated with the adjacency matrix of graphs, we introduce a new method of calculation of amplitudes of continuous-time quantum walk on some rather important graphs, such as line, cycle graph C_n, complete graph K_n, graph G_n, finite path and some other finite and infinite graphs, where all are connected with orthogonal polynomials such as Hermite, Laguerre, Tchebichef, and other orthogonal polynomials. It is shown that using the spectral distribution, one can obtain the infinite time asymptotic behavior of amplitudes simply by using the method of stationary phase approximation (WKB approximation), where as an example, the method is applied to star, two-dimensional comb lattices, infinite Hermite and Laguerre graphs. Also by using the Gauss quadrature formula one can approximate the infinite graphs with finite ones and vice versa, in order to derive large time asymptotic behavior by WKB method. Likewise, using this method, some new graphs are introduced, where their amplitudes are proportional to the product of amplitudes of some elementary graphs, even though the graphs themselves are not the same as the Cartesian product of their elementary graphs. Finally, by calculating the mean end to end distance of some infinite graphs at large enough times, it is shown that continuous-time quantum walk at different infinite graphs belong to different universality classes which are also different from those of the corresponding classical ones.     

Core percolation in random graphs: a critical phenomena analysis

We study both numerically and analytically what happens to a random graph of average connectivity α when its leaves and their neighbors are removed iteratively up to the point when no leaf remains. The remnant is made of isolated vertices plus an induced subgraph we call the core. In the thermodynamic limit of an infinite random graph, we compute analytically the dynamics of leaf removal, the number of isolated vertices and the number of vertices and edges in the core. We show that a second order phase transition occurs at α = e = 2.718 ... : below the transition, the core is small but above the transition, it occupies a finite fraction of the initial graph. The finite size scaling properties are then studied numerically in detail in the critical region, and we propose a consistent set of critical exponents, which does not coincide with the set of standard percolation exponents for this model. We clarify several aspects in combinatorial optimization and spectral properties of the adjacency matrix of random graphs. Received 31 January 2001 and Received in final form 26 June 2001     

On a Property of Random-Oriented Percolation in a Quadrant

Grimmett’s random-orientation percolation is formulated as follows. The square lattice is used to generate an oriented graph such that each edge is oriented rightwards (resp. upwards) with probability p and leftwards (resp. downwards) otherwise. We consider a variation of Grimmett’s model proposed by Hegarty, in which edges are oriented away from the origin with probability p, and towards it with probability 1?p, which implies rotational instead of translational symmetry. We show that both models could be considered as special cases of random-oriented percolation in the NE-quadrant, provided that the critical value for the latter is $\frac{1}{2}$ . As a corollary, we unconditionally obtain a non-trivial lower bound for the critical value of Hegarty’s random-orientation model. The second part of the paper is devoted to higher dimensions and we show that the Grimmett model percolates in any slab of height at least 3 in  $\mathbb{Z}^{3}$ .     

Anosov Geodesic Flows,Billiards and Linkages

Any smooth surface in \({{\mathbb R}^{3}}\) may be flattened along the z-axis, and the flattened surface becomes close to a billiard table in \({{\mathbb R}^{2}}\). We show that, under some hypotheses, the geodesic flow of this surface converges locally uniformly to the billiard flow. Moreover, if the billiard is dispersive and has finite horizon, then the geodesic flow of the corresponding surface is Anosov. We apply this result to the theory of mechanical linkages and their dynamics: we provide a new example of a simple linkage whose physical behavior is Anosov. For the first time, the edge lengths of the mechanism are given explicitly.     

Dynamics of Nearest-Neighbour Competitions on Graphs

Considering a collection of agents representing the vertices of a graph endowed with integer points, we study the asymptotic dynamics of the rate of the increase of their points according to a very simple rule: we randomly pick an an edge from the graph which unambiguously defines two agents we give a point the the agent with larger point with probability p and to the lagger with probability q such that \(p+q=1\). The model we present is the most general version of the nearest-neighbour competition model introduced by Ben-Naim, Vazquez and Redner. We show that the model combines aspects of hyperbolic partial differential equations—as that of a conservation law—graph colouring and hyperplane arrangements. We discuss the properties of the model for general graphs but we confine in depth study to d-dimensional tori. We present a detailed study for the ring graph, which includes a chemical potential approximation to calculate all its statistics that gives rather accurate results. The two-dimensional torus, not studied in depth as the ring, is shown to possess critical behaviour in that the asymptotic speeds arrange themselves in two-coloured islands separated by borders of three other colours and the size of the islands obey power law distribution. We also show that in the large d limit the d-dimensional torus shows inverse sine law for the distribution of asymptotic speeds.     

On AB Bond Percolation on the Square Lattice and AB Site Percolation on Its Line Graph

We prove that AB site percolation occurs on the line graph of the square lattice when $p \in (1 - \sqrt {1 - p_c } ,\sqrt {1 - p_c } )$ , where p _c is the critical probability for site percolation in $\mathbb{Z}^2$ . Also, we prove that AB bond percolation does not occur on $\mathbb{Z}^2$ for p = $\frac{1}{2}$ .     

Monte Carlo simulation of the percolation process caused by the random sequential adsorption of k-mers on heterogeneous triangular lattices

Mixed site-bond percolation is studied for a random sequential adsorption process of k-mers on heterogeneous lattices with variable connectivity by means of Monte Carlo simulation. The percolation phase diagrams are built to render evidence about complex structures. Critical exponents are also calculated to show that the universality class corresponding to ordinary percolation in two dimensions is preserved.     

The Critical Ising Model via Kac-Ward Matrices

The Kac-Ward formula allows to compute the Ising partition function on any finite graph G from the determinant of 2^2g matrices, where g is the genus of a surface in which G embeds. We show that in the case of isoradially embedded graphs with critical weights, these determinants have quite remarkable properties. First of all, they satisfy some generalized Kramers-Wannier duality: there is an explicit equality relating the determinants associated to a graph and to its dual graph. Also, they are proportional to the determinants of the discrete critical Laplacians on the graph G, exactly when the genus g is zero or one. Finally, they share several formal properties with the Ray-Singer ${\overline{\partial}}$ -torsions of the Riemann surface in which G embeds.     

Some Exact Results on Bond Percolation

We present some exact results on bond percolation. We derive a relation that specifies the consequences for bond percolation quantities of replacing each bond of a lattice ?? by ? bonds connecting the same adjacent vertices, thereby yielding the lattice ?? _? . This relation is used to calculate the bond percolation threshold on ?? _? . We show that this bond inflation leaves the universality class of the percolation transition invariant on a lattice of dimensionality d??2 but changes it on a one-dimensional lattice and quasi-one-dimensional infinite-length strips. We also present analytic expressions for the average cluster number per vertex and correlation length for the bond percolation problem on the N???? limits of several families of N-vertex graphs. Finally, we explore the effect of bond vacancies on families of graphs with the property of bounded diameter as N????.     

The Incipient Infinite Cluster for High-Dimensional Unoriented Percolation

We consider bond percolation on $\mathbb{Z}^d$ at the critical occupation density p _c for d>6 in two different models. The first is the nearest-neighbor model in dimension d?6. The second model is a “spread-out” model having long range parameterized by L in dimension d>6. In the spread-out case, we show that the cluster of the origin conditioned to contain the site x weakly converges to an infinite cluster as |x|→∞ when d>6 and L is sufficiently large. We also give a general criterion for this convergence to hold, which is satisfied in the case d?6 in the nearest-neighbor model by work of Hara.⁽¹²⁾ We further give a second construction, by taking p<p _c , defining a measure $\mathbb{Q}^p $ and taking its limit as p↗p ^? _c . The limiting object is the high-dimensional analogue of Kesten's incipient infinite cluster (IIC) in d=2. We also investigate properties of the IIC such as bounds on the growth rate of the cluster that show its four-dimensional nature. The proofs of both the existence and of the claimed properties of the IIC use the lace expansion. Finally, we give heuristics connecting the incipient infinite cluster to invasion percolation, and use this connection to support the well-known conjecture that for d>6 the probability for invasion percolation to reach a site x is asymptotic to c|x|^?(d?4) as |x|→∞.     

Percolation in a network with long-range connections: Implications for cytoskeletal structure and function

Cell shape, signaling, and integrity depend on cytoskeletal organization. In this study we describe the cytoskeleton as a simple network of filamentary proteins (links) anchored by complex protein structures (nodes). The structure of this network is regulated by a distance-dependent probability of link formation as P=p/d^s, where p regulates the network density and s controls how fast the probability for link formation decays with node distance (d). It was previously shown that the regulation of the link lengths is crucial for the mechanical behavior of the cells. Here we examined the ability of the two-dimensional network to percolate (i.e. to have end-to-end connectivity), and found that the percolation threshold depends strongly on s. The system undergoes a transition around s=2. The percolation threshold of networks with s<2 decreases with increasing system size L, while the percolation threshold for networks with s>2 converges to a finite value. We speculate that s<2 may represent a condition in which cells can accommodate deformation while still preserving their mechanical integrity. Additionally, we measured the length distribution of F-actin filaments from publicly available images of a variety of cell types. In agreement with model predictions, cells originating from more deformable tissues show longer F-actin cytoskeletal filaments.     

Dynamics of a neural network model with finite connectivity and cycle stored patterns

The spatiotemporal evolution and memory retrieval properties of a Hopfield-like neural network with cycle-stored patterns and finite connectivity are studied. The analytical studies on a mean-field version show that, given the number of stored patterns p, there is a critical connectivity k_c such that the retrieval states are stable fixed points if and only if k > k_c. The dependence of k_c on the number of stored patterns is also present. The numerical simulations are applied to the short-ranged model with local interaction. It is revealed that, given p, the memory retrieval function is kept if the connectivity is high enough while the dynamics of the system is in the frozen phase. However when the connectivity k is less than a critical value k_c the system is in the chaotic phase and loses its memory retrieval ability. The critical points of both the dynamical phase transition and memory-loss phase transition are obtained by simulation data.     

Scattering theory and discrete-time quantum walks

We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each, and consider walks that proceed from one half line, through the graph, to the other. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph.     

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

n-Particle Quantum Statistics on Graphs

We develop a full characterization of abelian quantum statistics on graphs. We explain how the number of anyon phases is related to connectivity. For 2-connected graphs the independence of quantum statistics with respect to the number of particles is proven. For non-planar 3-connected graphs we identify bosons and fermions as the only possible statistics, whereas for planar 3-connected graphs we show that one anyon phase exists. Our approach also yields an alternative proof of the structure theorem for the first homology group of n-particle graph configuration spaces. Finally, we determine the topological gauge potentials for 2-connected graphs.     

Evolution of a Modified Binomial Random Graph by Agglomeration

In the classical Erd?s–Rényi random graph G(n, p) there are n vertices and each of the possible edges is independently present with probability p. The random graph G(n, p) is homogeneous in the sense that all vertices have the same characteristics. On the other hand, numerous real-world networks are inhomogeneous in this respect. Such an inhomogeneity of vertices may influence the connection probability between pairs of vertices. The purpose of this paper is to propose a new inhomogeneous random graph model which is obtained in a constructive way from the Erd?s-Rényi random graph G(n, p). Given a configuration of n vertices arranged in N subsets of vertices (we call each subset a super-vertex), we define a random graph with N super-vertices by letting two super-vertices be connected if and only if there is at least one edge between them in G(n, p). Our main result concerns the threshold for connectedness. We also analyze the phase transition for the emergence of the giant component and the degree distribution. Even though our model begins with G(n, p), it assumes the existence of some community structure encoded in the configuration. Furthermore, under certain conditions it exhibits a power law degree distribution. Both properties are important for real-world applications.