Bounds for Local Density of Sphere Packings and the Kepler Conjecture

This paper formalizes the local density inequality approach to getting upper bounds for sphere packing densities in R ⁿ . This approach was first suggested by L. Fejes Tóth in 1953 as a method to prove the Kepler conjecture that the densest packing of unit spheres in R ³ has density π/\sqrt 18 , which is attained by the ``cannonball packing.' Local density inequalities give upper bounds for the sphere packing density formulated as an optimization problem of a nonlinear function over a compact set in a finite-dimensional Euclidean space. The approaches of Fejes Tóth, of Hsiang, and of Hales to the Kepler conjecture are each based on (different) local density inequalities. Recently Hales, together with Ferguson, has presented extensive details carrying out a modified version of the Hales approach to prove the Kepler conjecture. We describe the particular local density inequality underlying the Hales and Ferguson approach to prove Kepler's conjecture and sketch some features of their proof. Received November 19, 1999, and in revised form April 17, 2001. Online publication December 17, 2001.     

Coherent random permutations with biased record statistics

We consider random permutations that are defined coherently for all values of n, and for each n have a probability distribution which is conditionally uniform given the set of upper and lower record values. Our central example is a two-parameter family of random permutations that are conditionally uniform given the counts of upper and lower records. This family may be seen as an interpolation between two versions of Ewens’ distribution. We discuss characterisations of the conditionally uniform permutations, their asymptotic properties, constructions and relations to random compositions.     

A note on the quantization for probability measures with respect to the geometric mean error

We study the quantization with respect to the geometric mean error for probability measures μ on for which there exist some constants C, η > 0 such that for all ε > 0 and all . For such measures μ, we prove that the upper quantization dimension of μ is bounded from above by its upper packing dimension and the lower one is bounded from below by its lower Hausdorff dimension. This enables us to calculate the quantization dimension for a large class of probability measures which have nice local behavior, including the self-affine measures on general Sierpiński carpets and self-conformal measures. Moreover, based on our previous work, we prove that the upper and lower quantization coefficient for a self-conformal measure are both positive and finite.     

The quantifier complexity of polynomial‐size iterated definitions in first‐order logic

