Nonamenable products are not treeable

LetX andY be infinite graphs such that the automorphism group ofX is nonamenable and the automorphism group ofY has an infinite orbit. We prove that there is no automorphism-invariant measure on the set of spanning trees in the direct productX×Y. This implies that the minimal spanning forest corresponding to i.i.d. edge-weights in such a product has infinitely many connected components almost surely. Research partially supported by NSF grant DMS-9803597.     

Intersection-equivalence of Brownian paths and certain branching processes

We show that sample paths of Brownian motion (and other stable processes) intersect the same sets as certain random Cantor sets constructed by a branching process. With this approach, the classical result that two independent Brownian paths in four dimensions do not intersect reduces to the dying out of a critical branching process, and estimates due to Lawler (1982) for the long-range intersection probability of several random walk paths, reduce to Kolmogrov's 1938 law for the lifetime of a critical branching process. Extensions to random walks with long jumps and applications to Hausdorff dimension are also derived.     

Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing

We study the average case performance of the Best Fit algorithm for on-line bin packing under the distributionU{j, k}, in which the item sizes are uniformly distributed in the discrete range {1/k, 2/k,…,j/k}. Our main result is that, in the casej = k − 2, the expected waste for an infinite stream of items remains bounded. This settles an open problem posed by Coffmanet al.[[4]]. It is also the first result which involves a detailed analysis of the infinite multidimensional Markov chain underlying the algorithm.     

Visibility preserving terrain simplification— an experimental study

The terrain surface simplification problem has been studied extensively, as it has important applications in geographic information systems and computer graphics. The goal is to obtain a new surface that is combinatorially as simple as possible, while maintaining a prescribed degree of similarity with the original input surface. Generally, the approximation error is measured with respect to distance (e.g., Hausdorff) from the original or with respect to visual similarity. In this paper, we propose a new method of simplifying terrain surfaces, designed specifically to maximize a new measure of quality based on preserving inter-point visibility relationships. Our work is motivated by various problems of terrain analysis that rely on inter-point visibility relationships, such as optimal antenna placement.

We have implemented our new method and give experimental evidence of its effectiveness in simplifying terrains according to our quality measure. We experimentally compare its performance with that of other leading simplification methods.     

Fractional products of sets

For integers d > 1 and arbitrary 1 ? α ? d, α-products in d-fold Cartesian products are produced by probabilistic methods. Some explicit constructions are given by solutions of instances of the Turán problem for graphs.     

An Upper Bound on the Binomial Process Approximation to the Exceedance Process

In this paper we deal with an approximation to the point process of exceedances over a higher threshold. We compute sharp bounds on the remainder terms when actual distributions of exceedances are replaced by appropriate generalized Pareto distributions (GPD). The bound will be formulated in terms of the von Mises function. The ultimate as well as the penultimate approximations are considered; in the latter case the shape parameter of the approximating GPD depends on the threshold.     

Temperature dependence of the fluorescence properties of curcumin

Steady-state and time-resolved techniques were employed to study the nonradiative process of curcumin dissolved in ethanol and 1-propanol in a wide range of temperatures. We found that the nonradiative rate constants at temperatures between 175-250 K qualitatively follow the same trend as the dielectric relaxation times of both neat solvents. We attribute the nonradiative process to solvent-controlled proton transfer. We also found a kinetic isotope effect on the nonradiative process rate constant of ~2. We propose a model in which the excited-state proton transfer breaks the planar hexagonal structure of the keto-enol center of the molecule. This, in turn, enhances the nonradiative process driven by the twist angle between the two phenol moieties.