Asymptotic Analysis of the GI/M/ 1 /n Loss System as n Increases to Infinity

This paper provides the asymptotic analysis of the loss probability in the GI/M/1/n queueing system as n increases to infinity. The approach of this paper is alternative to that of the recent papers of Choi and Kim (2000) and Choi et al. (2000) and based on application of modern Tauberian theorems with remainder. This enables us to simplify the proofs of the results on asymptotic behavior of the loss probability of the abovementioned paper of Choi and Kim (2000) as well as to obtain some new results.     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Order and chaos in Hofstadter's Q(n) sequence

A number of observations are made on Hofstadter's integer sequence defined by Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), for n > 2, and Q(1) = Q(2) = 1. On short scales, the sequence looks chaotic. It turns out, however, that the Q(n) can be grouped into a sequence of generations. The k‐th generation has 2^k members that have “parents” mostly in generation k − 1 and a few from generation k − 2. In this sense, the sequence becomes Fibonacci type on a logarithmic scale. The variance of S(n) = Q(n) − n/2, averaged over generations, is ≅2^αk, with exponent α = 0.88(1). The probability distribution p*(x) of x = R(n) = S(n)/n^α, n ≫ 1, is well defined and strongly non‐Gaussian, with tails well described by the error function erfc. The probability distribution of x_m = R(n) − R(n − m) is given by p_m(x_m) = λ_m p*(x_m/λ_m), with λ_m → √2 for large m. © 1999 John Wiley & Sons, Inc.     

Bounded branching process and and/or tree evaluation

We study the tail distribution of supercritical branching processes for which the number of offspring of an element is bounded. Given a supercritical branching process {Z_n} with a bounded offspring distribution, we derive a tight bound, decaying super-exponentially fast as c increases, on the probability Pr[Z_n > cE(Z_n)], and a similar bound on the probability Pr[Z_n ≤ E(Z_n)/c] under the assumption that each element generates at least two offspring. As an application, we observe that the execution of a canonical algorithm for evaluating uniform AND/OR trees in certain probabilistic models can be viewed as a two-type supercritical branching process with bounded offspring, and show that the execution time of this algorithm is likely to concentrate around its expectation, with a standard deviation of the same order as the expectation.     

Achromatic Number of K 5 × K n for Small n

The achromatic number of a graph G is the maximum number of colours in a proper vertex colouring of G such that for any two distinct colours there is an edge of G incident with vertices of those two colours. We determine the achromatic number of the Cartesian product of K ₅ and K _n for all n ≤ 24.     

Representations of graphs modulo n

A graph is representable modulo n if its vertices can be labeled with distinct integers between 0 and n, the difference of the labels of two vertices being relatively prime to n if and only if the vertices are adjacent. Erd?s and Evans recently proved that every graph is representable modulo some positive integer. We derive a combinatorial formulation of representability modulo n and use it to characterize those graphs representable modulo certain types of integers, in particular integers with only two prime divisors. Other facets of representability are also explored. We obtain information about the values of n modulo which paths and cycles are representable.     

Universality for bounded degree spanning trees in randomly perturbed graphs

We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph G_α on n vertices with δ(G_α) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph G_α∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.     

Bi-invariant Integrals on GL(n) with Applications

In this paper measures and functions on GL(n) are called bi-invariant if they are invariant under left and right multiplication of their arguments. If v is any bi-invariant Borel measure on GL(n), then there exists a unique Borel measure v^* on D _{+ ≥}(n), the set of all diagonal matrices of rank n with positive non-increasing diagonal entries, such that holds for each v-integrable bi-invariant function f:GL(n) → IR. An explicit formula for v^* will be derived in case v equals the Lebesgue measure on GL(n) and the above integral formula will be applied to concrete integration problems. In particular, if v is a probability measure, then v^* can be interpreted as the distribution of the singular value vector. This fact will be used to derive a stochastic version of a theorem from perturbation theory concerning the numerical computation of the polar decomposition.     

The Ruelle-Sullivan map for actions of ℝ n

The Ruelle Sullivan map for an ℝⁿ-action on a compact metric space with invariant probability measure is a graded homomorphism between the integer Cech cohomology of the space and the exterior algebra of the dual of ℝⁿ. We investigate flows on tori to illuminate that it detects geometrical structure of the system. For actions arising from Delone sets of finite local complexity, the existence of canonical transversals and a formulation in terms of pattern equivariant functions lead to the result that the Ruelle Sullivan map is even a ring homomorphism provided the measure is ergodic.     

