Rate of growth of the coalescent set in a coalescing stochastic flow

Consider an isotropic stochastic flow in R_d (i.e. a simultaneous random, correlated motion of all points in space), where d=l,2 or 3, such that the joint law of the motion of two particles allows the particles to meet and coalesce in finite time. The coalescent set J _t is a random subset of R_d consisting of the initial positions of particles which have coalesced by time t with the particle which started at 0. We show that the expected volume of J t grows at a rate proportional to when d=1, and at rates close to proportional to t/log t (resp. t) when d = 2 (resp. d=3). We give an example of a coalescing stochastic flow when d = 3. These results are analogous to growth rates of expected population size of a surviving type in the "invasion process" described by Clifford and Sudbury     

Limit theory for the random on‐line nearest‐neighbor graph

In the on‐line nearest‐neighbor graph (ONG), each point after the first in a sequence of points in ?^d is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large‐sample asymptotic behavior of the total power‐weighted length of the ONG on uniform random points in (0,1)^d. In particular, for d = 1 and weight exponent α > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed‐point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest‐neighbor (directed) graph on uniform random points in the unit interval. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Planelike minimizers in periodic media

We show that given an elliptic integrand ?? in ?^d that is periodic under integer translations, and given any plane in ?^d, there is at least one minimizer of ?? that remains at a bounded distance from this plane. This distance can be bounded uniformly on the planes. We also show that, when folded back to ?^d/?^d, the minimizers we construct give rise to a lamination. One particular case of these results is minimal surfaces for metrics invariant under integer translations. The same results hold for other functionals that involve volume terms (small and average zero). In such a case the minimizers satisfy the prescribed mean curvature equation. A further generalization allows the formulation and proof of similar results in manifolds other than the torus provided that their fundamental group and universal cover satisfy some hypotheses. © 2001 John Wiley & Sons, Inc.     

Stability of Gabor frames with arbitrary sampling points

Summary We study the stability of Gabor frames with arbitrary sampling points in the time-frequency plane, in several aspects. We prove that a Gabor frame generated by a window function in the Segal algebra S₀(R^d) remains a frame even if (possibly) all the sampling points undergo an arbitrary perturbation, as long as this is uniformly small. We give explicit stability bounds when the window function is nice enough, showing that the allowed perturbation depends only on the lower frame bound of the original family and some qualitative parameters of the window under consideration. For the perturbation of window functions we show that a Gabor frame generated by any window function with arbitrary sampling points remains a frame when the window function has a small perturbation in S₀(R^d) sense. We also study the stability of dual frames, which is useful in practice but has not found much attention in the literature. We give some general results on this topic and explain consequences to Gabor frames.     

Percolation and limit theory for the poisson lilypond model

The lilypond model on a point process in d ‐space is a growth‐maximal system of non‐overlapping balls centred at the points. We establish central limit theorems for the total volume and the number of components of the lilypond model on a sequence of Poisson or binomial point processes on expanding windows. For the lilypond model over a homogeneous Poisson process, we give subexponentially decaying tail bounds for the size of the cluster at the origin. Finally, we consider the enhanced Poisson lilypond model where all the balls are enlarged by a fixed amount (the enhancement parameter), and show that for d > 1 the critical value of this parameter, above which the enhanced model percolates, is strictly positive. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

On lattice points in polyhedral cross-sections

(a) We prove that the convex hull of anyk ^d +1 points of ad-dimensional lattice containsk+1 collinear lattice points. (b) For a convex polyhedron we consider the numbers of its lattice points in consecutive parallel lattice hyperplanes (levels). We prove that if a polyhedron spans no more than 2 ^d−1 levels, then this string of numbers may be arbitrary. On the other hand, we give an example of a string of 2 ^d−1+1 numbers to which no convex polyhedron corresponds inR ^d .     

Limiting Values under Scaling of the Lebesgue Function for Polynomial Interpolation on Spheres

We consider interpolation by spherical harmonics at points on a (d−1)-dimensional sphere and show that, in the limit, as the points coalesce under an angular scaling, the Lebesgue function of the process converges to that of an associated algebraic interpolation problem for the original angles considered as points in ^d−1.     

The identification problem for the exponential Radon transform

The exponential Radon transform, which arises in single photon emission computed tomography, is defined by ? ?(μ:ω,s) = ∫_R?(sω + tomega;^?) e^μt dt?. Here ? is a compactly supported distribution in the plane which represents the location and intensity of a radio-pharmaceutical in a body of constant, but unknown, attenuation μ, and ω is a direction. The identification problem is to determine the attenuation μ from the data ?? with ? unknown. We will show that μ can be determined from the data if and only if ? is not a radial distribution and give formulae for computing μ when ? is not radial.     

On estimating the derivatives of symmetric diffusions in stationary random environment,with applications to ∇<Emphasis Type="Italic">ϕ</Emphasis> interface model

We consider diffusions on ℝ^d or random walks on ℤ^d in a random environment which is stationary in space and in time and with symmetric and uniformly elliptic coefficients. We show existence and H?lder continuity of second space derivatives and time derivatives for the annealed kernels of such diffusions and give estimates for these derivatives. In the case of random walks, these estimates are applied to the Ginzburg-Landau ∇ϕ interface model.     

