Random C 0 homeomorphism perturbations of hyperbolic sets

In this note we consider random C ⁰ homeomorphism perturbations of a hyperbolic set of a C ¹ diffeomorphism. We show that the hyperbolic set is semi-stable under such perturbations, in particular, the topological entropy will not decrease under such perturbations.     

On the fragmentation of a torus by random walk

We consider a simple random walk on a discrete torus \input amssym $({\Bbb Z}/N{\Bbb Z})^d$ with dimension d ≥ 3 and large side length N. For a fixed constant u ≥ 0, we study the percolative properties of the vacant set, consisting of the set of vertices not visited by the random walk in its first [uN^d] steps. We prove the existence of two distinct phases of the vacant set in the following sense: If u > 0 is chosen large enough, all components of the vacant set contain no more than (log N)^λ(u) vertices with high probability as N tends to infinity. On the other hand, for small u > 0, there exists a macroscopic component of the vacant set occupying a nondegenerate fraction of the total volume N^d. In dimensions d ≥ 5, we additionally prove that this macroscopic component is unique by showing that all other components have volumes of order at most (log N)^λ(u). Our results thus solve open problems posed by Benjamini and Sznitman, who studied the small u regime in high dimension. The proofs are based on a coupling of the random walk with random interlacements on \input amssym ${\Bbb Z}^d$ . Among other techniques, the construction of this coupling employs a refined use of discrete potential theory. By itself, this coupling strengthens a result by Windisch. © 2011 Wiley Periodicals, Inc.     

Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs

In [1] it is proved that an uncrowded (k + 1)-hypergraph of average degree t^k contains an independent set of size (cn/t)(1n t)^1/k. We present a polynomial time algorithm that finds such an independent set by derandomizing the original probabilistic proof. The technique that we use can be applied to derandomize other random algorithms that use several random variables having sufficiently small variances. © 1996 John Wiley & Sons, Inc.     

An average case analysis of the minimum spanning tree heuristic for the power assignment problem

We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst‐case approximation ratio of this heuristic is 2. We show that in Euclidean d‐dimensional space, when the vertex set consists of a set of i.i.d. uniform random independent, identically distributed random variables in [0,1]^d, and the distance power gradient equals the dimension d, the minimum spanning tree‐based power assignment converges completely to a constant depending only on d.     

Convergence theorems for adapted sequences of random sets

We consider random sets with values in a separable Banach space. We study set-valued amarts, L¹-amarts, uniform amarts and submartingales. For all these classes of random sets, we prove convergence theorems in all main modes of set convergence (weak, Wijsman, Mosco, and Hausdorff). We also prove new convergence theorems for vector-valued subpramarts and pramarts.     

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     

Suprema of Chaos Processes and the Restricted Isometry Property

We present a new bound for suprema of a special type of chaos process indexed by a set of matrices, which is based on a chaining method. As applications we show significantly improved estimates for the restricted isometry constants of partial random circulant matrices and time‐frequency structured random matrices. In both cases the required condition on the number m of rows in terms of the sparsity s and the vector length n is m ? s log² s log² n. © 2014 Wiley Periodicals, Inc.     

Polynomial parallel volume, convexity and contact distributions of random sets

We characterize convexity of a random compact set X in ℝ^d via polynomial expected parallel volume of X. The parallel volume of a compact set A is a function of r≥0 and is defined here in two steps. First we form the parallel set at distance r with respect to a one- or two-dimensional gauge body B. Then we integrate the volume of this (relative) parallel set with respect to all rotations of B. We apply our results to characterize convexity of the typical grain of a Boolean model via first contact distributions.     

Permutation Matrices, Wreath Products, and the Distribution of Eigenvalues

We consider a class of random matrix ensembles which can be constructed from the random permutation matrices by replacing the nonzero entries of the n×n permutation matrix matrix with M×M diagonal matrices whose entries are random Kth roots of unity or random points on the unit circle. Let X be the number of eigenvalues lying in a specified arc I of the unit circle, and consider the standardized random variable (X–E[X])/(Var(X))^1/2. We show that for a fixed set of arcs I ₁,...,I _N , the corresponding standardized random variables are jointly normal in the large n limit, and compare the covariance structures which arise with results for other random matrix ensembles.     

Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph

It is well known [9] that finding a maximal independent set in a graph is in class NC and [10] that finding a maximal independent set in a hypergraph with fixed dimension is in RNC. It is not known whether this latter problem remains in NC when the dimension is part of the input. We will study the problem when the problem instances are randomly chosen. It was shown in [6] that the expected running time of a simple parallel algorithm for finding the lexicographically first maximal independent set (Ifmis) in a random simple graph is logarithmic in the input size. In this paper, we will prove a generalization of this result. We show that if a random k-uniform hypergraph has vertex set {1, 2, …, n} and its edges are chosen independently with probability p from the set of (ⁿ_k) possible edges, then our algorithm finds the Ifmis in O( ) expected time. The hidden constant is independent of k, p. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 359–377 (1996)     

Eigenvalues of Euclidean random matrices

We study the spectral measure of large Euclidean random matrices. The entries of these matrices are determined by the relative position of n random points in a compact set Ω_n of ?^d. Under various assumptions, we establish the almost sure convergence of the limiting spectral measure as the number of points goes to infinity. The moments of the limiting distribution are computed, and we prove that the limit of this limiting distribution as the density of points goes to infinity has a nice expression. We apply our results to the adjacency matrix of the geometric graph. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On the probability of independent sets in random graphs

