Is the critical percolation probability local?

We show that the critical probability for percolation on a d-regular non-amenable graph of large girth is close to the critical probability for percolation on an infinite d-regular tree. We also prove a finite analogue of this statement, valid for expander graphs, without any girth assumption.     

A note on percolation

Summary An improvement of Harris' theorem on percolation is obtained; it implies relations between critical points of matching graphs of the type of the one stated by Essam and Sykes. As another consequence, it is proved that the percolation probability, as a function of the probability of occupation of a given site, is infinitely differentiable, except at most in the critical point.     

Enlargement of subgraphs of infinite graphs by Bernoulli percolation

We consider changes in properties of a subgraph of an infinite graph resulting from the addition of open edges of Bernoulli percolation on the infinite graph to the subgraph. We give the triplet of an infinite graph, one of its subgraphs, and a property of the subgraphs. Then, in a manner similar to the way Hammersley’s critical probability is defined, we can define two values associated with the triplet. We regard the two values as certain critical probabilities, and compare them with Hammersley’s critical probability. In this paper, we focus on the following cases of a graph property: being a transient subgraph, having finitely many cut points or no cut points, being a recurrent subset, or being connected. Our results depend heavily on the choice of the triplet.Most results of this paper are announced in Okamura (2016) [24] without proofs. This paper gives full details of them.     

Circuit decompositions of join‐covered graphs

In this paper, we focus our attention on join‐covered graphs, that is, ±1‐weighted graphs, without negative circuits, in which every edge lies in a zero‐weight circuit. Join covered graphs are a natural generalization of matching‐covered graphs. Many important properties of matching covered graphs, such as the existence of a canonical partition, tight cut decomposition and ear decomposition, have been generalized to join covered graphs by A. Seb? [5]. In this paper we prove that any two edges of a join‐covered graph lie on a zero‐weight circuit (under an equivalent weighting), generalize this statement to an arbitrary number of edges, and characterize minimal bipartite join‐covered graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 220–233, 2009     

Site percolation and isoperimetric inequalities for plane graphs

We use isoperimetric inequalities combined with a new technique to prove upper bounds for the site percolation threshold of plane graphs with given minimum degree conditions. In the process we prove tight new isoperimetric bounds for certain classes of hyperbolic graphs. This establishes the vertex isoperimetric constant for all triangular and square hyperbolic lattices, answering a question of Lyons and Peres. We prove that plane graphs of minimum degree at least 7 have site percolation threshold bounded away from 1/2, which was conjectured by Benjamini and Schramm, and make progress on a conjecture of Angel, Benjamini, and Horesh that the critical probability is at most 1/2 for plane triangulations of minimum degree 6. We prove additional bounds for stronger minimum degree conditions, and for graphs without triangular faces.     

Scaling Limit for the Ant in High-Dimensional Labyrinths

We study here a detailed conjecture regarding one of the most important cases of anomalous diffusion, i.e., the behavior of the “ant in the labyrinth.” It is natural to conjecture that the scaling limit for random walks on large critical random graphs exists in high dimensions and is universal. This scaling limit is simply the natural Brownian motion on the integrated super-Brownian excursion. We give here a set of four natural, sufficient conditions on the critical graphs and prove that this set of assumptions ensures the validity of this conjecture. The remaining future task is to prove that these sufficient conditions hold for the various classical cases of critical random structures, like the usual Bernoulli bond percolation, oriented percolation, and spread-out percolation in high enough dimension. In a companion paper, we do precisely that in a first case, the random walk on the trace of a large critical branching random walk. We verify the validity of these sufficient conditions and thus obtain the scaling limit mentioned above in dimensions larger than 14. © 2019 Wiley Periodicals, Inc.     

Minimization of circuit registers: Retiming revisited

We address the following problem: given a synchronous digital circuit, is it possible to construct a new circuit computing the same function as the original one but using a minimal number of registers? We show that the minimal number of registers is the size of the minimal cut on a bi-infinite graph, namely the unfolding of the dependencies in the digital circuit. Furthermore, the construction of such a cut and the corresponding circuit can be done in polynomial time, using a max-flow min-cut result of Orlin for one-periodic bi-infinite graphs. Finally, we show the relation between this construction and the retiming technique introduced by Leiserson and Saxe.     

Bond percolation on isoradial graphs: criticality and universality

