A Note on the Embedding of Subspaces of Lp into ℓNr, 0 < r < 1, r ≦ p < 2

In this paper we extend a result by Bourgain-Lindenstrauss-Milman (see [1]). We prove: Let 0 < ? < 1/2, 0< r < 1, r< p < 2. There exists a constant C = C(r,p,?) such that if X is any n-dimensional subspace of L_p(0, l), then there exists Y ? ?^N_r with d(X, Y) ≦ 1 + ?, whenever N > Cn. As an application, we obtain the following partial result: Let 0 < r < 1. There exist constants C = C(r) and C' = C' (r) such that if X is any n-dimensional subspace of L_r(0,1), then there exists Y ? ^N_r with d(X, Y) ≦ C (logn)^l/^r, whenever N ≧ C'n.     

Percolation in Voronoi tilings

We consider a percolation process on a random tiling of ℝ^d into Voronoi cells based on points of a realization of a Poisson process. We prove the existence of a phase transition as the proportion p of open cells is varied and provide estimates for the critical probability p_c. Specifically, we prove that for large d, 2^−d(9d log d)⁻¹ ≤ p_c(d) ≤ C2^−d log d. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

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     

Merging percolation on Zd and classical random graphs: Phase transition

We study a random graph model which is a superposition of bond percolation on Z^d with parameter p, and a classical random graph G(n,c/n). We show that this model, being a homogeneous random graph, has a natural relation to the so‐called “rank 1 case” of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the set of parameters c ≥ 0 and 0 ≤ p < p_c, where p_c = p_c(d) is the critical probability for the bond percolation on Z^d. The phase transition is of second order as in the classical random graph. We find the scaled size of the largest connected component in the supercritical regime. We also provide a sharp upper bound for the largest connected component in the subcritical regime. The latter is a new result for inhomogeneous random graphs with unbounded kernels. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Growth and percolation on the uniform infinite planar triangulation

A construction as a growth process for sampling of the uniform in- finite planar triangulation (UIPT), defined in [AnS], is given. The construction is algorithmic in nature, and is an efficient method of sampling a portion of the UIPT.By analyzing the progress rate of the growth process we show that a.s. the UIPT has growth rate r ⁴ up to polylogarithmic factors, in accordance with heuristic results from the physics literature. Additionally, the boundary component of the ball of radius r separating it from infinity a.s. has growth rate r ² up to polylogarithmic factors. It is also shown that the properly scaled size of a variant of the free triangulation of an m-gon (also defined in [AnS]) converges in distribution to an asymmetric stable random variable of type 1/2.By combining Bernoulli site percolation with the growth process for the UIPT, it is shown that a.s. the critical probability p _c = 1/2 and that at p _c percolation does not occur.     

Lifting results for rational points on Hurwitz moduli spaces

Hurwitz moduli spaces for G-covers of the projective line have two classical variants whether G-covers are considered modulo the action of PGL₂ on the base or not. A central result of this paper is that, given an integer r ≥ 3 there exists a bound d(r) ≥ 1 depending only on r such that any rational point p ^rd of a reduced (i.e., modulo PGL₂) Hurwitz space can be lifted to a rational point p on the nonreduced Hurwitz space with [κ(p): κ(p ^rd)] ≤ d(r). This result can also be generalized to infinite towers of Hurwitz spaces. Introducing a new Galois invariant for G-covers, which we call the base invariant, we improve this result for G-covers with a nontrivial base invariant. For the sublocus corresponding to such G-covers the bound d(r) can be chosen depending only on the base invariant (no longer on r) and ≤ 6. When r = 4, our method can still be refined to provide effective criteria to lift k-rational points from reduced to nonreduced Hurwitz spaces. This, in particular, leads to a rigidity criterion, a genus 0 method and, what we call an expansion method to realize finite groups as regular Galois groups over ℚ. Some specific examples are given.     

Nearest neighbor and hard sphere models in continuum percolation

Consider a Poisson process X in R ^d with density 1. We connect each point of X to its k nearest neighbors by undirected edges. The number k is the parameter in this model. We show that, for k = 1, no percolation occurs in any dimension, while, for k = 2, percolation occurs when the dimension is sufficiently large. We also show that if percolation occurs, then there is exactly one infinite cluster. Another percolation model is obtained by putting balls of radius zero around each point of X and let the radii grow linearly in time until they hit another ball. We show that this model exists and that there is no percolation in the limiting configuration. Finally we discuss some general properties of percolation models where balls placed at Poisson points are not allowed to overlap (but are allowed to be tangent). © 1996 John Wiley & Sons, Inc.     

