Holes in random graphs

It is shown that for every >0 with the probability tending to 1 as n→∞ a random graph G(n,p) contains induced cycles of all lengths k, 3 ≤ k ≤ (1 − )n log c/c, provided c(n) = (n − 1)p(n)→∞.     

On an optimal stopping problem of Gusein-Zade

We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r=25, we give the limiting (as n→∞) optimal risk (probability of not selecting one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r=10, and for r=15, 20 and 25.) We show that, for large n and r, the optical risk is approximately (1−t^*)^r, where t^*≈0.2834 is obtained as the roof of a function which is the solution to a certain differential equation. The optimal stopping rule τ_r,n lets approximately t^*n arrivals go by and then stops ‘almost immediately’, in the sense that τ_r,n/n→t^* in probability as n→∞, r→∞     

Second-order asymptotics in level crossing for differences of renewal processes

We consider level crossing for the difference of independent renewal processes. Second-order expansions for the distribution function of the crossing time of level n are found, as n → ∞. As a by-product several other results on the difference process are found. The expected minimum of the difference process appears to play an important role in the analysis. This makes this problem essentially harder than the level crossing for the sum process which was studied earlier.     

L2-approximation of real-valued functions with interpolatory constraints

We construct the polynomial p_m,n^* of degree m which interpolates a given real-valued function f L²[a, b] at pre-assigned n distinct nodes and is the best approximant to f in the L₂-sense over all polynomials of degree m with the same interpolatory character. It is shown that the L₂-error p_m,n^* − f → 0 as m → ∞ if f C[a, b].     

Full quadrature sums for pth powers of polynomials with Freud weights

In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate

1 p < ∞, for every polynomial P of degree at most n + rn^1/3, where W² is a Freud weight such as exp(−¦x¦), > 1, λ_jn are the Christoffel numbers, x_jn are the zeros of the orthonormal polynomials for the weight W², and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξ_nn^1/3, where ξ_n → ∞ as n → ∞. Previous estimates could sum only over those x_jn with ¦x_jn¦ σx_1n, some fixed 0 < σ < 1.     

Asymptotics of a certain integral

The asymptotic behaviour for t → ∞ of ^∞₀ exp[tx–c(x)]dx is studied. The function c is positive and ′(x) → ∞ (x → ∞). Sufficient conditions on c are given in order that the method of Laplace is applicable.     

“Drawings since hit tables in lotteries” and a new multivariate geometric distribution

In number lotteries people choose r numbers out of s. Weekly published “drawings since hit tables” indicate how many drawings have taken place since each of the s numbers was last selected as a winning number. Among many lotto players, they enhance the widespread belief that numbers should be “due” if they have not come up for a long time. Under the assumptions of independence of the drawings and equiprobability of all possible combinations, the random s-vectors Y_n, n 1, of entries in a drawings since hit table after n drawings form a Markov chain. The limit distribution of Y_n as n → ∞ is a new multivariate generalization of the geometric distribution. The determination of the distribution of the maximum entry in a drawings since hit table within the first n draws of a lottery seems to be an open problem.     

A sufficient and necessary condition for an OWA bag mapping having the self-identity

A mapping ƒ : _n=1^∞Iⁿ → I is called a bag mapping having the self-identity if for every (x₁,…,x_n) ε _i=1^∞Iⁿ we have (1) ƒ(x₁,…,x_n) = ƒ(x_i1,…,x_in) for any arrangement (i₁,…,i_n) of {1,…,n}; monotonic; (3) ƒ(x₁,…,x_n, ƒ(x₁,…,x_n)) = ƒ(x₁,…,x_n). Let {ω_i,n : I = 1,…,n;n = 1,2,…} be a family of non-negative real numbers satisfying Σ_i=1ⁿω_i,n = 1 for every n. Then one calls the mapping ƒ : _i=1^∞Iⁿ → I defined as follows an OWA bag mapping: for every (x₁,…,x_n) ε _i=1^∞Iⁿ, ƒ(x₁,…,x_n) = Σ_i=1ⁿω_i,ny_i, where y_i is the it largest element in the set {x₁,…,x_n}. In this paper, we give a sufficient and necessary condition for an OWA bag mapping having the self-identity.     

Embedding complete trees into the hypercube

