The number of infinite clusters in dynamical percolation

Summary. Dynamical percolation is a Markov process on the space of subgraphs of a given graph, that has the usual percolation measure as its stationary distribution. In previous work with O. H?ggstr?m, we found conditions for existence of infinite clusters at exceptional times. Here we show that for ℤ ^d , with p>p _c , a.s. simultaneously for all times there is a unique infinite cluster, and the density of this cluster is θ(p). For dynamical percolation on a general tree Γ, we show that for p>p _c , a.s. there are infinitely many infinite clusters at all times. At the critical value p=p _c , the number of infinite clusters may vary, and exhibits surprisingly rich behaviour. For spherically symmetric trees, we find the Hausdorff dimension of the set T ^k of times where the number of infinite clusters is k, and obtain sharp capacity criteria for a given time set to intersect T ^k . The proof of this capacity criterion is based on a new kernel truncation technique. Received: 5 May 1997 / In revised form: 24 November 1997     

Asymptotic behavior of the critical probability for ρ-percolation in high dimensions

We consider oriented bond or site percolation on ℤ ^d ₊. In the case of bond percolation we denote by P _p the probability measure on configurations of open and closed bonds which makes all bonds of ℤ ^d ₊ independent, and for which P _p {e is open} = 1 −P _p e {is closed} = p for each fixed edge e of ℤ ^d ₊. We take X(e) = 1 (0) if e is open (respectively, closed). We say that ρ-percolation occurs for some given 0 < ρ≤ 1, if there exists an oriented infinite path v ₀ = 0, v ₁, v ₂, …, starting at the origin, such that lim inf _{n →∞} (1/n) ∑ _i=1 ⁿ X(e _i ) ≥ρ, where e _i is the edge {v _i−1 , v _i }. [MZ92] showed that there exists a critical probability p _c = p _c (ρ, d) = p _c (ρ, d, bond) such that there is a.s. no ρ-percolation for p < p _c and that P _p {ρ-percolation occurs} > 0 for p > p _c . Here we find lim _{d →∞} d ^1/ρ p _c (ρd, bond) = D ₁ , say. We also find the limit for the analogous quantity for site percolation, that is D ₂ = lim _{d →∞} d ^1/ρ p _c (ρ, d, site). It turns out that for ρ < 1, D ₁ < D ₂ , and neither of these limits equals the analogous limit for the regular d-ary trees. Received: 7 January 1999 / Published online: 14 June 2000     

Linear lower bounds for δc(p) for a class of 2D self‐destructive percolation models

The self‐destructive percolation model is defined as follows: Consider percolation with parameter p > p_c. Remove the infinite occupied cluster. Finally, give each vertex (or, for bond percolation, each edge) that at this stage is vacant, an extra chance δ to become occupied. Let δ_c(p) be the minimal value of δ, needed to obtain an infinite occupied cluster in the final configuration. This model was introduced by van den Berg and Brouwer. They showed, for the site model on the square lattice (and a few other 2D lattices satisfying a special technical condition) that δ_c(p) ≥ . In particular, δ_c(p) is at least linear in p ? p_c. Although the arguments used by van den Berg and Brouwer look very lattice‐specific, we show that they can be suitably modified to obtain similar linear lower bounds for δ_c(p) (with p near p_c) for a much larger class of 2D lattices, including bond percolation on the square and triangular lattices, and site percolation on the star lattice (or matching lattice) of the square lattice. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Energy of flows on Z2 percolation clusters

We show that if p>p_c( Z ²), then the unique infinite percolation cluster supports a nonzero flow f with finite q energy for all q>2. This extends the work of Grimmett, Kesten, and Zhang (Probab Th. Relat Fields 96 (1993), 33–44) and Levin and Peres (Preprint, 1998) in dimensions d≥3. As an application of our techniques we exhibit a graph that has transient percolation clusters, but does not admit exponential intersection tails. This answers a question asked by Benjamini, Pemantle, and Peres (Ann Probab.) 26(3) (1998) 1198–1211. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 143–155, 2000     

On the multiplier conjecture

The Multiplier Theorem is a celebrated theorem in the Design theory. The conditionp>λ is crucial to all known proofs of the multiplier theorem. However in all known examples of difference sets μ _p . is a multiplier for every primep with (p, v)=1 andp‖n. Thus there is the multiplier conjecture: “The multiplier theorem holds without the assumption thatp>λ”. The general form of the multiplier theorem may be viewed as an attempt to partially resolve the multiplier conjecture, where the assumption “p>λ” is replaced by “n ₁>λ”. Since then Newman (1963), Turyn (1964), and McFarland (1970) attempted to partially resolve the multiplier conjecture (see [7], [8], [9]). This paper will prove the following result using the representation theory of finite groups and the algebraic number theory: LetG be an abelian group of orderv,v ₀ be the exponent ofG, andD be a (v, k, λ)-difference set inG. Ifn=2_{n 1}, then the general form of the multiplier theorem holds without the assumption thatn ₁>λ in any of the following cases:

Stability of infinite clusters in supercritical percolation

. A recent theorem by Häggström and Peres concerning independent percolation is extended to all the quasi-transitive graphs. This theorem states that if 0<p ₁<p ₂≤1 and percolation occurs at level p ₁, then every infinite cluster at level p ₂ contains some infinite cluster at level p ₁. Consequences are the continuity of the percolation probability above the percolation threshold and the monotonicity of the uniqueness of the infinite cluster, i.e., if at level p ₁ there is a unique infinite cluster then the same holds at level p ₂. These results are further generalized to graphs with a “uniform percolation” property. The threshold for uniqueness of the infinite cluster is characterized in terms of connectivities between large balls.     

An extension of Hawkes theorem on the Hausdorff dimension of a Galton–Watson tree

Let ? be the genealogical tree of a supercritical multitype Galton–Watson process, and let Λ be the limit set of ?, i.e., the set of all infinite self-avoiding paths (called ends) through ? that begin at a vertex of the first generation. The limit set Λ is endowed with the metric d(ζ, ξ) = 2 ⁻ⁿ where n = n(ζ, ξ) is the index of the first generation where ζ and ξ differ. To each end ζ is associated the infinite sequence Φ(ζ) of types of the vertices of ζ. Let Ω be the space of all such sequences. For any ergodic, shift-invariant probability measure μ on Ω, define Ω_μ to be the set of all μ-generic sequences, i.e., the set of all sequences ω such that each finite sequence v occurs in ω with limiting frequency μ(Ω(v)), where Ω(v) is the set of all ω′?Ω that begin with the word v. Then the Hausdorff dimension of Λ∩Φ⁻¹ (Ω_μ) in the metric d is

The game for the speed of convergence in repeated games of incomplete information

We consider an infinitely repeated two-person zero-sum game with incomplete information on one side, in which the maximizer is the (more) informed player. Such games have value v _∞ (p) for all 0≤p≤1. The informed player can guarantee that all along the game the average payoff per stage will be greater than or equal to v _∞ (p) (and will converge from above to v _∞ (p) if the minimizer plays optimally). Thus there is a conflict of interest between the two players as to the speed of convergence of the average payoffs-to the value v _∞ (p). In the context of such repeated games, we define a game for the speed of convergence, denoted SG _∞ (p), and a value for this game. We prove that the value exists for games with the highest error term, i.e., games in which v _n (p)− v _∞ (p) is of the order of magnitude of . In that case the value of SG _∞ (p) is of the order of magnitude of . We then show a class of games for which the value does not exist. Given any infinite martingale 𝔛^∞={X _k }^∞ _k=1, one defines for each n : V _n (𝔛^∞) ≔E∑ⁿ _k=1 |X _k+1 − X _k|. For our first result we prove that for a uniformly bounded, infinite martingale 𝔛^∞, V _n (𝔛^∞) can be of the order of magnitude of n ^1/2−ε, for arbitrarily small ε>0. Received January 1999/Final version April 2002     

The Alexander-Orbach conjecture holds in high dimensions

We examine the incipient infinite cluster (IIC) of critical percolation in regimes where mean-field behavior has been established, namely when the dimension d is large enough or when d>6 and the lattice is sufficiently spread out. We find that random walk on the IIC exhibits anomalous diffusion with the spectral dimension d_s=\frac43d_{s}=\frac{4}{3} , that is, p _t (x,x)=t ^−2/3+o(1). This establishes a conjecture of Alexander and Orbach (J. Phys. Lett. (Paris) 43:625–631, 1982). En route we calculate the one-arm exponent with respect to the intrinsic distance.     

Dependent percolation in two dimensions

