Reconstructing a random scenery observed with random errors along a random walk path

 We show that an i.i.d. uniformly colored scenery on ℤ observed along a random walk path with bounded jumps can still be reconstructed if there are some errors in the observations. We assume the random walk is recurrent and can reach every point with positive probability. At time k, the random walker observes the color at her present location with probability 1−δ and an error Y _k with probability δ. The errors Y _k , k≥0, are assumed to be stationary and ergodic and independent of scenery and random walk. If the number of colors is strictly larger than the number of possible jumps for the random walk and δ is sufficiently small, then almost all sceneries can be almost surely reconstructed up to translations and reflections. Received: 3 February 2002 / Revised version: 15 January 2003 Published online: 28 March 2003 Mathematics Subject Classification (2000): 60K37, 60G50 Key words or phrases:Scenery reconstruction – Random walk – Coin tossing problems     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

On the Nonexistence of <Emphasis Type="Italic">k</Emphasis>-reptile Tetrahedra

A d-dimensional simplex S is called a k-reptile if it can be tiled without overlaps by simplices S ₁,S ₂,…,S _k that are all mutually congruent, and similar to S. For d=2, k-reptile simplices (triangles) exist for many values of k, and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, for d≥3, only one construction of k-reptile simplices is known, the Hill simplices, and it provides only k of the form m ^d , m=2,3,….     

Weak convergence to fractional Brownian motion in Brownian scenery

 Kesten and Spitzer have shown that certain random walks in random sceneries converge to stable processes in random sceneries. In this paper, we consider certain random walks in sceneries defined using stationary Gaussian sequence, and show their convergence towards a certain self-similar process that we call fractional Brownian motion in Brownian scenery. Received: 17 April 2002 / Revised version: 11 October 2002 / Published online: 15 April 2003 Research supported by NSFC (10131040). Mathematics Subject Classification (2002): 60J55, 60J15, 60J65 Key words or phrases: Weak convergence – Random walk in random scenery – Local time – Fractional Brownian motion in Brownian scenery     

Enhanced interface repulsion from quenched hard–wall randomness

 We consider the harmonic crystal, or massless free field, , , that is the centered Gaussian field with covariance given by the Green function of the simple random walk on ℤ ^d . Our main aim is to obtain quantitative information on the repulsion phenomenon that arises when we condition to be larger than , is an IID field (which is also independent of ϕ), for every x in a large region , with N a positive integer and D a bounded subset of ℝ ^d . We are mostly motivated by results for given typical realizations of σ (quenched set–up), since the conditioned harmonic crystal may be seen as a model for an equilibrium interface, living in a (d+1)–dimensional space, constrained not to go below an inhomogeneous substrate that acts as a hard wall. We consider various types of substrate and we observe that the interface is pushed away from the wall much more than in the case of a flat wall as soon as the upward tail of σ ₀ is heavier than Gaussian, while essentially no effect is observed if the tail is sub–Gaussian. In the critical case, that is the one of approximately Gaussian tail, the interplay of the two sources of randomness, ϕ and σ, leads to an enhanced repulsion effect of additive type. This generalizes work done in the case of a flat wall and also in our case the crucial estimates are optimal Large Deviation type asymptotics as of the probability that ϕ lies above σ in D _N . Received: 6 February 2002 / Revised version: 23 May 2002 / Published online: 30 September 2002 Mathematics Subject Classification (2000): 82B24, 60K35, 60G15 Keywords or phrases: Harmonic Crystal – Rough Substrate – Quenched and Annealed Models – Entropic Repulsion – Gaussian fields – Extrema of Random Fields – Large Deviations – Random Walks     

On the equationx(x +d 1)…(x + (k - 1)d 1) =y(y +d 2)…(y + (mk - 1)d 2)

For given positive integersm ≥ 2,d ₁ andd ₂, we consider the equation of the title in positive integersx, y andk ≥ 2. We show that the equation implies thatk is bounded. For a fixedk, we give conditions under which the equation implies that max(x, y) is bounded. Dedicated to the memory of Professor K G Ramanathan     

Modular curves and bases for the spaces of cuspidal modular forms