On the Number of Galois Points for a Plane Curve in Positive Characteristic

We study Galois points for a plane smooth curve C ? P ² of degree d ≥ 4 in characteristic p > 2. We generalize Yoshihara's result on the number of inner (resp., outer) Galois points to positive characteristic under the assumption that d ? 1 (resp., d ? 0) modulo p. As an application, we also find the number of Galois points in the case that d = p.     

Colorful Strips

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k − 1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k − 1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy.     

Triangulating point sets in space

A setP ofn points inR ^d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn/(d + 1) points. A splitter can be found inO(d ⁴ +nd ²) time. Using this result, we give anO(nd ⁴ log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR ³ we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR ³ for which the number of simplices produced may vary between (n – 1)² + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678.     

Specifying attracting cycles for Newton maps of polynomials

We show that for any set of n distinct points in the complex plane, there exists a polynomial p of degree at most n+1 so that the corresponding Newton map, or even the relaxed Newton map, for p has the given points as a super-attracting cycle. This improves the result in Plaza and Romero [6], which shows how to find such a polynomial of degree 2n. Moreover, we show that in general one cannot improve upon degree n+1. Our methods allow us to give a simple, constructive proof of the known result that for each cycle length n ≥ 2 and degree d ≥ 3, there exists a polynomial of degree d whose Newton map has a super-attracting cycle of length n.     

Presenting Schur Algebras as Quotients of the Universal Enveloping Algebra of gl2

We give a presentation of the Schur algebras S _Q (2,d) by generators and relations, in fact a presentation which is compatible with Serre's presentation of the universal enveloping algebra of a simple Lie algebra. In the process we find a new basis for S _Q (2,d), a truncated form of the usual PBW basis. We also locate the integral Schur algebra within the presented algebra as the analogue of Kostant's Z-form, and show that it has an integral basis which is a truncated version of Kostant's basis.     

Fitting a Set of Points by a Circle

Given a set of points S={p ₁ ,. . ., p _n } in Euclidean d -dimensional space, we address the problem of computing the d -dimensional annulus of smallest width containing the set. We give a complete characterization of the centers of annuli which are locally minimal in arbitrary dimension and we show that, for d=2 , a locally minimal annulus has two points on the inner circle and two points on the outer circle that interlace anglewise as seen from the center of the annulus. Using this characterization, we show that, given a circular order of the points, there is at most one locally minimal annulus consistent with that order and it can be computed in time O(n log n) using a simple algorithm. Furthermore, when points are in convex position, the problem can be solved in optimal Θ(n) time. Received June 25, 1997, and in revised form March 5, 1998.     

Another Three Part Sperner Theorem

We show that a result of Katona can be made into a three part Sperner theorem which is independent of the best previously known such theorem, in that neither hypothesis implies the other. These three part theorems are stated in terms of a three dimensional rectangular integer lattice L, and give sufficient conditions for F ? L, containing no two points on a line, to be no larger in size than the set of points of middle rank in L. The theorems apply to the more general problem in which L is the product of three symmetric chain orders and F ? L contains no two points equal in two components and ordered in the third.     

Simulation of Stationary Gaussian Processes in [0, 1] d

Abstract

A method for simulating a stationary Gaussian process on a fine rectangular grid in [0, 1]^d ??^d is described. It is assumed that the process is stationary with respect to translations of ?^d, but the method does not require the process to be isotropic. As with some other approaches to this simulation problem, our procedure uses discrete Fourier methods and exploits the efficiency of the fast Fourier transform. However, the introduction of a novel feature leads to a procedure that is exact in principle when it can be applied. It is established that sufficient conditions for it to be possible to apply the procedure are (1) the covariance function is summable on ?^d, and (2) a certain spectral density on the d-dimensional torus, which is determined by the covariance function on ?^d, is strictly positive. The procedure can cope with more than 50,000 grid points in many cases, even on a relatively modest computer. An approximate procedure is also proposed to cover cases where it is not feasible to apply the procedure in its exact form.     

Cohomology vanishing¶and a problem in approximation theory

For a simplicial subdivison Δ of a region in k ⁿ (k algebraically closed) and r∈N, there is a reflexive sheaf ? on P ⁿ , such that H ⁰(?(d)) is essentially the space of piecewise polynomial functions on Δ, of degree at most d, which meet with order of smoothness r along common faces. In [9], Elencwajg and Forster give bounds for the vanishing of the higher cohomology of a bundle ℰ on P ⁿ in terms of the top two Chern classes and the generic splitting type of ℰ. We use a spectral sequence argument similar to that of [16] to characterize those Δ for which ? is actually a bundle (which is always the case for n= 2). In this situation we can obtain a formula for H ⁰(?(d)) which involves only local data; the results of [9] cited earlier allow us to give a bound on the d where the formula applies. We also show that a major open problem in approximation theory may be formulated in terms of a cohomology vanishing on P ² and we discuss a possible connection between semi-stability and the conjectured answer to this open problem. Received: 9 April 2001