Twist–Rotation Transformations of Binary Trees and Arithmetic Expressions

The paper studies the computational complexity and efficient algorithms for the twist–rotation transformations of binary trees, which is equivalent to the transformation of arithmetic expressions over an associative and commutative binary operation. The main results are (1) a full binary tree with n labeled leaves can be transformed into any other in at most 3n log n + 2n twist and rotation operations, (2) deciding the twist–rotation distance between two binary trees is NP-complete, and (3) the twist–rotation transformation can be approximated with ratio 6 log n + 4 in polynomial time for full binary trees with n uniquely labeled leaves.     

The birth of the giant component

Limiting distributions are derived for the sparse connected components that are present when a random graph on n vertices has approximately 1/2n edges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching √2/3 cosh √5/18 ≈ 0.9325 as n→∞. The limiting probability that it is consists of trees, unicyclic components, and at most one another component is approximately 0.9957; the limiting probability that it is planar lies between 0.987 and 0.9998. When a random graph evolves and the number of edges passes 1/2n, its components grow in cyclic complexity according to an interesting Markov process whose asymptotic structure is derived. The probability that there never is more than a single component with more edges than vertices, throughout the veolution, approaches 5 π/18 ≈ 0.8727. A “uniform” model of random graphs, which allows self-loops and multiple edges, is shown to lead to formulas that are substanitially simpler than the analogous formulas for the classical random graphs of Erdõs and Rényi. The notions of “excess” and “deficiency,” which are significant characteristics of the generating function as well as of the graphs themselves, lead to a mathematically attractive structural theory for the uniform model. A general approach to the study of stopping configurations makes it possible to sharpen previously obtained estimates in a uniform manner and often to obtain closed forms for the constants of interest. Empirical results are presented to complement the analysis, indicating the typical behavior when n is near 2oooO. © 1993 John Wiley & Sons, Inc.     

On the probability that the determinant of an n x n matrix over a finite field vanishes

An expression is derived for the probability that the determinant of an n x n matrix over a finite field vanishes; from this it is deduced that for a fixed field this probability tends to 1 as n tends to ∞.     

Weighted isoperimetric inequalities on ℝn and applications to rearrangements

We study isoperimetric inequalities for a certain class of probability measures on ?ⁿ together with applications to integral inequalities for weighted rearrangements. Furthermore, we compare the solution to a linear elliptic problem with the solution to some “rearranged” problem defined in the domain {x: x₁ < α (x₂, …, x_n)} with a suitable function α (x₂, …, x_n). (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bijections for ternary trees and non-crossing trees

The number N_n of non-crossing trees of size n satisfies N_n+1=T_n where T_n enumerates ternary trees of size n. We construct a new bijection to establish that fact. Since , it follows that 3(3n−1)(3n−2)T_n−1=2n(2n+1)T_n. We construct two bijections “explaining” this recursion; one of them easily extends to the case of t-ary trees.     

Card shuffling and a transformation on S n

Summary We consider two card shuffling schemes. The first, which has appeared in the literature previously ([G], [RB], [T]), is as follows: start with a deck ofn cards, and pick a random tuplet { 1, 2, , n} ⁿ ; interchange cards 1 andt ₁, then interchange cards 2 andt ₂, etc. The second scheme, which can be viewed as a transformation on the symmetric groupS _n , is given by the restriction of the former shuffling scheme to tuplest which form a permutation of {1, 2,,n}.We determine the bias of each of these shuffling schemes with respect to the sets of transpositions and derangements, and the expected number of fixed points of a permutation generated by each of these shuffling schemes. For the latter scheme we prove combinatorially that the permutation which arises with the highest probability is the identity. The same question is open for the former scheme. We refute a candidate answer suggested by numerical evidence [RB].This work was carried out in part while R.S. was visiting the Institute for Mathematics and its Applications and was partly supported through NSF Grant CCR-8707539.     

On Beauville structures on the groups S n and A n

It is known that the symmetric group S _n , for n ≥ 5, and the alternating group A _n , for large n, admit a Beauville structure. In this paper we prove that A _n admits a Beauville (resp. strongly real Beauville) structure if and only if n ≥ 6 (resp n ≥ 7). We also show that S _n admits a strongly real Beauville structure for n ≥ 5.