Let Γ⊂SL ₂(ℝ) be a Fuchsian group of the first kind. For a character χ of Γ→ℂ^× of finite order, we define the usual space S _m (Γ,χ) of cuspidal modular forms of weight m≥0. For each ξ in the upper half–plane and m≥3, we construct cuspidal modular forms Δ _k,m,ξ,χ ∈S _m (Γ,χ) (k≥0) which represent the linear functionals f?\fracd^kfdz^k|_z=xf\mapsto\frac{d^{k}f}{dz^{k}}|_{z=\xi} in terms of the Petersson inner product. We write their Fourier expansion and use it to write an expression for the Ramanujan Δ-function. Also, with the aid of the geometry of the Riemann surface attached to Γ, for each non-elliptic point ξ and integer m≥3, we construct a basis of S _m (Γ,χ) out of the modular forms Δ _k,m,ξ ,χ (k≥0). For Γ=Γ ₀(N), we use this to write a matrix realization of the usual Hecke operators T _p for S _m (N,χ).     

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     

Growth and recurrence of stationary random walks

 Let (X _n ,n≥1) be a real-valued ergodic stationary stochastic process, and let (Y _n =X ₁ +…+X _n ,n≥1) be the associated random walk. We prove the following: if the sequence of distributions of the random variables Y _n /n,n≥1, is uniformly tight (or, more generally, does not have the zero measure as a vague limit point), then there exists a real number c such that the random walk (Y _n −nc,n≥1) is recurrent. If this sequence of distributions converges to a probability measure ρ on ℝ (or, more generally, has a nonzero limit ρ in the vague topology), then (Y _n −nc,n≥1) is recurrent for ρ−a.e.cℝ. Received: 24 September 2001 / Revised version: 1 August 2002 / Published online: 24 October 2002 The first author was partially supported by the FWF research project P14379-MAT. Mathematics Subject Classification (2000): 37A20, 37A50, 60G10, 60G50 Key words or phrases: Recurrent stationary random walks – Recurrent cocycles     

Ornstein-Zernike theory for finite range Ising models above T c

 We derive a precise Ornstein-Zernike asymptotic formula for the decay of the two-point function 〈Σ₀Σ _x 〉_β in the general context of finite range Ising type models on ℤ ^d . The proof relies in an essential way on the a-priori knowledge of the strict exponential decay of the two-point function and, by the sharp characterization of phase transition due to Aizenman, Barsky and Fernández, goes through in the whole of the high temperature region β<β _c . As a byproduct we obtain that for every β<β _c , the inverse correlation length ξ_β is an analytic and strictly convex function of direction. Received: 10 January 2002 / Revised version: 19 June 2002 / Published online: 14 November 2002 Partly supported by Italian G. N. A. F. A, EC grant SC1-CT91-0695 and the University of Bologna. Funds for selected research topics. Partly supported by the ISRAEL SCIENCE FOUNDATION founded by The Israel Academy of Science and Humanities. Partly supported by the Swiss National Science Foundation grant #8220-056599. Mathematics Subject Classification (2000): 60F15, 60K15, 60K35, 82B20, 37C30 Key words or phrases: Ising model – Ornstein-Zernike decay of correlations – Ruelle operator – Renormalization – Local limit theorems     

Disk-like Tiles Derived from Complex Bases

For each positive integer k, the radix representation of the complex numbers in the base –k+i gives rise to a lattice self-affine tile T _k in the plane, which consists of all the complex numbers that can be expressed in the form ∑ _j≥1 d _j (–k+i)^–j , where d _j ∈{0, 1, 2, ...,k ²}. We prove that T _k is homeomorphic to the closed unit disk {z∈C:∣z∣ ≤ 1} if and only if k ≠ 2. The first author is supported by Youth Project of Tianyuan Foundation (10226031) and Zhongshan University Promotion Foundation for Young Teachers (34100-1131206); the second author is supported by National Science Foundation (10041005) and Guangdong Province Science Foundation (011221)     

