Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

We study random subgraphs of the n-cube {0,1}ⁿ, where nearest-neighbor edges are occupied with probability p. Let p_c(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value λ2^n/3, where λ is a small positive constant. Let ε=n(p−p_c(n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2^−n/3) is of size Θ(2^2n/3), below this scaling window it is at most 2(log 2)nε⁻², and above this scaling window it is at most O(ε2ⁿ). In this paper, we prove that for the size of the largest component is at least Θ(ε2ⁿ), which is of the same order as the upper bound. The proof is based on a method that has come to be known as “sprinkling,” and relies heavily on the specific geometry of the n-cube.     

Infinite paths in a Lorentz lattice gas model

We consider infinite paths in an illumination problem on the lattice ℤ², where at each vertex, there is either a two-sided mirror (with probability p≥ 0) or no mirror (with probability 1 −p). The mirrors are independently oriented NE-SW or NW-SE with equal probability. We consider beams of light which are shone from the origin and deflected by the mirrors. The beam of light is either periodic or unbounded. The novel feature of this analysis is that we concentrate on the measure on the space of paths. In particular, under the assumption that the set of unbounded paths has positive measure, we are able to establish a useful ergodic property of the measure. We use this to prove results about the number and geometry of infinite light beams. Extensions to higher dimensions are considered. Received: 14 November 1996 / Revised version: 1 September 1998     

Diffusive scaling of the spectral gap for the dilute Ising lattice-gas dynamics below the percolation threshold

We consider a conservative stochastic lattice-gas dynamics reversible with respect to the canonical Gibbs measure of the bond dilute Ising model on ℤ ^d at inverse temperature β. When the bond dilution density p is below the percolation threshold we prove that for any particle density and any β, with probability one, the spectral gap of the generator of the dyamics in a box of side L centered at the origin scales like L ⁻². Such an estimate is then used to prove a decay to equilibrium for local functions of the form where ε is positive and arbitrarily small and α = ? for d = 1, α=1 for d≥2. In particular our result shows that, contrary to what happes for the Glauber dynamics, there is no dynamical phase transition when β crosses the critical value β _c of the pure system. Received: 10 April 2000 / Revised version: 23 October 2000 / Published online: 5 June 2001     

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     

UNIFORM CONVERGENCE OF CESARO MEANS OF NEGATIVE ORDER OF DOUBLE TRIGONOMETRIC FOURIER SERIES

In this paper we prove that iff ∈ C([-π,π]2) and the function f is bounded partial p-variation for some p ∈ [1, ∞), then the double trigonometric Fourier series of a function f is uniformly (C;-α,-β) summable (α β＜ 1/p,α,β＞ 0) in the sense of Pringsheim. If α β≥ 1/p, then there exists a continuous function f0 of bounded partial double trigonometric Fourier series of fo diverge over cubes.     

A new inductive approach to the lace expansion for self-avoiding walks

Summary. We introduce a new inductive approach to the lace expansion, and apply it to prove Gaussian behaviour for the weakly self-avoiding walk on ℤ ^d where loops of length m are penalised by a factor e ^{−β/m p} (0<β≪1) when: (1) d>4, p≥0; (2) d≤4, . In particular, we derive results first obtained by Brydges and Spencer (and revisited by other authors) for the case d>4, p=0. In addition, we prove a local central limit theorem, with the exception of the case d>4, p=0. Received: 29 October 1997 / In revised form: 15 January 1998     

The asymmetric random cluster model and comparison of Ising and Potts models

We introduce the asymmetric random cluster (or ARC) model, which is a graphical representation of the Potts lattice gas, and establish its basic properties. The ARC model allows a rich variety of comparisons (in the FKG sense) between models with different parameter values; we give, for example, values (β, h) for which the 0‘s configuration in the Potts lattice gas is dominated by the “+” configuration of the (β, h) Ising model. The Potts model, with possibly an external field applied to one of the spins, is a special case of the Potts lattice gas, which allows our comparisons to yield rigorous bounds on the critical temperatures of Potts models. For example, we obtain 0.571 ≤ 1 − exp(−β _c ) ≤ 0.600 for the 9-state Potts model on the hexagonal lattice. Another comparison bounds the movement of the critical line when a small Potts interaction is added to a lattice gas which otherwise has only interparticle attraction. ARC models can also be compared to related models such as the partial FK model, obtained by deleting a fraction of the nonsingleton clusters from a realization of the Fortuin-Kasteleyn random cluster model. This comparison leads to bounds on the effects of small annealed site dilution on the critical temperature of the Potts model. Received: 27 August 2000 / Revised version: 31 August 2000 / Published online: 8 May 2001     

Estimates on path delocalization for copolymers at selective interfaces

Starting from the simple symmetric random walk {S_n}_n, we introduce a new process whose path measure is weighted by a factor exp with α,h≥0, {W_n}_n a typical realization of an IID process and N a positive integer. We are looking for results in the large N limit. This factor favors S_n>0 if W_n+h>0 and S_n<0 if W_n+h<0. The process can be interpreted as a model for a random heterogeneous polymer in the proximity of an interface separating two selective solvents. It has been shown [6] that this model undergoes a (de)localization transition: more precisely there exists a continuous increasing function λ↦h_c(λ) such that if h<h_c(λ) then the model is localized while it is delocalized if h≥h_c(λ). However, localization and delocalization were not given in terms of path properties, but in a free energy sense. Later on it has been shown that free energy localization does indeed correspond to a (strong) form of path localization [3]. On the other hand, only weak results on the delocalized regime have been known so far. We present a method, based on concentration bounds on suitably restricted partition functions, that yields much stronger results on the path behavior in the interior of the delocalized region, that is for h>h_c(λ). In particular we prove that, in a suitable sense, one cannot expect more than O( log N) visits of the walk to the lower half plane. The previously known bound was o(N). Stronger O(1)–type results are obtained deep inside the delocalized region. The same approach is also helpful for a different type of question: we prove in fact that the limit as α tends to zero of h_c(λ)/λ exists and it is independent of the law of ω₁, at least when the random variable ω₁ is bounded or it is Gaussian. This is achieved by interpolating between this class of variables and the particular case of ω₁ taking values ±1 with probability 1/2, treated in [6].     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

A large-deviation result for the range of random walk and for the Wiener sausage

Let {S _n } be a random walk on ℤ ^d and let R _n be the number of different points among 0, S ₁,…, S _{n −1}. We prove here that if d≥ 2, then ψ(x) := lim _{n →∞}(−:1/n) logP{R _n ≥nx} exists for x≥ 0 and establish some convexity and monotonicity properties of ψ(x). The one-dimensional case will be treated in a separate paper. We also prove a similar result for the Wiener sausage (with drift). Let B(t) be a d-dimensional Brownian motion with constant drift, and for a bounded set A⊂ℝ ^d let Λ _t = Λ _t (A) be the d-dimensional Lebesgue measure of the `sausage' ∪_{0≤ s ≤ t} (B(s) + A). Then φ(x) := lim _t→∞: (−1/t) log P{Λ _t ≥tx exists for x≥ 0 and has similar properties as ψ. Received: 20 April 2000 / Revised version: 1 September 2000 / Published online: 26 April 2001     

Phase transition of the principal Dirichlet eigenvalue in a scaled Poissonian potential

We consider d-dimensional Brownian motion in a scaled Poissonian potential and the principal Dirichlet eigenvalue (ground state energy) of the corresponding Schr?dinger operator. The scaling is chosen to be of critical order, i.e. it is determined by the typical size of large holes in the Poissonian cloud. We prove existence of a phase transition in dimensions d≥ 4: There exists a critical scaling constant for the potential. Below this constant the scaled infinite volume limit of the corresponding principal Dirichlet eigenvalue is linear in the scale. On the other hand, for large values of the scaling constant this limit is strictly smaller than the linear bound. For d > 4 we prove that this phase transition does not take place on that scale. Further we show that the analogous picture holds true for the partition sum of the underlying motion process. Received: 10 December 1999 / Revised version: 14 July 2000/?Published online: 15 February 2001     

<Emphasis Type="BoldItalic">π</Emphasis>-forms of Brauer’s <Emphasis Type="BoldItalic">k</Emphasis>(<Emphasis Type="BoldItalic">B</Emphasis>)—conjecture and Olsson’s Conjecture

Our main purpose of this paper is to give π-block forms of Brauer’s k(B) −conjecture and Olsson’s conjecture for finite π −separable groups.     

On the Constants in the Meyer Inequality

 We study the growth of the constants in the Meyer inequality as p → 1 and p → ∞. Both constants grow, within constant factors, like (p − 1)⁻¹ and like p respectively. Received August 10, 2001; in revised form February 5, 2002     

A Prime Sensitive Hankel Determinant of Jacobi Symbol Enumerators

We show that the determinant of a Hankel matrix of odd dimension n whose entries are the enumerators of the Jacobi symbols which depend on the row and the column indices vanishes if and only if n is composite. If the dimension is a prime p, then the determinant evaluates to a polynomial of degree p − 1 which is the product of a power of p and the generating polynomial of the partial sums of Legendre symbols. The sign of the determinant is determined by the quadratic character of −1 modulo p. The proof of the evaluation makes use of elementary properties of Legendre symbols, quadratic Gauss sums, and orthogonality of trigonometric functions.     

On counting twists of a character appearing in its associated Weil representation

Consider an irreducible, admissible representation π of GL(2,F) whose restriction to GL(2,F)⁺ breaks up as a sum of two irreducible representations π ₊ + π −. If π = r _θ , the Weil representation of GL(2,F) attached to a character θ of K ^* does not factor through the norm map from K to F, then c ? [^(K^*)]\chi\in \widehat{K^*} with (c. q^-1)| _{F ^*} =w _K/F(\chi . \theta ^{-1})\vert _{ F^{ * }}=\omega _{ {K/F}} occurs in r _{θ  +} if and only if e(qc^-1,y₀)=e([`(q)]c^-1,y₀)=1\epsilon(\theta\chi^{-1},\psi_0)=\epsilon(\overline \theta\chi^{-1},\psi_0)=1 and in r _θ− if and only if both the epsilon factors are − 1. But given a conductor n, can we say precisely how many such χ will appear in π? We calculate the number of such characters at each given conductor n in this work.     