Embedding Subspaces of Lp into 𝓁Np, 0 < p < 1

It is shown that if X is an n – dimensional subspace of L_p, 0 < p < 1, then there exists a subspace Y of 𝓁^N_p such that d(X, Y) ≤ 1 + ε and N ≤ C(ε, p)n(log n)³.     

Generating Random Vectors in (ℤ/<Emphasis Type="Italic">p</Emphasis>ℤ)<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript> via an Affine Random Process

This paper considers some random processes of the form X _n+1=T X _n +B _n (mod p) where B _n and X _n are random variables over (ℤ/pℤ) ^d and T is a fixed d×d integer matrix which is invertible over the complex numbers. For a particular distribution for B _n , this paper improves results of Asci to show that if T has no complex eigenvalues of length 1, then for integers p relatively prime to det (T), order (log p)² steps suffice to make X _n close to uniformly distributed where X ₀ is the zero vector. This paper also shows that if T has a complex eigenvalue which is a root of unity, then order p ^b steps are needed for X _n to get close to uniformly distributed for some positive value b≤2 which may depend on T and X ₀ is the zero vector.     

Separations by Random Oracles and “Almost” Classes for Generalized Reducibilities

Let ≤_r and ≤_sbe two binary relations on 2^ℕ which are meant as reducibilities. Let both relations be closed under finite variation (of their set arguments) and consider the uniform distribution on 2^ℕ, which is obtained by choosing elements of 2^ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤_r‐cone of a randomly chosen set X, that is, the class of all sets A with A ≤_r X, differs from the lower ≤_s‐cone of X. By c osure under finite variation, the Kolmogorov 0‐1 aw yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles.Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper ≤_r‐cone of A is either 0 or 1; let Almost_r be the class of sets for which the upper ≤_r‐cone has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on 2^ℕ which can be defined by a countable set of total continuous functionals on 2^ℕ in the same way as the usual resource‐bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises a natura resource‐bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yield corollaries about specific resource‐bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations.     

Lusternik–Schnirelmann category of non-simply connected compact simple Lie groups

Let FX→B be a fibre bundle with structure group G, where B is (d−1)-connected and of finite dimension, d1. We prove that the strong L–S category of X is less than or equal to , if F has a cone decomposition of length m under a compatibility condition with the action of G on F. This gives a consistent prospect to determine the L–S category of non-simply connected Lie groups. For example, we obtain cat(PU(n))3(n−1) for all n1, which might be best possible, since we have cat(PU(p^r))=3(p^r−1) for any prime p and r1. Similarly, we obtain the L–S category of SO(n) for n9 and PO(8). We remark that all the above Lie groups satisfy the Ganea conjecture on L–S category.     

l p n Superspaces of spans of independent random variables

We show that for 1 ≦p < ∞,p ≠ 2, ifɛ > 0 is small enough andX ≦L _p is the span ofn independent Rademacher functions orn independent Gaussian random variables, then any superspaceY ofX satisfyingd(Y,L _p ^m ) ≦ 1 +ɛ has dimension larger thanr ⁿ, wherer =r(ɛ, p) > 1. This forms part of the author’s doctoral dissertation prepared at Texas A&M University under the direction of Professor W. B. Johnson. Supported in part by NSF DMS-85 00764.     

Percolation on random recursive trees

We study Bernoulli bond percolation on a random recursive tree of size n with percolation parameter p(n) converging to 1 as n tends to infinity. The sizes of the percolation clusters are naturally stored in a tree structure. We prove convergence in distribution of this tree‐indexed process of cluster sizes to the genealogical tree of a continuous‐state branching process in discrete time. As a corollary we obtain the asymptotic sizes of the largest and next largest percolation clusters, extending thereby a recent work of Bertoin [5]. In a second part, we show that the same limit tree appears in the study of the tree components which emerge from a continuous‐time destruction of a random recursive tree. We comment on the connection to our first result on Bernoulli bond percolation. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 655–680, 2016     

Coloring random graphs online without creating monochromatic subgraphs

Consider the following random process: The vertices of a binomial random graph G_n,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p₀(F,r,n) = n^‐1/m*₁(F,r), where m*₁(F,r) denotes the so‐called online vertex‐Ramsey density of F and r. This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex‐Ramsey density m*₁(F,r) is a computable rational number. Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring G_n,p as desired with probability 1 ‐ o(1) for any p(n) = o(n^‐1/m*₁(F,r)). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014     