In an investigation of percolation on isoradial graphs, we prove the criticality of canonical bond percolation on isoradial embeddings of planar graphs, thus extending celebrated earlier results for homogeneous and inhomogeneous square, triangular, and other lattices. This is achieved via the star–triangle transformation, by transporting the box-crossing property across the family of isoradial graphs. As a consequence, we obtain the universality of these models at the critical point, in the sense that the one-arm and $2j$ -alternating-arm critical exponents (and therefore also the connectivity and volume exponents) are constant across the family of such percolation processes. The isoradial graphs in question are those that satisfy certain weak conditions on their embedding and on their track system. This class of graphs includes, for example, isoradial embeddings of periodic graphs, and graphs derived from rhombic Penrose tilings.     

Self-induced systems

A minimal Cantor system is said to be self-induced whenever it is conjugate to one of its induced systems. Substitution subshifts and some odometers are classical examples, and we show that these are the only examples in the equicontinuous or expansive case. Nevertheless, we exhibit a zero entropy self-induced system that is neither equicontinuous nor expansive. We also provide non-uniquely ergodic self-induced systems with infinite entropy. Moreover, we give a characterization of self-induced minimal Cantor systems in terms of substitutions on finite or infinite alphabets.     

Semi-hyper-connected edge transitive graphs

A graph G is said to be hyper-connected if the removal of every minimum cut creates exactly two connected components, one of which is an isolated vertex. In this paper, we first generalize the concept of hyper-connected graphs to that of semi-hyper-connected graphs: a graph G is called semi-hyper-connected if the removal of every minimum cut of G creates exactly two components. Then we characterize semi-hyper-connected edge transitive graphs.     

Critical Percolation and the Minimal Spanning Tree in Slabs

The minimal spanning forest on ?^d is known to consist of a single tree for d ≤ 2 and is conjectured to consist of infinitely many trees for large d . In this paper, we prove that there is a single tree for quasi‐planar graphs such as ?² × {0,…,k }^d?2. Our method relies on generalizations of the “gluing lemma” of Duminil‐Copin, Sidoravicius, and Tassion. A related result is that critical Bernoulli percolation on a slab satisfies the box‐crossing property. Its proof is based on a new Russo‐Seymour‐Welsh‐type theorem for quasi‐planar graphs. Thus, at criticality, the probability of an open path from 0 of diameter n decays polynomially in n . This strengthens the result of Duminil‐Copin et al., where the absence of an infinite cluster at criticality was first established. © 2017 Wiley Periodicals, Inc.     

Clairvoyant scheduling of random walks

Two infinite walks on the same finite graph are called compatible if it is possible to introduce delays into them in such a way that they never collide. Years ago, Peter Winkler asked the question: for which graphs are two independent random walks compatible with positive probability. Up to now, no such graphs were found. We show in this paper that large complete graphs have this property. The question is equivalent to a certain dependent percolation with a power‐law behavior: the probability that the origin is blocked at distance n but not closer decreases only polynomially fast and not, as usual, exponentially. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Two-dimensional scaling limits via marked nonsimple loops

We postulate the existence of a natural Poissonian marking of the double (touching) points of SLE₆ and hence of the related continuum nonsimple loop process that describes macroscopic cluster boundaries in 2D critical percolation. We explain how these marked loops should yield continuum versions of near-critical percolation, dynamical percolation, minimal spanning trees and related plane filling curves, and invasion percolation. We showthat this yields for some of the continuum objects a conformal covariance property that generalizes the conformal invariance of critical systems. It is an open problem to rigorously construct the continuum objects and to prove that they are indeed the scaling limits of the corresponding lattice objects.     

Minimal Configurations and Sandpile Measures

We give a new simple construction of the sandpile measure on an infinite graph G, under the sole assumption that each tree in the Wired Uniform Spanning Forest on G has one end almost surely. For the so-called generalized minimal configurations, the limiting probability on G exists even without this assumption. We also give determinantal formulas for minimal configurations on general graphs in terms of the transfer current matrix.     

Minimal multicut and maximal integer multiflow: A survey

We present a survey about the maximum integral multiflow and minimum multicut problems and their subproblems, such as the multiterminal cut and the unsplittable flow problems. We consider neither continuous multiflow nor minimum cost multiflow. Most of the results are very recent and some are new. We recall the dual relationship between both problems, give complexity results and algorithms, firstly in unrestricted graphs and secondly in several special graphs: trees, bipartite or planar graphs. A table summarizes the most important results.     

Universality in two‐dimensional enhancement percolation

We consider a type of dependent percolation introduced in 2 , where it is shown that certain “enhancements” of independent (Bernoulli) percolation, called essential, make the percolation critical probability strictly smaller. In this study we first prove that, for two‐dimensional enhancements with a natural monotonicity property, being essential is also a necessary condition to shift the critical point. We then show that (some) critical exponents and the scaling limit of crossing probabilities of a two‐dimensional percolation process are unchanged if the process is subjected to a monotonic enhancement that is not essential. This proves a form of universality for all dependent percolation models obtained via a monotonic enhancement (of Bernoulli percolation) that does not shift the critical point. For the case of site percolation on the triangular lattice, we also prove a stronger form of universality by showing that the full scaling limit 12 , 13 is not affected by any monotonic enhancement that does not shift the critical point. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Group-invariant Percolation on Graphs