Scaling identity for crossing Brownian motion in a Poissonian potential

We consider d-dimensional Brownian motion in a truncated Poissonian potential (d≥ 2). If Brownian motion starts at the origin and ends in the closed ball with center y and radius 1, then the transverse fluctuation of the path is expected to be of order |y|^ξ, whereas the distance fluctuation is of order |y|^χ. Physics literature tells us that ξ and χ should satisfy a scaling identity 2ξ− 1 = χ. We give here rigorous results for this conjecture. Received: 31 December 1997 / Revised version: 14 April 1998     

Monotonicity of uniqueness for percolation on Cayley graphs: all infinite clusters are born simultaneously

. Consider site or bond percolation with retention parameter p on an infinite Cayley graph. In response to questions raised by Grimmett and Newman (1990) and Benjamini and Schramm (1996), we show that the property of having (almost surely) a unique infinite open cluster is increasing in p. Moreover, in the standard coupling of the percolation models for all parameters, a.s. for all p ₂>p ₁>p _c , each infinite p ₂-cluster contains an infinite p ₁-cluster; this yields an extension of Alexander's (1995) “simultaneous uniqueness” theorem. As a corollary, we obtain that the probability θ _v (p) that a given vertex v belongs to an infinite cluster is depends continuously on p throughout the supercritical phase p>p _c . All our results extend to quasi-transitive infinite graphs with a unimodular automorphism group. Received: 22 December 1997 / Revised version: 1 July 1998     

