The critical probability for confetti percolation equals 1/2

In the confetti percolation model, or two‐coloured dead leaves model, radius one disks arrive on the plane according to a space‐time Poisson process. Each disk is coloured black with probability p and white with probability . In this paper we show that the critical probability for confetti percolation equals 1/2. That is, if p > 1/2 then a.s. there is an unbounded curve in the plane all of whose points are black; while if then a.s. all connected components of the set of black points are bounded. This answers a question of Benjamini and Schramm [1]. The proof builds on earlier work by Hirsch [7] and makes use of an adaptation of a sharp thresholds result of Bourgain. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 679–697, 2017     

Sharp asymptotic for the chemical distance in long‐range percolation

We consider instances of long‐range percolation on and , where points at distance r get connected by an edge with probability proportional to r^?s, for s ∈ (d,2d), and study the asymptotic of the graph‐theoretical (a.k.a. chemical) distance D(x,y) between x and y in the limit as |x ? y|→∞. For the model on we show that, in probability as |x|→∞, the distance D(0,x) is squeezed between two positive multiples of , where for γ: = s/(2d). For the model on we show that D(0,xr) is, in probability as r→∞ for any nonzero , asymptotic to for φ a positive, continuous (deterministic) function obeying φ(r^γ) = φ(r) for all r > 1. The proof of the asymptotic scaling is based on a subadditive argument along a continuum of doubly‐exponential sequences of scales. The results strengthen considerably the conclusions obtained earlier by the first author. Still, significant open questions remain.     

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     

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     

Self‐destructive percolation as a limit of forest‐fire models on regular rooted trees

Let T be a regular rooted tree. For every natural number n, let T_n be the finite subtree of vertices with graph distance at most n from the root. Consider the following forest‐fire model on T_n: Each vertex can be “vacant” or “occupied”. At time 0 all vertices are vacant. Then the process is governed by two opposing mechanisms: Vertices become occupied at rate 1, independently for all vertices. Independently thereof and independently for all vertices, “lightning” hits vertices at rate λ(n) > 0. When a vertex is hit by lightning, its occupied cluster becomes vacant instantaneously. Now suppose that λ(n) decays exponentially in n but much more slowly than 1/|T_n|, where |T_n| denotes the number of vertices of T_n. We show that then there exist such that between time 0 and time the forest‐fire model on T_n tends to the following process on T as n goes to infinity: At time 0 all vertices are vacant. Between time 0 and time τ vertices become occupied at rate 1, independently for all vertices. Immediately before time τ there are infinitely many infinite occupied clusters. At time τ all these clusters become vacant. Between time τ and time vertices again become occupied at rate 1, independently for all vertices. At time all occupied clusters are finite. This process is a dynamic version of self‐destructive percolation. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 86–113, 2017     

On percolation and ‐hardness

The edge‐percolation and vertex‐percolation random graph models start with an arbitrary graph G, and randomly delete edges or vertices of G with some fixed probability. We study the computational complexity of problems whose inputs are obtained by applying percolation to worst‐case instances. Specifically, we show that a number of classical ‐hard problems on graphs remain essentially as hard on percolated instances as they are in the worst‐case (assuming ). We also prove hardness results for other ‐hard problems such as Constraint Satisfaction Problems and Subset‐Sum, with suitable definitions of random deletions. Along the way, we establish that for any given graph G the independence number and the chromatic number are robust to percolation in the following sense. Given a graph G, let be the graph obtained by randomly deleting edges of G with some probability . We show that if is small, then remains small with probability at least 0.99. Similarly, we show that if is large, then remains large with probability at least 0.99. We believe these results are of independent interest.     

Cardy's formula for some dependent percolation models

We prove Cardy's formula for rectangular crossing probabilities in dependent site percolation models that arise from a deterministic cellular automaton with a random initial state. The cellular automaton corresponds to the zero-temperature case of Domany's stochastic Ising ferromagnet on the hexagonal lattice  (with alternating updates of two sublattices) [7]; it may also be realized on the triangular lattice 𝕋 with flips when a site disagrees with six, five and sometimes four of its six neighbors. Received: 24 December 2001     

Ambarzumyan‐type theorem with polynomially dependent eigenparameter

In this paper, we are concerned with the inverse Sturm–Liouville problem with polynomially dependent eigenparameter in discontinuity and boundary conditions. By using a self‐adjoint operator‐theoretic interpretation for this sort of problem, Ambarzumyan theorem is provided for the mentioned Sturm–Liouville operator. Copyright © 2014 John Wiley & Sons, Ltd.     

A Liouville theorem for the compressible Navier‐Stokes equations

This paper is concerned with 3‐dimensional steady compressible Navier‐Stokes equations. A Liouville‐type theorem is proved when some suitable conditions are satisfied.     

An unknotting theorem for delta and sharp edge‐homotopy

