Bootstrap percolation with inhibition

We study a variant of the classical bootstrap percolation process on Erd?s Rényi random graphs. The graphs we consider have inhibitory vertices obstructing the diffusion of activity and excitatory vertices facilitating it. We study both a synchronous and an asynchronous version of the process. Both begin with a small initial set of active vertices, and the activation spreads to all vertices for which the number of excitatory active neighbors exceeds the number of inhibitory active neighbors by a certain amount. We show that in the synchronous process, inhibitory vertices may cause unstable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. We further show that in the asynchronous model the process becomes stable and stops with an active set containing a nontrivial deterministic constant fraction of all vertices. Moreover, we show that percolation occurs significantly faster asynchronously than synchronously.     

A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least infected neighbours becomes infected and remains so forever. Assume that initially vertices are randomly infected, where is the total number of vertices of the graph. Suppose also that , where is the average degree. We determine a critical function such that when , complete infection occurs with high probability as , but when , then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to .     

Saturation in random graphs

A graph H is K_s ‐saturated if it is a maximal K_s ‐free graph, i.e., H contains no clique on s vertices, but the addition of any missing edge creates one. The minimum number of edges in a K_s ‐saturated graph was determined over 50 years ago by Zykov and independently by Erd?s, Hajnal and Moon. In this paper, we study the random analog of this problem: minimizing the number of edges in a maximal K_s ‐free subgraph of the Erd?s‐Rényi random graph G (n, p ). We give asymptotically tight estimates on this minimum, and also provide exact bounds for the related notion of weak saturation in random graphs. Our results reveal some surprising behavior of these parameters. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 169–181, 2017     

On connectivity,conductance and bootstrap percolation for a random k‐out,age‐biased graph

A uniform attachment graph (with parameter k), denoted G_n,k in the paper, is a random graph on the vertex set [n], where each vertex v makes k selections from [v ? 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of G_n,k to show that the conductance of G_n,k is of order . We also study the bootstrap percolation on G_n,k, where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set.     

First‐passage percolation on a ladder graph,and the path cost in a VCG auction

This paper studies the time constant for first‐passage percolation, and the Vickrey‐Clarke‐Groves (VCG) payment, for the shortest path on a ladder graph (a width‐2 strip) with random edge costs, treating both in a unified way based on recursive distributional equations. For first‐passage percolation where the edge costs are independent Bernoulli random variables we find the time constant exactly; it is a rational function of the Bernoulli parameter. For first‐passage percolation where the edge costs are uniform random variables we present a reasonably efficient means for obtaining arbitrarily close upper and lower bounds. Using properties of Harris chains we also show that the incremental cost to advance through the medium has a unique stationary distribution, and we compute stochastic lower and upper bounds. We rely on no special properties of the uniform distribution: the same methods could be applied to any well‐behaved, bounded cost distribution. For the VCG payment, with Bernoulli‐distributed costs the payment for an n‐long ladder, divided by n, tends to an explicit rational function of the Bernoulli parameter. Again, our methods apply more generally. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 350‐364, 2011     

Spread‐out percolation in ℝd

Fix d ≥ 2, and let X be either ℤ^d or the points of a Poisson process in ℝ^d of intensity 1. Given parameters r and p, join each pair of points of X within distance r independently with probability p. This is the simplest case of a “spread‐out” percolation model studied by Penrose [Ann Appl Probab 3 (1993) 253–276], who showed that, as r → ∞, the average degree of the corresponding random graph at the percolation threshold tends to 1, i.e., the percolation threshold and the threshold for criticality of the naturally associated branching process approach one another. Here we show that this result follows immediately from of a general result of [3] on inhomogeneous random graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Merging percolation on Zd and classical random graphs: Phase transition

We study a random graph model which is a superposition of bond percolation on Z^d with parameter p, and a classical random graph G(n,c/n). We show that this model, being a homogeneous random graph, has a natural relation to the so‐called “rank 1 case” of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the set of parameters c ≥ 0 and 0 ≤ p < p_c, where p_c = p_c(d) is the critical probability for the bond percolation on Z^d. The phase transition is of second order as in the classical random graph. We find the scaled size of the largest connected component in the supercritical regime. We also provide a sharp upper bound for the largest connected component in the subcritical regime. The latter is a new result for inhomogeneous random graphs with unbounded kernels. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Line percolation

We study a new geometric bootstrap percolation model, line percolation, on the d‐dimensional integer grid . In line percolation with infection parameter r, infection spreads from a subset of initially infected lattice points as follows: if there exists an axis‐parallel line L with r or more infected lattice points on it, then every lattice point of on L gets infected, and we repeat this until the infection can no longer spread. The elements of the set A are usually chosen independently, with some density p, and the main question is to determine , the density at which percolation (infection of the entire grid) becomes likely. In this paper, we determine up to a multiplicative factor of and up to a multiplicative constant as for every fixed . We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter.     

The cover time of the giant component of a random graph

We study the cover time of a random walk on the largest component of the random graph G_n,p. We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(lnn). In particular, we show that the cover time is not monotone for c = Θ(lnn). We also determine the cover time of the k‐cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Large‐deviations/thermodynamic approach to percolation on the complete graph

We present a large‐deviations/thermodynamic approach to the classic problem of percolation on the complete graph. Specifically, we determine the large‐deviation rate function for the probability that the giant component occupies a fixed fraction of the graph while all other components are “small.” One consequence is an immediate derivation of the “cavity” formula for the fraction of vertices in the giant component. As a byproduct of our analysis we compute the large‐deviation rate functions for the probability of the event that the random graph is connected, the event that it contains no cycles and the event that it contains only small components. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Critical percolation on random regular graphs

The behavior of the random graph G(n,p) around the critical probability p_c = is well understood. When p = (1 + O(n^1/3))p_c the components are roughly of size n^2/3 and converge, when scaled by n^?2/3, to excursion lengths of a Brownian motion with parabolic drift. In particular, in this regime, they are not concentrated. When p = (1 ‐ ?(n))p_c with ?(n)n^1/3 →∞ (the subcritical regime) the largest component is concentrated around 2?^?2 log(?³n). When p = (1 + ?(n))p_c with ?(n)n^1/3 →∞ (the supercritical regime), the largest component is concentrated around 2?n and a duality principle holds: other component sizes are distributed as in the subcritical regime. Itai Benjamini asked whether the same phenomenon occurs in a random d‐regular graph. Some results in this direction were obtained by (Pittel, Ann probab 36 (2008) 1359–1389). In this work, we give a complete affirmative answer, showing that the same limiting behavior (with suitable d dependent factors in the non‐critical regimes) extends to random d‐regular graphs. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

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.     

On the cycle space of a random graph

Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].     

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.     