For a natural number k, define an oriented site percolation on ℤ² as follows. Let x _i , y _j be independent random variables with values uniformly distributed in {1, …, k}. Declare a site (i, j) ∈ℤ² closed if x _i = y _j , and open otherwise. Peter Winkler conjectured some years ago that if k≥ 4 then with positive probability there is an infinite oriented path starting at the origin, all of whose sites are open. I.e., there is an infinite path P = (i ₀, j ₀)(i ₁, j ₁) · · · such that 0 = i ₀≤i ₁≤· · ·, 0 = j ₀≤j ₁≤· · ·, and each site (i _n , j _n ) is open. Rather surprisingly, this conjecture is still open: in fact, it is not known whether the conjecture holds for any value of k. In this note, we shall prove the weaker result that the corresponding assertion holds in the unoriented case: if k≤ 4 then the probability that there is an infinite path that starts at the origin and consists only of open sites is positive. Furthermore, we shall show that our method can be applied to a wide variety of distributions of (x _i ) and (y _j ). Independently, Peter Winkler [14] has recently proved a variety of similar assertions by different methods. Received: 4 March 1999 / Revised version: 27 September 1999 / Published online: 21 June 2000     

Koszul homology and syzygies of Veronese subalgebras

A graded K-algebra R has property N _p if it is generated in degree 1, has relations in degree 2 and the syzygies of order ≤ p on the relations are linear. The Green–Lazarsfeld index of R is the largest p such that it satisfies the property N _p . Our main results assert that (under a mild assumption on the base field) the cth Veronese subring of a polynomial ring has Green–Lazarsfeld index ≥ c + 1. The same conclusion also holds for an arbitrary standard graded algebra, provided c >> 0{c\gg 0}.     

On embedding expanders into ℓ p spaces

In this note we show that the minimum distortion required to embed alln-point metric spaces into the Banach space ℓ _p is between (c ₁/p) logn and (c ₂/p) logn, wherec ₂>c ₁>0 are absolute constants and 1≤p<logn. The lower bound is obtained by a generalization of a method of Linial et al. [LLR95], by showing that constant-degree expanders (considered as metric spaces) cannot be embedded any better. Research supported by Czech Republic Grant GAČR 201/94/2167 and Charles University grants No. 351 and 361.     

On the mixing time of a simple random walk on the super critical percolation cluster

 We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in Z ^d . We show that for d≥2 and p>p _c (Z ^d ), the mixing time of simple random walk on the largest cluster inside is Θ(n ² ) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance method. This is the first non-trivial application of this method which yields a tight result. Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002     

Supercritical biharmonic equations with power-type nonlinearity

We study two different versions of a supercritical biharmonic equation with a power-type nonlinearity. First, we focus on the equation Δ² u = |u| ^p-1 u over the whole space , where n > 4 and p > (n + 4)/(n − 4). Assuming that p < p _c, where p _c is a further critical exponent, we show that all regular radial solutions oscillate around an explicit singular radial solution. As it was already known, on the other hand, no such oscillations occur in the remaining case p ≥ p _c. We also study the Dirichlet problem for the equation Δ² u = λ (1 + u) ^p over the unit ball in , where λ > 0 is an eigenvalue parameter, while n > 4 and p > (n + 4)/(n − 4) as before. When it comes to the extremal solution associated to this eigenvalue problem, we show that it is regular as long as p < p _c. Finally, we show that a singular solution exists for some appropriate λ > 0.      

Further Results on the Existence of Splitting BIBDs and Application to Authentication Codes

Let (v,u×c,λ)-splitting BIBD denote a (v,u×c,λ)-splitting balanced incomplete block design of order v with block size u×c and index λ. Necessary conditions for the existence of a (v,u×c,λ)-splitting BIBD are v≥uc, λ(v−1)≡0 (mod c(u−1)) and λ v(v−1)≡0 (mod (c ² u(u−1))). We show in this paper that the necessary conditions for the existence of a (v,3×3,λ)-splitting BIBD are also sufficient with possible exceptions when (1) (v,λ)∈{(55,1),(39,9k):k=1,2,…}, (2) λ≡0 (mod 54) and v≡0 (mod 2). We also show that there exists a (v,3×4,1)-splitting BIBD when v≡1 (mod 96). As its application, we obtain a new infinite class of optimal 4-splitting authentication codes.     

The critical probability for random Voronoi percolation in the plane is 1/2

We study percolation in the following random environment: let Z be a Poisson process of constant intensity on ℝ², and form the Voronoi tessellation of ℝ² with respect to Z. Colour each Voronoi cell black with probability p, independently of the other cells. We show that the critical probability is 1/2. More precisely, if p>1/2 then the union of the black cells contains an infinite component with probability 1, while if p<1/2 then the distribution of the size of the component of black cells containing a given point decays exponentially. These results are analogous to Kesten's results for bond percolation in ℤ². The result corresponding to Harris' Theorem for bond percolation in ℤ² is known: Zvavitch noted that one of the many proofs of this result can easily be adapted to the random Voronoi setting. For Kesten's results, none of the existing proofs seems to adapt. The methods used here also give a new and very simple proof of Kesten's Theorem for ℤ²; we hope they will be applicable in other contexts as well. Research supported in part by NSF grant ITR 0225610 and DARPA grant F33615-01-C-1900 Research partially undertaken during a visit to the Forschungsinstitut für Mathematik, ETH Zürich, Switzerland     