Two spatial embeddings of a graph are said to be delta (resp. sharp) edge‐homotopic if they are transformed into each other by self delta (resp. sharp) moves and ambient isotopies. We show that any two spatial embeddings of a graph are delta (resp. sharp) edge‐homotopic if and only if the graph does not contain a subgraph which is homeomorphic to the theta graph or the disjoint union of two 1‐spheres, or equivalently G is homeomorphic to a bouquet. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Asymptotics in percolation on high‐girth expanders

We consider supercritical bond percolation on a family of high‐girth ‐regular expanders. The previous study of Alon, Benjamini and Stacey established that its critical probability for the appearance of a linear‐sized (“giant”) component is . Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant and its 2‐core at any . It was further shown in the previous study that the second largest component, at any , has size at most for some . We show that, unlike the situation in the classical Erd?s‐Rényi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size for arbitrarily close to 1. Moreover, as a by‐product of that construction, we answer negatively a question of Benjamini on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, for example, the existence of a linear path.     

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.     

Self-normalized central limit theorem for sums of weakly dependent random variables

Let {X _n,n1} be a strictly stationary sequence of weakly dependent random variables satisfyingEX _n=,EX _n ² <,Var S _n /n² and the central limit theorem. This paper presents two estimators of ². Their weak and strong consistence as well as their rate of convergence are obtained for -mixing, -mixing and associated sequences.Supported by a NSF grant and a Taft travel grant. Department of Mathematical Sciences, University of Cincinnati, Cincinnati, Ohio 45221-0025.Supported by a Taft Post-doctoral Fellowship at the University of Cincinnati and by the Fok Yingtung Education Foundation of China. Hangzhou University, Hangzhou, Zhejiang, P.R. China and Department of Mathematics, National University of Singapore, Singapore 0511.     

Liouville‐type theorem for the steady compressible Hall‐MHD system

In this paper, we prove a Liouville‐type theorem for the steady compressible Hall‐magnetohydrodynamics system in Π, where Π is whole space or half space . We show that a smooth solution (ρ, u , B ,P) satisfying 1/C₀<ρ<C₀, , and B ∈L^9/2(Π) for some constant C₀>0 is indeed trivial. This generalizes and improves 2 results of Chae.     

A unified proof of Brooks’ theorem and Catlin’s theorem

Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d$d$ be an integer at least 3, and let G$G$ be a graph with maximum degree d$d$. If G$G$ does not contain _Kd+1$K_{d+1}$ as a subgraph, then G$G$ has a d$d$-coloring in which one color class has size α(G)$\alpha \left(G\right)$. Here α(G)$\alpha \left(G\right)$ denotes the independence number of G$G$. We give a unified proof of Brooks’ theorem and Catlin’s theorem.     

Information percolation and cutoff for the random‐cluster model

We consider the random‐cluster model (RCM) on with parameters p∈(0,1) and q ≥ 1. This is a generalization of the standard bond percolation (with edges open independently with probability p) which is biased by a factor q raised to the number of connected components. We study the well‐known Fortuin‐Kasteleyn (FK)‐dynamics on this model where the update at an edge depends on the global geometry of the system unlike the Glauber heat‐bath dynamics for spin systems, and prove that for all small enough p (depending on the dimension) and any q>1, the FK‐dynamics exhibits the cutoff phenomenon at with a window size , where λ_∞ is the large n limit of the spectral gap of the process. Our proof extends the information percolation framework of Lubetzky and Sly to the RCM and also relies on the arguments of Blanca and Sinclair who proved a sharp mixing time bound for the planar version. A key aspect of our proof is the analysis of the effect of a sequence of dependent (across time) Bernoulli percolations extracted from the graphical construction of the dynamics, on how information propagates.     

Mantel's theorem for random graphs

For a graph G, denote by t(G) (resp. b(G)) the maximum size of a triangle‐free (resp. bipartite) subgraph of G. Of course for any G, and a classic result of Mantel from 1907 (the first case of Turán's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e., for what p = p(n)) is the “Erd?s‐Rényi” random graph G = G(n,p) likely to satisfy t(G) = b(G)? We show that this is true if for a suitable constant C, which is best possible up to the value of C. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 59–72, 2015     

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     

A Sharp Threshold for k‐Colorability

Let k be a fixed integer and f_k(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists d_k(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999     

A constructive proof of the Peter‐Weyl theorem

We present a new and constructive proof of the Peter‐Weyl theorem on the representations of compact groups. We use the Gelfand representation theorem for commutative C*‐algebras to give a proof which may be seen as a direct generalization of Burnside's algorithm [3]. This algorithm computes the characters of a finite group. We use this proof as a basis for a constructive proof in the style of Bishop. In fact, the present theory of compact groups may be seen as a natural continuation in the line of Bishop's work on locally compact, but Abelian, groups [2]. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)