Large deviation analysis for layered percolation problems on the complete graph

We analyze the large deviation properties for the (multitype) version of percolation on the complete graph – the simplest substitutive generalization of the Erd&0151;s‐Rènyi random graph that was treated in article by Bollobás et al. (Random Structures Algorithms 31 (2007), 3–122). Here the vertices of the graph are divided into a fixed finite number of sets (called layers) the probability of {u,v} being in our edge set depends on the respective layers of u and v. We determine the exponential rate function for the probability that a giant component occupies a fixed fraction of the graph, while all other components are small. We also determine the exponential rate function for the probability that a particular exploration process on the random graph will discover a certain fraction of vertices in each layer, without encountering a giant component.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 460–492, 2012     

Tight products and graph expansion

In this article, we study a new product of graphs called tight product. A graph H is said to be a tight product of two (undirected multi) graphs G₁ and G₂, if V(H) = V(G₁) × V(G₂) and both projection maps V(H)→V(G₁) and V(H)→V(G₂) are covering maps. It is not a priori clear when two given graphs have a tight product (in fact, it is NP‐hard to decide). We investigate the conditions under which this is possible. This perspective yields a new characterization of class‐1 (2k+ 1)‐regular graphs. We also obtain a new model of random d‐regular graphs whose second eigenvalue is almost surely at most O(d^3/4). This construction resembles random graph lifts, but requires fewer random bits. © 2011 Wiley Periodicals, Inc. J Graph Theory     

The order of the largest complete minor in a random graph

Let ccl(G) denote the order of the largest complete minor in a graph G (also called the contraction clique number) and let G_n,p denote a random graph on n vertices with edge probability p. Bollobás, Catlin, and Erd?s (Eur J Combin 1 (1980), 195–199) asymptotically determined ccl(G_n,p) when p is a constant. ?uczak, Pittel and Wierman (Trans Am Math Soc 341 (1994) 721–748) gave bounds on ccl(G_n,p) when p is very close to 1/n, i.e. inside the phase transition. We show that for every ε > 0 there exists a constant C such that whenever C/n < p < 1 ‐ ε then asymptotically almost surely ccl(G_n,p) = (1 ± ε)n/ , where b := 1/(1 ‐ p). If p = C/n for a constant C > 1, then ccl(G_n,p) = Θ( ). This extends the results in (Bollobás, Catlin, and P. Erd?s, Eur J Combin 1 (1980), 195–199) and answers a question of Krivelevich and Sudakov (preprint, 2006). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008