Let k be the asymptotic value of the independence number of the random graph G(n, p). We prove that if the edge probability p(n) satisfies p(n) ? n^?2/5ln^6/5n then the probability that G(n, p) does not contain an independent set of size k ? c, for some absolute constant c > 0, is at most exp{?cn²/(k⁴p)}. We also show that the obtained exponent is tight up to logarithmic factors, and apply our result to obtain new bounds on the choice number of random graphs. We also discuss a general setting where our approach can be applied to provide an exponential bound on the probability of certain events in product probability spaces. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 1–14, 2003     

Adaptive estimation in circular functional linear models

We consider the problem of estimating the slope parameter in circular functional linear regression, where scalar responses Y ₁, ..., Y _n are modeled in dependence of 1-periodic, second order stationary random functions X ₁, ...,X _n . We consider an orthogonal series estimator of the slope function β, by replacing the first m theoretical coefficients of its development in the trigonometric basis by adequate estimators. We propose a model selection procedure for m in a set of admissible values, by defining a contrast function minimized by our estimator and a theoretical penalty function; this first step assumes the degree of ill-posedness to be known. Then we generalize the procedure to a random set of admissible m’s and a random penalty function. The resulting estimator is completely data driven and reaches automatically what is known to be the optimal minimax rate of convergence, in terms of a general weighted L ²-risk. This means that we provide adaptive estimators of both β and its derivatives.     

Percolation for the vacant set of random interlacements

We investigate random interlacements on ?^d, d ≥ 3. This model, recently introduced in [8], corresponds to a Poisson cloud on the space of doubly infinite trajectories modulo time shift tending to infinity at positive and negative infinite times. A nonnegative parameter u measures how many trajectories enter the picture. Our main interest lies in the percolative properties of the vacant set left by random interlacements at level u. We show that for all d ≥ 3 the vacant set at level u percolates when u is small. This solves an open problem of [8], where this fact has only been established when d ≥ 7. It also completes the proof of the nondegeneracy in all dimensions d ≥ 3 of the critical parameter u_* of [8]. © 2008 Wiley Periodicals, Inc.     

On variants of the Johnson–Lindenstrauss lemma

The Johnson–Lindenstrauss lemma asserts that an n‐point set in any Euclidean space can be mapped to a Euclidean space of dimension k = O(ε^‐2 log n) so that all distances are preserved up to a multiplicative factor between 1 ? ε and 1 + ε. Known proofs obtain such a mapping as a linear map R ⁿ → R ^k with a suitable random matrix. We give a simple and self‐contained proof of a version of the Johnson–Lindenstrauss lemma that subsumes a basic versions by Indyk and Motwani and a version more suitable for efficient computations due to Achlioptas. (Another proof of this result, slightly different but in a similar spirit, was given independently by Indyk and Naor.) An even more general result was established by Klartag and Mendelson using considerably heavier machinery. Recently, Ailon and Chazelle showed, roughly speaking, that a good mapping can also be obtained by composing a suitable Fourier transform with a linear mapping that has a sparse random matrix M; a mapping of this form can be evaluated very fast. In their result, the nonzero entries of M are normally distributed. We show that the nonzero entries can be chosen as random ± 1, which further speeds up the computation. We also discuss the case of embeddings into R ^k with the ?₁ norm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Understanding preservation theorems,II

We present an exposition of much of Sections VI.3 and XVIII.3 from Shelah's book Proper and Improper Forcing. This covers numerous preservation theorems for countable support iterations of proper forcing, including preservation of the property “no new random reals over V ”, the property “reals of the ground model form a non‐meager set”, the property “every dense open set contains a dense open set of the ground model”, and preservation theorems related to the weak bounding property, the weak ^ωω ‐bounding property, and the property “the set of reals of the ground model has positive outer measure” (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

On samples of independent random vectors in spaces of infinitely increasing dimension

We study the asymptotic behavior of a set of random vectors ξ_i, i = 1,..., m, whose coordinates are independent and identically distributed in a space of infinitely increasing dimension. We investigate the asymptotics of the distribution of the random vectors, the consistency of the sets M _m⁽ⁿ⁾ = ξ₁,..., ξ_m and X _n^λ = x ∈ X _n: ρ(x) ≤ λn, and the mutual location of pairs of vectors. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1706–1711, December, 1998.     

The topological structure of scaling limits of large planar maps

We discuss scaling limits of large bipartite planar maps. If p≥2 is a fixed integer, we consider, for every integer n≥2, a random planar map M _n which is uniformly distributed over the set of all rooted 2p-angulations with n faces. Then, at least along a suitable subsequence, the metric space consisting of the set of vertices of M _n , equipped with the graph distance rescaled by the factor n ^-1/4, converges in distribution as n→∞ towards a limiting random compact metric space, in the sense of the Gromov–Hausdorff distance. We prove that the topology of the limiting space is uniquely determined independently of p and of the subsequence, and that this space can be obtained as the quotient of the Continuum Random Tree for an equivalence relation which is defined from Brownian labels attached to the vertices. We also verify that the Hausdorff dimension of the limit is almost surely equal to 4.