Let G be a closed group of automorphisms of a graph X. We relate geometric properties of G and X, such as amenability and unimodularity, to properties of G-invariant percolation processes on X, such as the number of infinite components, the expected degree, and the topology of the components. Our fundamental tool is a new masstransport technique that has been occasionally used elsewhere and is developed further here.¶ Perhaps surprisingly, these investigations of group-invariant percolation produce results that are new in the Bernoulli setting. Most notably, we prove that critical Bernoulli percolation on any nonamenable Cayley graph has no infinite clusters. More generally, the same is true for any nonamenable graph with a unimodular transitive automorphism group.¶ We show that G is amenable if for all $ \alpha < 1 $ \alpha < 1 , there is a G-invariant site percolation process w \omega on X with $ {\bf P} [x \in \omega] > \alpha $ {\bf P} [x \in \omega] > \alpha for all vertices x and with no infinite components. When G is not amenable, a threshold $ \alpha < 1 $ \alpha < 1 appears. An inequality for the threshold in terms of the isoperimetric constant is obtained, extending an inequality of Häggström for regular trees.¶ If G acts transitively on X, we show that G is unimodular if the expected degree is at least 2 in any G-invariant bond percolation on X with all components infinite.¶ The investigation of dependent percolation also yields some results on automorphism groups of graphs that do not involve percolation.     

Asymptotic of the Critical Value of the Large-Dimensional SIR Epidemic on Clusters

In this paper we are concerned with the susceptible-infective-removed (SIR) epidemic on open clusters of bond percolation on the square lattice. For the SIR model, a susceptible vertex is infected at rate proportional to the number of infective neighbors, while an infective vertex becomes removed at a constant rate. A removed vertex will never be infected again. We assume that at \(t=0\) the only infective vertex is the origin and define the critical value of the model as the supremum of the infection rates with which infective vertices die out with probability one; then, we show that the critical value under the annealed measure is \(\big (1+o(1)\big )/(2dp)\) as the dimension d of the lattice grows to infinity, where p is the probability that a given edge is open. Furthermore, we show that the critical value under the quenched measure equals the annealed one when the origin belongs to an infinite open cluster of the percolation.     

Noise sensitivity in continuum percolation

We prove that the Poisson Boolean model, also known as the Gilbert disc model, is noise sensitive at criticality. This is the first such result for a Continuum Percolation model, and the first which involves a percolation model with critical probability p _c ≠ 1/2. Our proof uses a version of the Benjamini-Kalai-Schramm Theorem for biased product measures. A quantitative version of this result was recently proved by Keller and Kindler. We give a simple deduction of the non-quantitative result from the unbiased version. We also develop a quite general method of approximating Continuum Percolation models by discrete models with p _c bounded away from zero; this method is based on an extremal result on non-uniform hypergraphs.     

Aggregation models with limited choice and the multiplicative coalescent

The percolation phase transition and the mechanism of the emergence of the giant component through the critical scaling window for random graph models, has been a topic of great interest in many different communities ranging from statistical physics, combinatorics, computer science, social networks and probability theory. The last few years have witnessed an explosion of models which couple random aggregation rules, that specify how one adds edges to existing configurations, and choice, wherein one selects from a “limited” set of edges at random to use in the configuration. While an intense study of such models has ensued, understanding the actual emergence of the giant component and merging dynamics in the critical scaling window has remained impenetrable to a rigorous analysis. In this work we take an important step in the analysis of such models by studying one of the standard examples of such processes, namely the Bohman‐Frieze model, and provide first results on the asymptotic dynamics, through the critical scaling window, that lead to the emergence of the giant component for such models. We identify the scaling window and show that through this window, the component sizes properly rescaled converge to the standard multiplicative coalescent. Proofs hinge on a careful analysis of certain infinite‐type branching processes with types taking values in the space of cadlag paths, and stochastic analytic techniques to estimate susceptibility functions of the components all the way through the scaling window where these functions explode. Previous approaches for analyzing random graphs at criticality have relied largely on classical breadth‐first search techniques that exploit asymptotic connections with Brownian excursions. For dynamic random graph models evolving via general Markovian rules, such approaches fail and we develop a quite different set of tools that can potentially be used for the study of critical dynamics for all bounded size rules. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 55–116, 2015