Approximation of the effective conductivity of ergodic media by periodization

 This paper is concerned with the approximation of the effective conductivity σ(A, μ) associated to an elliptic operator ∇ _xA (x,η)∇ _x where for xℝ ^d , d≥1, A(x,η) is a bounded elliptic random symmetric d×d matrix and η takes value in an ergodic probability space (X, μ). Writing A ^N (x, η) the periodization of A(x, η) on the torus T ^d _N of dimension d and side N we prove that for μ-almost all η

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

An optimal bound on the tail distribution of the number of recurrences of an event in product spaces

 Let X ₁ ,X ₂ ,... be independent random variables and a a positive real number. For the sake of illustration, suppose A is the event that |X _i+1 +...+X _j |≥a for some integers 0≤i<j<∞. For each k≥2 we upper-bound the probability that A occurs k or more times, i.e. that A occurs on k or more disjoint intervals, in terms of P(A), the probability that A occurs at least once. More generally, let X=(X ₁ ,X ₂ ,...)Ω=Π _{j ≥1}Ω _j be a random element in a product probability space (Ω,ℬ,P=⊗ _{j ≥1} P _j ). We are interested in events AB that are (at most contable) unions of finite-dimensional cylinders. We term such sets sequentially searchable. Let L(A) denote the (random) number of disjoint intervals (i,j] such that the value of X _(i,j] =(X _i+1 ,...,X _j ) ensures that XA. By definition, for sequentially searchable A, P(A)≡P(L(A)≥1)=P(𝒩_{−ln (P(Ac))} ≥1), where 𝒩_γ denotes a Poisson random variable with some parameter γ>0. Without further assumptions we prove that, if 0<P(A)<1, then P(L(A)≥k)<P(𝒩_{−ln (P(Ac))} ≥k) for all integers k≥2. An application to sums of independent Banach space random elements in l ^∞ is given showing how to extend our theorem to situations having dependent components. Received: 8 June 2001 / Revised version: 30 October 2002 Published online: 15 April 2003 RID="*" ID="*" Supported by NSF Grant DMS-99-72417. RID="†" ID="†" Supported by the Swedish Research Council. Mathematics Subject Classification (2000): Primary 60E15, 60G50 Key words or phrases: Tail probability inequalities – Hoffmann-Jo rgensen inequality – Poisson bounds – Number of event recurrences – Number of entrance times – Product spaces     

A Bichromatic Incidence Bound and an Application

We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O _d (m ^2/3 k ^2/3 n ^(d−2)/3+kn ^d−2+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Ω(n ^d−2). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359–369, 1992).     

On Light Graphs in 3-Connected Plane Graphs Without Triangular or Quadrangular Faces

 We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P _k , a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m. Received: June 29, 1998 Final version received: April 11, 2000     

The Decomposition Dimension of Graphs

 For an ordered k-decomposition ? = {G ₁, G ₂,…,G _k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G ₁), d(e, G ₂),…,d(e, G _k )), where d(e, G _i ) is the distance from e to G _i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K _n ) ≤⌊(2n + 5)/3⌋ for n≥ 3. Received: June 17, 1998 Final version received: August 10, 1999     

Measure-valued limits of interacting particle systems with <Emphasis Type="Italic">k</Emphasis>-nary interactions

 Results on existence, uniqueness, non-explosion and stochastic monotonicity are obtained for one-dimensional Markov processes having non-local pseudo-differential generators with symbols of polynomial growth. It is proven that the processes of this kind can be obtained as the limits of random evolutions of systems of identical indistinguishable particles with k-nary interaction. Received: 24 May 2002 / Revised version: 19 February 2003 / Published online: 12 May 2003 Mathematics Subject Classification (2000): 60K35, 60J75, 60J80 Key words or phrases: Interacting particles – k-nary interaction – Measure-valued processes – One-dimensional Feller processes with polynomially growing symbols – Duality – Stochastic monotonicity – Heat kernel     

Kähler hyperbolicity and the Euler number of a compact manifold with geodesic flow of Anosov type

 Let M be a 2m-dimensional compact Riemannian manifold with Anosov geodesic flow. We prove that every closed bounded k form, k≥2, on the universal covering of M is d(bounded). Further, if M is homotopy equivalent to a compact K?hler manifold, then its Euler number χ(M) satisfies (−1) ^m χ(M)>0. Received: 25 September 2001 / Published Online: 16 October 2002