We consider embeddings of the complete t-ary trees of depth k (denotation T^k,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(T^k,t), is known if max{k,t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(T^k,3)2k+1 up to lim_k→∞dim(T^k,3)/k5/3 and show lim_t→∞dim(T^3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(T^k,t) for arbitrary k and t.     

Krylov subspace methods for eigenvalues with special properties and their analysis for normal matrices

In this paper we propose a general approach by which eigenvalues with a special property of a given matrix A can be obtained. In this approach we first determine a scalar function ψ: C → C whose modulus is maximized by the eigenvalues that have the special property. Next, we compute the generalized power iterations uinj + 1 = ψ(A)u_j, j = 0, 1,…, where u₀ is an arbitrary initial vector. Finally, we apply known Krylov subspace methods, such as the Arnoldi and Lanczos methods, to the vector u_n for some sufficiently large n. We can also apply the simultaneous iteration method to the subspace span{x⁽ⁿ⁾₁,…,x⁽ⁿ⁾_k} with some sufficiently large n, where x^(j+1)_m = ψ(A)x^(j)_m, j = 0, 1,…, m = 1,…, k. In all cases the resulting Ritz pairs are approximations to the eigenpairs of A with the special property. We provide a rather thorough convergence analysis of the approach involving all three methods as n → ∞ for the case in which A is a normal matrix. We also discuss the connections and similarities of our approach with the existing methods and approaches in the literature.     

On a question about sum-free sequences

An increasing sequence of positive integers {n₁, n₂, …} is called a sum-free sequence if every term is never a sum of distinct smaller terms. We prove that there exist sum-free sequences {n_k} with polynomial growth and such that lim_k→∞ n_k+1/n_k = 1.     

Some peculiar boundary phenomena for extremes of rth nearest neighbor links

Let D_n,r denote the largest rth nearest neighbor link for n points drawn independently and uniformly from the unit d-cube C_d. We show that according as r < d or r>d, the limiting behavior of D_n,r, as n → ∞, is determined by the two-dimensional ‘faces’ respectively one-dimensional ‘edges’ of the boundary of C_d. If d = r, a ‘balance’ between faces and edges occurs. In case of a d-dimensional sphere (instead of a cube) the boundary dominates the asymptotic behavior of D_n,r if d 3 or if d = 2, r 3.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Limit laws for the number of near maxima via the Poisson approximation

Given a sequence of i.i.d. random variables, new proofs are given for limit theorems for the number of observations near the maximum up to time n, as n → ∞. The proofs rely on a Poisson approximation to conditioned binomial laws, and they reveal the origin in the limit laws of mixing with respect to extreme value laws. For the case of attraction to the Fréchet law, the effects of relaxing a technical condition are examined. The results are set in the broader context of counting observations near upper order statistics. This involves little extra effort.     

The game of n-times nim

The following game is considered. The first player can take any number of stones, but not all the stones, from a single pile of stones. After that, each player can take at most n-times as many as the previous one. The player first unable to move loses and his opponent wins. Let f₁,f₂,… be an initial sequence of stones in increasing order, such that the second player has a winning strategy when play begins from a pile of size f_i. It is proved that there exist constants c=c(n) and k₀=k₀(n) such that f_k+1=f_k+f_k−c for all k>k₀, and lim_n→∞ c(n)/(nlogn)=1.     

The connectivity of a graph on uniform points on [0,1]

A random graph G_n(x) is constructed on independent random points U₁,…,U_n distributed uniformly on [0,1]^d, d1, in which two distinct such points are joined by an edge if the l_∞-distance between them is at most some prescribed value 0<x<1. The connectivity distance c_n, the smallest x for which G_n(x) is connected, is shown to satisfy

(1)

For d2, the random graph G_n(x) behaves like a d-dimensional version of the random graphs of Erdös and Rényi, despite the fact that its edges are not independent: c_n/d_n→1, a.s., as n→∞, where d_n is the largest nearest-neighbor link, the smallest x for which G_n(x) has no isolated vertices.     

On some properties of the series ∑k=0 kx and the Stirling numbers of the second kind

We partially characterize the rational numbers x and integers n 0 for which the sum ∑_k=0^∞ kⁿx^k assumes integers. We prove that if ∑_k=0^∞ kⁿx^k is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where v_a(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.

New identities are also derived for the Stirling numbers, e.g., we show that ∑_k=0²ⁿk! S(2n, k) , for all integers n 1.     

The existence of moments of the conditioned limit of the subcritical Crump-Mode-Jagers branching process

If Z (t) is the sum of the characteristics at time t of the population in a Crump-Mode-Jagers branching process, and T is the time to extinction, it is known that under certain conditions, the distribution of Z (t) conditioned on {T > t} converges to a proper distribution as t→∞. We derive necessary and sufficient conditions in terms of the offspring process, for the existence of integral moments of this limit distribution.     

A shortcut to asymptotics for orthogonal polynomials

We consider the asymptotic behavior of the ratios q_n+1(z)/q_n(z) of polynomials orthonormal with respect to some positive measure μ. Let the recurrence coefficients _n and β_n converge to 0 and , respectively. Then, q_n+1(z)/q_n(z) Φ(z),for n→∞ locally uniformly for , where Φ maps conformally onto the exterior of the unit disc (Nevai (1979)). We provide a new and direct proof for this and some related results due to Nevai, and apply it to convergence acceleration of diagonal Padé approximants.     

Between local and global logarithmic averages

We obtain an approximation for the logarithmic averages of I{k^1/2a(k) S(k) k^1/2b(k)}, where a(k) → 0, b(k) → 0 (k → ∞) and S(k) is partial sum of independent, identically distributed random variables.