m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements

It is known that the joint distribution of the number of nodes of each type of an m‐ary search tree is asymptotically multivariate normal when m ≤ 26. When m ≥ 27, we show the following strong asymptotics of the random vector X_n = ^t(X, … , X), where X denotes the number of nodes containing i ? 1 keys after having introduced n ? 1 keys in the tree: There exist (nonrandom) vectors X, C, and S and random variables ρ and φ such that (X_n ? nX)/n ? ρ(C cos(τ₂log n + φ) + S sin(τ₂log n + φ)) →_n→∞ 0 almost surely and in L²; σ₂ and τ₂ denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Word maps and spectra of random graph lifts

We study here the spectra of random lifts of graphs. Let G be a finite connected graph, and let the infinite tree T be its universal cover space. If λ₁ and ρ are the spectral radii of G and T respectively, then, as shown by Friedman (Graphs Duke Math J 118 (2003), 19–35), in almost every n‐lift H of G, all “new” eigenvalues of H are ≤ O(λ ρ^1/2). Here we improve this bound to O(λ ρ^2/3). It is conjectured in (Friedman, Graphs Duke Math J 118 (2003) 19–35) that the statement holds with the bound ρ + o(1) which, if true, is tight by (Greenberg, PhD thesis, 1995). For G a bouquet with d/2 loops, our arguments yield a simple proof that almost every d‐regular graph has second eigenvalue O(d^2/3). For the bouquet, Friedman (2008). has famously proved the (nearly?) optimal bound of . Central to our work is a new analysis of formal words. Let w be a formal word in letters g,…,g. The word map associated with w maps the permutations σ₁,…,σ_k ∈ S_n to the permutation obtained by replacing for each i, every occurrence of g_i in w by σ_i. We investigate the random variable X that counts the fixed points in this permutation when the σ_i are selected uniformly at random. The analysis of the expectation ??(X) suggests a categorization of formal words which considerably extends the dichotomy of primitive vs. imprimitive words. A major ingredient of a our work is a second categorization of formal words with the same property. We establish some results and make a few conjectures about the relation between the two categorizations. These conjectures suggest a possible approach to (a slightly weaker version of) Friedman's conjecture. As an aside, we obtain a new conceptual and relatively simple proof of a theorem of A. Nica (Nica, Random Struct Algorithms 5 (1994), 703–730), which determines, for every fixed w, the limit distribution (as n →∞) of X. A surprising aspect of this theorem is that the answer depends only on the largest integer d so that w = u^d for some word u. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Law of large numbers for increasing subsequences of random permutations

Let the random variable Z_n,k denote the number of increasing subsequences of length k in a random permutation from S_n, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Finding blocks and other patterns in a random coloring of ℤ

Let ξ = (ξ_k)_k∈? be i.i.d. with P(ξ_k = 0) = P(ξ_k = 1) = 1/2, and let S: = (S_k) be a symmetric random walk with holding on ?, independent of ξ. We consider the scenery ξ observed along the random walk path S, namely, the process (χ_k := ξ). With high probability, we reconstruct the color and the length of blockⁿ, a block in ξ of length ≥ n close to the origin, given only the observations (χ_k). We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on blockⁿ and in the interval [?3ⁿ,3ⁿ]. Moreover, we reconstruct with high probability a piece of ξ of length of the order 3 around blockⁿ, given only 3 observations collected by the random walker starting on the boundary of blockⁿ. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Phase transition for Parking blocks,Brownian excursion and coalescence

In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n < m), and ? = m ? n empty places. For a noncomputer science‐minded reader, we shall use the metaphore of n cars parking on m places: each car c_i chooses a place p_i at random, and if p_i is occupied, c_i tries successively p_i + 1, p_i + 2, until it finds an empty place. Pittel [42] proves that when ?/m goes to some positive limit β < 1, the size B of the largest block of consecutive cars satisfies 2(β ? 1 ? log β)B = 2 log m ? 3 log log m + Ξ_m, where Ξ_m converges weakly to an extreme‐value distribution. In this paper we examine at which level for n a phase transition occurs between B = o(m) and m ? B = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 76–119, 2002     

Function Spaces with Exponential Weights II