We refine the constructions of Ferrante‐Rackoff and Solovay on iterated definitions in first‐order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier‐free case and in the case of purely existential or universal quantifiers, we show that Ω(n /log n) quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao‐Håstad switching lemma (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The exact packing measure of Lévy trees

We study fine properties of Lévy trees that are random compact metric spaces introduced by Le Gall and Le Jan in 1998 as the genealogy of continuous state branching processes. Lévy trees are the scaling limits of Galton-Watson trees and they generalize the Aldous continuum random tree which corresponds to the Brownian case. In this paper, we prove that Lévy trees always have an exact packing measure: we explicitly compute the packing gauge function and we prove that the corresponding packing measure coincides with the mass measure up to a multiplicative constant.     

A recurrence/transience result for circle packings

It is known that any infinite simplicial complex homeomorphic to the plane and satisfying a couple of other conditions is the nerve of a circle packing of either the plane or the disc (and not of both). We prove that such a complex is the nerve of a packing of the plane or the disc according as the simple random walk on its 1-skeleton is recurrent or transient, and discuss some applications. We also prove a criterion for transience of simple random walk on the 1-skeleton of a triangulation of the plane, in terms of average degrees of suitable sets of vertices.

     

Generalized random recursive constructions and geometric properties of random fractals

We study random recursive constructions in which the contracting vectors have different distributions at different stages. With such constructions, the one parameter family of martingales are introduced and the probabilistic behaviours of the limit random objects (not identically distributed) are discussed. We prove that the random fractal associated with such construction has a constant Hausdorff dimension almost surely and give an explicit formula to determine it. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sharp-interface limit of the Allen-Cahn action functional in one space dimension

We analyze the sharp-interface limit of the action minimization problem for the stochastically perturbed Allen-Cahn equation in one space dimension. The action is a deterministic functional which is linked to the behavior of the stochastic process in the small noise limit. Previously, heuristic arguments and numerical results have suggested that the limiting action should “count” two competing costs: the cost to nucleate interfaces and the cost to propagate them. In addition, constructions have been used to derive an upper bound for the minimal action which was proved optimal on the level of scaling. In this paper, we prove that for d = 1, the upper bound achieved by the constructions is in fact sharp. Furthermore, we derive a lower bound for the functional itself, which is in agreement with the heuristic picture. To do so, we characterize the sharp-interface limit of the space-time energy measures. The proof relies on an extension of earlier results for the related elliptic problem. Mathematics Subject Classification (2000) 49J45, 35R60, 60F10     

Exact packing dimension in random recursive constructions

We explore the exact packing dimension of certain random recursive constructions. In case of polynomial decay at 0 of the distribution function of random variable X, associated with the construction, we prove that it does not exist, and in case of exponential decay it is t|log|logt||, where is the fractal dimension of the limit set and 1/ is the rate of exponential decay.Research supported by the Department of Mathematics and Statistics (Mathematics) at University of Jyväskylä.Mathematics Subject Classification (2000):Primary 28A78, 28A80; Secondary 60D05, 60J80     

填充维数的一个等价定义

本文研究了填充维数与上盒维数的关系.利用Cantor-Bendixson定理的方法,得到了由上盒维数给出的填充维数的等价定义.并证明了齐次Moran集对上盒维数和填充维数的连续性.     

Planar cyclic difference packings

A planar cyclic difference packing modulo v is a collection D = {d₁, d₂,…,d_k} of distinct residues modulo v such that any residue α ≢ 0 (mod v) has at most one representation as a difference d_i − d_j (mod v). This paper develops various constructions of such designs and for a fixed positive integer v presents upper and lower bounds on Ψ (v), the maximal number of elements that a planar cyclic difference packing modulo v can contain. This paper also presents the results of calculating Ψ (v) for v ≤ 144, including the fact that 134 is the smallest value of v for which the elementary upper bound of exceeds Ψ (v) by two. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 426–434, 2000     

Minimum independent dominating sets of random cubic graphs

We present a heuristic for finding a small independent dominating set ?? of cubic graphs. We analyze the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations, and obtain an upper bound on the expected size of ??. A corresponding lower bound is derived by means of a direct expectation argument. We prove that ?? asymptotically almost surely satisfies 0.2641n ≤ |??| ≤ 0.27942n. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 147–161, 2002     

Dispersing hash functions

We define a family of functions F from a domain U to a range R to be dispersing if for every set S ? U of a certain size and random h ∈ F, the expected value of ∣S∣ – ∣h[S]∣ is not much larger than the expectation if h had been chosen at random from the set of all functions from U to R. We give near‐optimal upper and lower bounds on the size of dispersing families and present several applications where using such a family can reduce the use of random bits compared to previous randomized algorithms. A close relationship between dispersing families and extractors is exhibited. This relationship provides good explicit constructions of dispersing hash functions for some parameters, but in general the explicit construction is left open. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Markov Incremental Constructions

A classic result asserts that many geometric structures can be constructed optimally by successively inserting their constituent parts in random order. These randomized incremental constructions (RICs) still work with imperfect randomness: the dynamic operations need only be “locally” random. Much attention has been given recently to inputs generated by Markov sources. These are particularly interesting to study in the framework of RICs, because Markov chains provide highly nonlocal randomness, which incapacitates virtually all known RIC technology. We generalize Mulmuley’s theory of Θ-series and prove that Markov incremental constructions with bounded spectral gap are optimal within polylog factors for trapezoidal maps, segment intersections, and convex hulls in any fixed dimension. The main contribution of this work is threefold: (i) extending the theory of abstract configuration spaces to the Markov setting; (ii) proving Clarkson–Shor-type bounds for this new model; (iii) applying the results to classical geometric problems. We hope that this work will pioneer a new approach to randomized analysis in computational geometry. This work was supported in part by NSF grants CCR-0306283, CCF-0634958.     

Probabilistic and fractal aspects of Lévy trees

We investigate the random continuous trees called Lévy trees, which are obtained as scaling limits of discrete Galton-Watson trees. We give a mathematically precise definition of these random trees as random variables taking values in the set of equivalence classes of compact rooted -trees, which is equipped with the Gromov-Hausdorff distance. To construct Lévy trees, we make use of the coding by the height process which was studied in detail in previous work. We then investigate various probabilistic properties of Lévy trees. In particular we establish a branching property analogous to the well-known property for Galton-Watson trees: Conditionally given the tree below level a, the subtrees originating from that level are distributed as the atoms of a Poisson point measure whose intensity involves a local time measure supported on the vertices at distance a from the root. We study regularity properties of local times in the space variable, and prove that the support of local time is the full level set, except for certain exceptional values of a corresponding to local extinctions. We also compute several fractal dimensions of Lévy trees, including Hausdorff and packing dimensions, in terms of lower and upper indices for the branching mechanism function which characterizes the distribution of the tree. We finally discuss some applications to super-Brownian motion with a general branching mechanism.     

Upper and Lower Hausdorff Dimension Estimates for Invariant Sets of k — 1 — Endomorphisms

For a special class of non–injective maps on Riemannian manifolds upper and lower bounds for the Hausdorff dimension of invariant sets are given in terms of the singular values of the tangent map. The upper estimation is based on a theorem by Douady and Oesterlé and its generalization to Riemannian manifolds by Noack and Reitmann , but additionally information about the noninjectivity is used. The lower estimation can be reached by modifying a method, derived by Shereshevskij for geometric constructions on the real line (also described by Barreira , for similar constructions in general metric spaces. The upper and lower dimension estimates for k — 1 — endomorphisms can for instance be applied to Julia sets of quadratic maps on the complex plane.     

Sparse random graphs: Eigenvalues and eigenvectors

In this paper, we prove the semi‐circular law for the eigenvalues of regular random graph G_n,d in the case d →∞, complementing a previous result of McKay for fixed d. We also obtain a upper bound on the infinity norm of eigenvectors of Erd?s–Rényi random graph G(n,p), answering a question raised by Dekel–Lee–Linial. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Packing Measure and Dimension of Random Fractals

We consider random fractals generated by random recursive constructions. We prove that the box-counting and packing dimensions of these random fractals, K, equals , their almost sure Hausdorff dimension. We show that some almost deterministic conditions known to ensure that the Hausdorff measure satisfies also imply that the packing measure satisfies 0< . When these conditions are not satisfied, it is known . Correspondingly, we show that in this case , provided a random strong open set condition is satisfied. We also find gauge functions (t) so that the -packing measure is finite.     

Packing vertices and edges in random regular graphs

In this paper we consider the problem of finding large collections of vertices and edges satisfying particular separation properties in random regular graphs of degree r, for each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the maximal sizes of these sets. The lower bounds are proved by analyzing a class of algorithms that return feasible solutions for the given problems. The analysis uses the differential equation method proposed by Wormald [Lectures on Approximation and Randomized Algorithms, PWN, Wassaw, 1999, pp. 239–298]. The upper bounds are proved by direct combinatorial means. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Designs from subcode supports of linear codes

We present new constructions of t-designs by considering subcode supports of linear codes over finite fields. In particular, we prove an Assmus-Mattson type theorem for such subcodes, as well as an automorphism characterization. We derive new t-designs (t ≤ 5) from our constructions.