Graph diameter in long‐range percolation

We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^dWe study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^d$. We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x ? y|^?s+o(1) when |x ? y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)^Δ+o(1) where Δ^?1 := log₂(2d/s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp{r^1/Δ+o(1)} in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210‐227, 2011     

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.     

Non-recursive functions,knots “with thick ropes,” and self-clenching “thick” hyperspheres

We introduce an approach to certain geometric variational problems based on the use of the algorithmic unrecognizability of the n-dimensional sphere for n ≥ 5. Sometimes this approach allows one to prove the existence of infinitely many solutions of a considered variational problem. This recursion-theoretic approach is applied in this paper to a class of functionals on the space of C^1.1-smooth hypersurfaces diffeomorphic to Sⁿ in Rⁿ⁺¹, where n is any fixed number ≥ 5. The simplest of these functionals k_v is defined by the formula k_v(Σⁿ) = (vol(Σⁿ))^1/n/r(Σⁿ), where r(Σⁿ) denotes the radius of injectivity of the normal exponential map for Σⁿ ? Rⁿ+l. We prove the existence of an infinite set of distinct locally minimal values of k_v on the space of C^1.1-smooth topological hyperspheres in Rⁿ⁺¹ for any n ≥ 5. The functional k_v naturally arises when one attempts to generalize knot theory in order to deal with embeddings and isotopies of “thick” circles and, more generally, “thick” spheres into Euclidean spaces. We introduce the notion of knot “with thick rope” types. The theory of knot “with thick rope” types turns out to be quite different from the classical knot theory because of the following result: There exists an infinite set of non-trivial knot “with thick rope” types in codimension one for every dimension greater than or equal to five.     

Erratum to the paper “An Integral Delay Inequality and its Applications to Boundary Value Problems”

We consider the infinitesimal generator of the time reversal of a time-homogeneous one-dimensional gap diffusion with state space [0, 1] given by the infinitesimal generator A^o = dD_s⁺ - dk / dm with nonlocal boundary conditions of Feller-Wentzell-type. This leads to an infinitesimal generator which belongs to a class of generators introduced in the earlier note [W1].     

On Heilbronn’s Problem in Higher Dimension

Heilbronn conjectured that given arbitrary n points in the 2-dimensional unit square [0, 1]², there must be three points which form a triangle of area at most O(1/n²). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz and Szemerédi [10] who showed that for every n there is a configuration of n points in the unit square [0, 1]² where all triangles have area at least (log n/n²). Considering a generalization of this problem to dimensions d3, Barequet [3] showed for every n the existence of n points in the d-dimensional unit cube [0, 1]^d such that the minimum volume of every simplex spanned by any (d+1) of these n points is at least (1/n^d). We improve on this lower bound by a logarithmic factor (log n).     

Spin depolarization decay rates in α-symmetric stable fields on cubic lattices

We study the asymptotic, long-time behavior of the energy function where {X_s : 0 ≤ s < ∞} is the standard random walk on the d-dimensional lattice Z^d, 1 < α ≤ 2, and f:R⁺ → R⁺ is any nondecreasing concave function. In the special case f(x) = x, our setting represents a lattice model for the study of transverse magnetization of spins diffusing in a homogeneous, α-stable, i.i.d., random, longitudinal field {λV(x) : x ∈ Z^d} with common marginal distribution, the standard α-symmetric stable distribution; the parameter λ describes the intensity of the field. Using large-deviation techniques, we show that S_c(λ α f) = lim_t→∞ E(t; λ f) exists. Moreover, we obtain a variational formula for this decay rate S_c. Finally, we analyze the behavior S_c(λ α f) as λ → 0 when f(x) = x^β for all 1 ≥ β > 0. Consequently, several physical conjectures with respect to lattice models of transverse magnetization are resolved by setting β = 1 in our results. We show that S_c(λ, α, 1) ≈ λ^α for d ≥ 3, λ^agr;(ln 1/λ)^α−1 in d = 2, and in d = 1. © 1996 John Wiley & Sons, Inc.     

Stabbing Simplices by Points and Flats

The following result was proved by Bárány in 1982: For every d≥1, there exists c _d >0 such that for every n-point set S in ℝ ^d , there is a point p∈ℝ ^d contained in at least c _d n ^d+1−O(n ^d ) of the d-dimensional simplices spanned by S. We investigate the largest possible value of c _d . It was known that c _d ≤1/(2 ^d (d+1)!) (this estimate actually holds for every point set S). We construct sets showing that c _d ≤(d+1)^−(d+1), and we conjecture that this estimate is tight. The best known lower bound, due to Wagner, is c _d ≥γ _d :=(d ²+1)/((d+1)!(d+1) ^d+1); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than γ _d n ^d+1+O(n ^d ) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved.     

On Approximate Spectral Factorization of Matrix Functions

It is proved that if positive definite matrix functions (i.e. matrix spectral densities) S _n , n=1,2,… , are convergent in the L ₁-norm, ||S_n-S||_L1? 0\|S_{n}-S\|_{L_{1}}\to 0, and ò₀^2plogdetS_n(e^iq) dq?ò₀^2plogdetS(e^iq) dq\int_{0}^{2\pi}\log \mathop{\mathrm{det}}S_{n}(e^{i\theta})\,d\theta\to\int_{0}^{2\pi}\log \mathop{\mathrm{det}}S(e^{i\theta})\,d\theta, then the corresponding (canonical) spectral factors are convergent in L ₂, ||S⁺_n-S⁺||_L2? 0\|S^{+}_{n}-S^{+}\|_{L_{2}}\to 0. The formulated logarithmic condition is easily seen to be necessary for the latter convergence to take place.     

Effective Dynamics of the Nonlinear Schrödinger Equation on Large Domains

We consider the nonlinear Schrödinger (NLS) equation posed on the box [0,L]^d with periodic boundary conditions. The aim is to describe the long‐time dynamics by deriving effective equations for it when L is large and the characteristic size ɛ of the data is small. Such questions arise naturally when studying dispersive equations that are posed on large domains (like water waves in the ocean), and also in the theory of statistical physics of dispersive waves, which goes by the name of “wave turbulence.” Our main result is deriving a new equation, the continuous resonant (CR) equation, which describes the effective dynamics for large L and small ɛ over very large timescales. Such timescales are well beyond the (a) nonlinear timescale of the equation, and (b) the euclidean timescale at which the effective dynamics are given by (NLS) on ℝ^d. The proof relies heavily on tools from analytic number theory, such as a relatively modern version of the Hardy‐Littlewood circle method, which are modified and extended to be applicable in a PDE setting.© 2018 Wiley Periodicals, Inc.     

Metric entropy of the integration operator and small ball probabilities for the Brownian sheet

Let T_d : L₂([0, 1]^d) → C([0, 1]^d) be the d-dimensional integration operator. We show that its Kolmogorov and entropy numbers decrease with order at least k⁻¹ (log k)d− 1/2. From this we derive that the small ball probabilities of the Brownian sheet on [0, 1]^d under the C([0, 1]^d)-norm can be estimated from below by exp(−Cɛ⁻²¦ log ɛ¦^2d−1), which improves the best known lower bounds considerably. We also get similar results with respect to certain Orlicz norms.     

A phase transition phenomenon in a random directed acyclic graph

Let a random directed acyclic graph be defined as being obtained from the random graph G_{n, p} by orienting the edges according to the ordering of vertices. Let γ_n* be the size of the largest (reflexive, transitive) closure of a vertex. For p=c(log n)/n, we prove that, with high probability, γ_n* is asymptotic to n^c log n, 2n(log log n)/log n, and n(1−1/c) depending on whether c<1, c=1, or c>1. We also determine the limiting distribution of the first vertex closure in all three ranges of c. As an application, we show that the expected number of comparable pairs is asymptotic to n^1+c/c log n, ½(n(log log n)/log n)², and ½(n(1−1/c))², respectively. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 164–184, 2001     

Swendsen‐Wang dynamics for general graphs in the tree uniqueness region

The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G = (V,E). The dynamics is conjectured to converge to equilibrium in O(|V|^1/4) steps at any (inverse) temperature β, yet there are few results providing o(|V|) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, when β < β_c(d) where β_c(d) denotes the uniqueness/nonuniqueness threshold on infinite d‐regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degree d ≥ 3. Our proof utilizes a monotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing time and relaxation time Θ(1) on any graph of maximum degree d for all β < β_c(d). Our proof technology can be applied to general monotone Markov chains, including for example the heat‐bath block dynamics, for which we obtain new tight mixing time bounds.     

A Systematic “Saddle Point Near a Pole” Asymptotic Method with Application to the Gauss Hypergeometric Function

In recent works [ 1 ] and [ 2 ], we have proposed more systematic versions of the Laplace’s and saddle point methods for asymptotic expansions of integrals. Those variants of the standard methods avoid the classical change of variables and give closed algebraic formulas for the coefficients of the expansions. In this work we apply the ideas introduced in [ 1 ] and [ 2 ] to the uniform method “saddle point near a pole.” We obtain a computationally more systematic version of that uniform asymptotic method for integrals having a saddle point near a pole that, in many interesting examples, gives a closed algebraic formula for the coefficients. The asymptotic sequence is given, in general, in terms of exponential integrals of fractional order (or incomplete gamma functions). In particular, when the order of the saddle point is two, the basic approximant is given in terms of the error function (as in the standard method). As an application, we obtain new asymptotic expansions of the Gauss Hypergeometric function ₂F₁(a, b, c; z) for large b and c with c > b + 1 .     

Differential forms in Carnot groups: a Γ-convergence approach

Carnot groups (connected simply connected nilpotent stratified Lie groups) can be endowed with a complex (E ₀ ^* , d _c ) of “intrinsic” differential forms. In this paper we prove that, in a free Carnot group of step κ, intrinsic 1-forms as well as their intrinsic differentials d _c appear naturally as limits of usual “Riemannian” differentials d _ε , ε >?0. More precisely, we show that L ²-energies associated with ε ^?κ d _ε on 1 forms Γ-converge, as ε → 0, to the energy associated with d _c .     

Two-Dimensional and Three-Dimensional Point Location in Rectangular Subdivisions

We apply van Emde Boas-type stratified trees to point location problems in rectangular subdivisions in 2 and 3 dimensions. In a subdivision with n rectangles having integer coordinates from [0, U − 1], we locate an integer query point in O((log log U)^d) query time using O(n) space when d ≤ 2 or O(n log log U) space when d = 3. Applications and extensions of this "fixed universe" approach include spatial point location using logarithmic time and linear space in rectilinear subdivisions having arbitrary coordinates, point location in c-oriented polygons or fat triangles in the plane, point location in subdivisions of space into "fat prisms," and vertical ray shooting among horizontal "fat objects." Like other results on stratified trees, our algorithms run on a RAM model and make use of perfect hashing.     

Generalized Stokes resolvent equations in an infinite layer with mixed boundary conditions

In this paper we prove unique solvability of the generalized Stokes resolvent equations in an infinite layer Ω₀ = ℝ^{n –1} × (–1, 1), n ≥ 2, in L^q ‐Sobolev spaces, 1 < q < ∞, with slip boundary condition of on the “upper boundary” ∂Ω⁺₀ = ℝ^{n –1} × {1} and non‐slip boundary condition on the “lower boundary” ∂Ω^–₀ = ℝ^{n –1} × {–1}. The solution operator to the Stokes system will be expressed with the aid of the solution operators of the Laplace resolvent equation and a Mikhlin multiplier operator acting on the boundary. The present result is the first step to establish an L^q ‐theory for the free boundary value problem studied by Beale [9] and Sylvester [22] in L ²‐spaces. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The amount of non-uniqueness for factored equations with Euler-Poisson-Darboux factors

Of concern are factored Euler–Poisson–Darboux equations of the type ∏^N_j=1(d²/dt²+(ρ/t)d/dt+A_j)u(t)=0, where, for example, A_j=−c_jΔ, Δ being the Dirichlet Laplacian acting on L²(Ω), Ω⊂ℝⁿ, and 0<c₁<…<c_N. More generally −A_j can be the square of the generator of a (C₀) group on a Banach space. When the constant ρ is negative, the initial value problem for the factored EPD equation is ill-posed. Nevertheless, we determine how many initial conditions are necessary to guarantee uniqueness of a solution. This number jumps up as ρ crosses a negative integer from right to left. © 1997 by B. G. Teubner Stuttgart–John Wiley & Sons Ltd.     

Cutoff for the Ising model on the lattice

Introduced in 1963, Glauber dynamics is one of the most practiced and extensively studied methods for sampling the Ising model on lattices. It is well known that at high temperatures, the time it takes this chain to mix in L ¹ on a system of size n is O(logn). Whether in this regime there is cutoff, i.e. a sharp transition in the L ¹-convergence to equilibrium, is a fundamental open problem: If so, as conjectured by Peres, it would imply that mixing occurs abruptly at (c+o(1))logn for some fixed c>0, thus providing a rigorous stopping rule for this MCMC sampler. However, obtaining the precise asymptotics of the mixing and proving cutoff can be extremely challenging even for fairly simple Markov chains. Already for the one-dimensional Ising model, showing cutoff is a longstanding open problem. We settle the above by establishing cutoff and its location at the high temperature regime of the Ising model on the lattice with periodic boundary conditions. Our results hold for any dimension and at any temperature where there is strong spatial mixing: For ?² this carries all the way to the critical temperature. Specifically, for fixed d≥1, the continuous-time Glauber dynamics for the Ising model on (?/n?) ^d with periodic boundary conditions has cutoff at (d/2λ _∞)logn, where λ _∞ is the spectral gap of the dynamics on the infinite-volume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even understanding its stationary distribution is limited. The proof hinges on a new technique for translating L ¹-mixing to L ²-mixing of projections of the chain, which enables the application of logarithmic-Sobolev inequalities. The technique is general and carries to other monotone and anti-monotone spin-systems, e.g. gas hard-core, Potts, anti-ferromagentic Ising, arbitrary boundary conditions, etc.     

Contributo allo studio degli sviluppi in serie di polinom? di Laguerre

Sunto. La condizionec ₀ ² +(c₀+c₄)²+...<∞ è posta a fondamento dello studio degli sviluppic ₀L₀(t)+c₁L₁(t)+... in serie di polinom? di Laguerre.