This paper is a continuation of [8]. We study weighted function spaces of type B and F on the Euclidean space Rⁿ, where u is a weight function of at most exponential growth. In particular, u(χ (±|χ|) is an admissible weight. We deal with atomic decompositions of these spaces. Furthermore, we prove that the spaces B and F are isomorphic to the corresponding unweighted spaces B and F.     

Subgraphs smaller than the girth

For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k-node tree T, then for every k-node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.     

On the Lorentz-Marcinkiewicz Operator Ideal

This article deals with the LORENTZ-MARCINKIEWICZ operator ideal ?? generated by an additive s-function and the LORENTZ-MARCINKIEWICZ sequence space λ^q(φ). We give eigenvalue distributions for operators belonging to ?? (E, E) and we show the interpolation properties of ??-ideals. Furthermore, we study certain SCHAUDER bases in ?? (H, K), H and K Hilbert spaces.     

On restricted min‐wise independence of permutations

A family of permutations ℱ ⊆ S_n with a probability distribution on it is called k-restricted min-wise independent if we have Pr[min π(X) = π(x)] = 1/|X| for every subset X ⊆ [n] with |X| ≤ k, every x ∈ X, and π ∈ ℱ chosen at random. We present a simple proof of a result of Norin: every such family has size at least Some features of our method might be of independent interest. The best available upper bound for the size of such family is 1 + ∑ (j − 1)(). We show that this bound is tight if the goal is to imitate not the uniform distribution on S_n, but a distribution given by assigning suitable priorities to the elements of [n] (the stationary distribution of the Tsetlin library, or self-organizing lists). This is analogous to a result of Karloff and Mansour for k-wise independent random variables. We also investigate the cases where the min-wise independence condition is required only for sets X of size exactly k (where we have only an Ω(log log n + k) lower bound), or for sets of size k and k − 1 (where we already obtain a lower bound of n − k + 2). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Markov chains on hypercubes: Spectral representations and several majorization relations

Various Markov chains on hypercubes ??are considered and their spectral representations are presentend in terms of Kronecker products. Special attention is given to random walks on the graphs ??(l = 1,n ? 2), where the vertex set is ?? and two vertices are connected if and only if their Hamming distance is at most l. It is shown that λ(??₁)>λ(??₁)>λ(??_n?1)>λ(??_n),l=2,…,n?2, where λ (??_I) is the specturum of the random walk on ??I, and > denotes the majorization ordering. A similar majorization relation is established for graphs V₁ where two veritces are connected if and only if their Hamming distance is exactly l. Some applications to mean times of these random walks are given. © 1993 John Wiley & Sons, Inc.     

A new construction of perfect nonlinear functions using Galois rings

For a prime p, we give a construction of perfect nonlinear functions from ? to ? when either of the following conditions holds: (1) n≥p; (2) n<p, and n is a composite number or is the sum of positive composite numbers. It follows that when n≥12, there is a perfect nonlinear function from ? to ? for any prime p. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 229‐239, 2009     

On invariant measures of extensions of Markov transition functions

By using the LITTLEWOOD matrices A_2n we generalize CLARKSON' S inequalities, or equivalently, we determine the norms ‖A_2n: l(L_P) → l(L_P)‖ completely. The result is compared with the norms ‖A_2n: l → l‖, which are calculated implicitly in PIETSCH [6].     

Subelliptic Estimates for a Class of Degenerate Elliptic Integro-Differential Operators

In this paper we prove subelliptic estimates for operators of the form Δ_x + λ² (x)S in ?^N = ? × ?, where the operator S is an elliptic integro - differential operator in ?^N and λ is a nonnegative Lipschitz continuous function.     

The determining number of a Cartesian product

A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G=G□?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q_n)=?log₂n?+1 which matches the lower bound, and that Det(K)=?log₃(2n+1)?+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(Hⁿ)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory     

Resonance phenomena for a class of partial differential equations of higher order in cylindrical waveguides

We consider a domain Ω in ?ⁿ of the form Ω = ?^l × Ω′ with bounded Ω′ ? ?^n?l. In Ω we study the Dirichlet initial and boundary value problem for the equation ? u + [(? ? ?… ? ?)^m + (? ? ?… ? ?)^m]u = fe^?iωt. We show that resonances can occur if 2m ≥ l. In particular, the amplitude of u may increase like t^α (α rational, 0<α<1) or like in t as t∞∞. Furthermore, we prove that the limiting amplitude principle holds in the remaining cases.     

Uniform stability of spectral nonlinear Galerkin methods

This article provides a stability analysis for the backward Euler schemes of time discretization applied to the spatially discrete spectral standard and nonlinear Galerkin approximations of the nonstationary Navier‐Stokes equations with some appropriate assumption of the data (λ, u₀, f). If the backward Euler scheme with the semi‐implicit nonlinear terms is used, the spectral standard and nonlinear Galerkin methods are uniform stable under the time step constraint Δt ≤ (2/λλ₁). Moreover, if the backward Euler scheme with the explicit nonlinear terms is used, the spectral standard and nonlinear Galerkin methods are uniform stable under the time step constraints Δt = O(λ) and Δt = O(λ), respectively, where λ ≤ λ, which shows that the restriction on the time step of the spectral nonlinear Galerkin method is less than that of the spectral standard Galerkin method. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2004     

On the density of 2‐colorable 3‐graphs in which any four points span at most two edges

Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)$. We improve the previously best known lower and upper bounds of 0.25682 and 3/10?ε, respectively, by showing that This implies the following new upper bound for the Turán density of K In order to establish these results we use a combination of the properties of computer‐generated extremal 3‐graphs for small n and an argument based on “super‐saturation”. Our computer results determine the exact values of ex(n, K) for n≤19 and ex₂(n, K) for n≤17, as well as the sets of extremal 3‐graphs for those n. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105–114, 2010     

ITERATIONS OF SATISFACTION CLASSES AND MODELS OF PEANO ARITHMETIC

We consider iterations of satisfaction classes and apply them to construct expansions of models of Peano arithmetic to models of A|Δ+∑-AC. 1991 MSC: 03F35, 03C62.     

Über die Radon-Transformation kreissymmetrischer Funktionen und ihre Beziehung zur Sommerfeldschen Theorie der Hankelfunktionen

For the Radon transform of functions with circular symmetry an inversion formula is proved in a new and elementary way. The inversion formula combined with Fourier theory is applied to Sommer-feld's integral for H, yielding a representation of products which generalizes Nicholson's integral for |H| ².