Global nonparametric estimation of conditional quantile functions and their derivatives

Let (X, Y) be a random vector such that X is d-dimensional, Y is real valued, and θ(X) is the conditional αth quantile of Y given X, where α is a fixed number such that 0 < α < 1. Assume that θ is a smooth function with order of smoothness p > 0, and set r = (p − m)/(2p + d), where m is a nonnegative integer smaller than p. Let T(θ) denote a derivative of θ of order m. It is proved that there exists estimate of T(θ), based on a set of i.i.d. observations (X₁, Y₁), …, (X_n, Y_n), that achieves the optimal nonparametric rate of convergence n^−r in L_q-norms (1 ≤ q < ∞) restricted to compacts under appropriate regularity conditions. Further, it has been shown that there exists estimate of T(θ) that achieves the optimal rate (n/log n)^−r in L_∞-norm restricted to compacts.     

Lower bounds for weak epsilon-nets and stair-convexity

A set N ⊂ ℝ ^d is called a weak ɛ-net (with respect to convex sets) for a finite X ⊂ ℝ ^d if N intersects every convex set C with |X ∩ C| ≥ ɛ|X|. For every fixed d ≥ 2 and every r ≥ 1 we construct sets X ⊂ ℝ ^d for which every weak 1/r -net has at least Ω(r log ^d−1 r) points; this is the first superlinear lower bound for weak ɛ-nets in a fixed dimension.     

On the Strong Law of Large Numbers and the Law of the Logarithm for Weighted Sums of Independent Random Variables with Multidimensional Indices

Let (X, X ; ^d} be a field of independent identically distributed real random variables, 0 < p < 2, and {a _, ; ( , ) ^d × ^d, ≤ } a triangular array of real numbers, where ^d is the d-dimensional lattice. Under the minimal condition that sup _, |a _, | < ∞, we show that | |^{− 1/p} ∑ _≤ a _, X → 0 a.s. as | | → ∞ if and only if E(|X|^p(L|X|)^{d − 1}) < ∞ provided d ≥ 2. In the above, if 1 ≤ p < 2, the random variables are needed to be centered at the mean. By establishing a certain law of the logarithm, we show that the Law of the Iterated Logarithm fails for the weighted sums ∑ _≤ a _, X under the conditions that EX = 0, EX² < ∞, and E(X²(L|X|)^{d − 1}/L₂|X|) < ∞ for almost all bounded families {a _, ; ( , ) ^d × ^d, ≤ of numbers.     

Some properties of the range of super-Brownian motion

We consider a super-Brownian motion X. Its canonical measures can be studied through the path-valued process called the Brownian snake. We obtain the limiting behavior of the volume of the ɛ-neighborhood for the range of the Brownian snake, and as a consequence we derive the analogous result for the range of super-Brownian motion and for the support of the integrated super-Brownian excursion. Then we prove the support of X _t is capacity-equivalent to [0, 1]² in ℝ^d, d≥ 3, and the range of X, as well as the support of the integrated super-Brownian excursion are capacity-equivalent to [0, 1]⁴ in ℝ^d, d≥ 5. Received: 7 April 1998 / Revised version: 2 October 1998     

On K1 and K2 of Algebraic Surfaces

In this paper we study higher Chow groups of smooth, projective surfaces over a field k of characteristic zero, using some new Hodge theoretic methods which we develop for this purpose. In particular we investigate the subgroup of CH ^r+1 (X,r) with r = 1,2 consisting of cycles that are supported over a normal crossing divisor Z on X. In this case, the Hodge theory of the complement forms an interesting variation of mixed Hodge structures in any geometric deformation of the situation. Our main result is a structure theorem in the case where X is a very general hypersurface of degree d in projective 3-space for d sufficiently large and Z is a union of very general hypersurface sections of X. In this case we show that the subgroup of CH ^r+1 (X,r) we consider is generated by obvious cycles only arising from rational functions on X with poles along Z. This can be seen as a generalization of the Noether–Lefschetz theorem for r = 0. In the case r = 1 there is a similar generalization by Müller-Stach, but our result is more precise than it, since it is geometric and not only cohomological. The case r = 2 is entirely new and original in this paper. For small d, we construct some explicit examples for r = 1 and 2 where the corresponding higher Chow groups are indecomposable, i.e. not the image of certain products of lower order groups. In an appendix Alberto Collino constructs even more indecomposable examples in CH ³ (X,2) which move in a one-dimensional family on the surface X.Contribution to appendix.     

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.