On the insertion time of random walk cuckoo hashing

Cuckoo Hashing is a hashing scheme invented by pervious study of Pagh and Rodler. It uses d ≥ 2 distinct hash functions to insert n items into the hash table of size m = (1 + ε)n. In their original paper they treated d = 2 and m = (2 + ε)n. It has been an open question for some time as to the expected time for Random Walk Insertion to add items when d > 2. We show that if the number of hash functions d ≥ d_ε = O(1) then the expected insertion time is O(1) per item.     

Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs

For positive integers r>?, an r‐uniform hypergraph is called an ?‐cycle if there exists a cyclic ordering of its vertices such that each of its edges consists of r consecutive vertices, and such that every pair of consecutive edges (in the natural ordering of the edges) intersect in precisely ? vertices; such cycles are said to be linear when ?=1, and nonlinear when ?>1. We determine the sharp threshold for nonlinear Hamiltonian cycles and show that for all r>?>1, the threshold for the appearance of a Hamiltonian ?‐cycle in the random r‐uniform hypergraph on n vertices is sharp and given by for an explicitly specified function λ. This resolves several questions raised by Dudek and Frieze in 2011.10     

The stripping process can be slow: Part I

Given an integer k, we consider the parallel k‐stripping process applied to a hypergraph H: removing all vertices with degree less than k in each iteration until reaching the k‐core of H. Take H as : a random r‐uniform hypergraph on n vertices and m hyperedges with the uniform distribution. Fixing with , it has previously been proved that there is a constant such that for all m = cn with constant , with high probability, the parallel k‐stripping process takes iterations. In this paper, we investigate the critical case when . We show that the number of iterations that the process takes can go up to some power of n, as long as c approaches sufficiently fast. A second result we show involves the depth of a non‐k‐core vertex v: the minimum number of steps required to delete v from where in each step one vertex with degree less than k is removed. We will prove lower and upper bounds on the maximum depth over all non‐k‐core vertices.     

Sharp thresholds for constraint satisfaction problems and homomorphisms

We determine under which conditions certain natural models of random constraint satisfaction problems have sharp thresholds of satisfiability. These models include graph and hypergraph homomorphism, the (d,k,t)‐model, and binary constraint satisfaction problems with domain size three. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On k‐connectivity for a geometric random graph

For n points uniformly randomly distributed on the unit cube in d dimensions, with d≥2, let ρ_n (respectively, σ_n) denote the minimum r at which the graph, obtained by adding an edge between each pair of points distant at most r apart, is k‐connected (respectively, has minimum degree k). Then P[ρ_n=σ_n]→1 as n→∞. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 145–164, 1999     

Upper bounds on probability thresholds for asymmetric Ramsey properties

Given two graphs G and H, we investigate for which functions the random graph (the binomial random graph on n vertices with edge probability p) satisfies with probability that every red‐blue‐coloring of its edges contains a red copy of G or a blue copy of H. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which G and H are complete graphs of arbitrary size. In our proof we present an alternative to the so‐called deletion method, which was introduced by Rödl and Ruciński in their study of symmetric Ramsey properties of random graphs (i.e. the case G = H), and has been used in many proofs of similar results since then.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 1–28, 2014     

On the Number of Subgraphs of a Specified Form Embedded in a Random Graph

Let U ₁, U ₂,... be a sequence of i.i.d. random elements in R^d. For x>0, a graph G _n (x) may be formed by connecting with an edge each pair of points in that are separated by a distance no greater than x. The points of G _n (x) could represent the stations in a telecommunications network and the edge set the lines of communication that exist among them. Let be a collection of graphs on mn points having a specified form or structure, and let denote the number of subgraphs embedded in G _n (x) and contained in . It is shown that a SLLN, CLT and LIL for follow easily from the theory of U-statistics. In addition, a uniform (in x) SLLN is proved for collections that satisfy a certain monotonicity condition. Some applications are mentioned and the results of some simulations presented. The scaling constants appearing in the CLT are usually hard to obtain. These are worked out for some special cases.     

Sharp Growth Theorems and Coefficient Bounds for Starlike Mappings in Several Complex Variables

Let B be the unit ball in a complex Banach space. Let S^＊k＋1（B） be the family of normalized starlike mappings f on B such that z = 0 is a zero of order k ＋ 1 of f（z） - z. The authors obtain sharp growth and covering theorems, as well as sharp coefficient bounds for various subsets of S^＊k＋1（B）.     

一类近于凸映照子族精确的偏差定理

首先建立了C~n中单位多圆柱上一类近于凸映照子族精确的偏差定理,同时在复Banach空间单位球上也建立了该类映照精确的偏差定理的下界估计.其次在复Banach空间单位球上建立了准星形映照精确的偏差定理.所得结果将单复变中近于凸函数和星形函数的偏差定理推广至高维情形,并且对龚升提出的一个公开问题给出肯定的回答.     

Tight bounds for the vertices of degree k in minimally k‐connected graphs

For minimally k‐connected graphs on n vertices, Mader proved a tight lower bound for the number of vertices of degree k in dependence on n and k. Oxley observed 1981 that in many cases a considerably better bound can be given if is used as additional parameter, i.e. in dependence on m, n, and k. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long‐standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case.     

随机变量相等的一个充要条件

本文证得分布于有限区间上的随机变量相等的充要条件为其各阶原点矩相等．     

A self normalized law of the iterated logarithm for random walk in random scenery

LetX,X _i ,i1, be a sequence of i.i.d. random vectors in ^d . LetS _o=0 and, forn1, letS _n =X ₁+...+X _n . LetY,Y(), ^d , be i.i.d. -valued random variables which are independent of theX _i . LetZ _n =Y(S _o )+...+Y(S _n ). We will callZ _n arandom walk in random scenery.In this work, we consider the law of the iterated logarithm for random walk in random sceneries. Under fairly general conditions, we obtain arandomly normalized law of the iterated logarithm.Supported in part by NSF Grants DMS-85-21586 and DMS-90-24961.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

Multiple positive fixed points for the sum of expansive mappings and k‐set contractions

In this work, we are concerned with the existence of multiple positive fixed points for the sum of an expansive mapping with constant h > 1 and a k‐set contraction when 0 ≤ k < h ? 1. In particular, the case of the sum of an expansive mapping with constant h > 1 and an e‐concave operator and an e‐convex operator is considered. Two examples of application illustrate some of the theoretical results.     

随机向量自正则和的重对数律

本文给出了独立随机向量序列自正则和的重对数律成立的一个充分条件.     

On martingale tail sums for the path length in random trees

For a martingale (X_n) converging almost surely to a random variable X, the sequence (X_n– X) is called martingale tail sum. Recently, Neininger (Random Structures Algorithms 46 (2015), 346–361) proved a central limit theorem for the martingale tail sum of Régnier's martingale for the path length in random binary search trees. Grübel and Kabluchko (in press) gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane‐oriented recursive trees. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 493–508, 2017