On critical Fujita exponents for heat equations with nonlinear flux conditions on the boundary

We consider nonnegative solutions of initial-boundary value problems for parabolic equationsu _t=u_xx, u_t=(u^m)_xxand (m>1) forx>0,t>0 with nonlinear boundary conditions−u _x=u^p,−(u ^m)_x=u^pand forx=0,t>0, wherep>0. The initial function is assumed to be bounded, smooth and to have, in the latter two cases, compact support. We prove that for each problem there exist positive critical valuesp ₀,p_c(withp ₀<p_c)such that forp∃(0,p ₀],all solutions are global while forp∃(p₀,p_c] any solutionu≢0 blows up in a finite time and forp>p _csmall data solutions exist globally in time while large data solutions are nonglobal. We havep _c=2,p _c=m+1 andp _c=2m for each problem, whilep ₀=1,p ₀=1/2(m+1) andp ₀=2m/(m+1) respectively. This work was done during visits of the first author to Iowa State University and the Institute for Mathematics and its Applications at the University of Minnesota. The second author was supported in part by NSF Grant DMS-9102210.     

Random subgraphs of finite graphs: I. The scaling window under the triangle condition

We study random subgraphs of an arbitrary finite connected transitive graph ?? obtained by independently deleting edges with probability 1 ? p. Let V be the number of vertices in ??, and let Ω be their degree. We define the critical threshold p_c = p_c (??, λ) to be the value of p for which the expected cluster size of a fixed vertex attains the value λV^1/3, where λ is fixed and positive. We show that, for any such model, there is a phase transition at p_c analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold p_c. In particular, we show that the largest cluster inside a scaling window of size |p ? p_c| = Θ(Ω^?1V^?1/3) is of size Θ(V^2/3), while, below this scaling window, it is much smaller, of order O(?^?2 log(V?³)), with ? = Ω(p_c ? p). We also obtain an upper bound O(Ω(p ? p_c)V) for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order Θ(Ω(p ? p_c)). Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the n‐cube and certain Hamming cubes, as well as the spread‐out n‐dimensional torus for n > 6. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Exact and explicit analytic solutions of an extended Jabotinsky functional differential equation

A Banach space X will be called extensible if every operator E → X from a subspace E ⊂ X can be extended to an operator X → X. Denote by dens X. The smallest cardinal of a subset of X whose linear span is dense in X, the space X will be called automorphic when for every subspace E ⊂ X every into isomorphism T: E → X for which dens X/E = dens X/TE can be extended to an automorphism X → X. Lindenstrauss and Rosenthal proved that c ₀ is automorphic and conjectured that c ₀ and ℓ₂ are the only separable automorphic spaces. Moreover, they ask about the extensible or automorphic character of c ₀(Γ), for Γ uncountable. That c ₀(Γ) is extensible was proved by Johnson and Zippin, and we prove here that it is automorphic and that, moreover, every automorphic space is extensible while the converse fails. We then study the local structure of extensible spaces, showing in particular that an infinite dimensional extensible space cannot contain uniformly complemented copies of ℓ _n ^p , 1 ≤ p < ∞, p ≠ 2. We derive that infinite dimensional spaces such as L _p (μ), p ≠ 2, C(K) spaces not isomorphic to c ₀ for K metric compact, subspaces of c ₀ which are not isomorphic to c ₀, the Gurarij space, Tsirelson spaces or the Argyros-Deliyanni HI space cannot be automorphic. The work of the first author has been supported in part by project MTM2004-02635     

Cp

The spacec _p is the class of operators on a Hilbert space for which thec _p norm |T| _p =[trace(T*T) ^p/2]^1/p is finite. We prove many of the known results concerningc _p in an elementary fashion, together with the result (new for 1<p<2) thatc _p is as uniformly convex a Banach space asl _p. In spite of the remarkable parallel of norm inequalities in the spacesc _p andl _p, we show thatp ≠ 2, noc _p built on an infinite dimensional Hilbert space is equivalent to any subspace of anyl _p orL _p space. The author was supported by National Science Foundation Grant GP-5707.