Besov spaces andK-functionals inL p, 0<p<1*

We investigate Besov spaces and their connection with trigonometric polynomial approximation inL _p[−π,π], algebraic polynomial approximation inL _p[−1,1], algebraic polynomial approximation inL _p(S), and entire function of exponential type approximation inL _p(R), and characterizeK-functionals for certain pairs of function spaces including (L _p[−π,π],B _s ^a(L _p[−π,π])), (L _p(R),_s ^a(L_p(R))), , and , where 0<s≤∞, 0<p<1,S is a simple polytope and 0<α<r. This project is supported by the National Science Foundation of China.     

The nearness problems for symmetric centrosymmetric with a special submatrix constraint

We say that X=[x_ij]_i,j=1ⁿX=[x_{ij}]_{i,j=1}^n is symmetric centrosymmetric if x _ij  = x _ji and x _{n − j + 1,n − i + 1}, 1 ≤ i,j ≤ n. In this paper we present an efficient algorithm for minimizing ||AXA ^T  − B|| where ||·|| is the Frobenius norm, A ∈ ℝ ^m×n , B ∈ ℝ ^m×m and X ∈ ℝ ^n×n is symmetric centrosymmetric with a specified central submatrix [x _ij ] _{p ≤ i,j ≤ n − p} . Our algorithm produces a suitable X such that AXA ^T  = B in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

Structure of <Emphasis Type="Italic">K</Emphasis>-interval exchange transformations: Induction,trajectories, and distance theorems

We define a new induction algorithm for k-interval exchange transformations associated to the “symmetric” permutation i ↦ k − i + 1. Acting as a multi-dimensional continued fraction algorithm, it defines a sequence of generalized partial quotients given by an infinite path in a graph whose vertices, or states, are certain trees we call trees of relations. This induction is self-dual for the duality between the usual Rauzy induction and the da Rocha induction. We use it to describe those words obtained by coding orbits of points under a symmetric interval exchange, in terms of the generalized partial quotients associated with the vector of lengths of the k intervals. As a consequence, we improve a bound of Boshernitzan in a generalization of the three-distances theorem for rotations. However, a variant of our algorithm, applied to a class of interval exchange transformations with a different permutation, shows that the former bound is optimal outside the hyperelliptic class of permutations.