A note on the connectivity of 2-regular digraphs

Let D ₂(n) be the probability space of 2-regular digraphs on n vertices with the uniform measure. As n tends to infinity, the probability that the digraphs are 2-connected tends to 1. © 1993 John Wiley & Sons, Inc.     

On irreducible characters of the group Sn that are semiproportional on An or Sn?An. II

In the author’s previous paper, the hypothesis that the alternating groups A _n have no pairs of semiproportional irreducible characters is reduced to a hypothesis concerning the problem of describing the pairs of irreducible characters of the symmetric group S _n that are semiproportional on one of the sets A _n or S _n ∖A _n . In this hypothesis, properties of such a pair of characters are expressed in terms of Young’s diagrams corresponding to these characters. The theorem proved in this paper allows one to exclude from consideration some stages of the verification of this hypothesis.     

Visible Vectors and Discrete Euclidean Medial Axis

We denote by ℳ _R ⁿ the test neighbourhood sufficient to extract the Euclidean Medial Axis of any n-dimensional discrete shape whose inner radius is no greater than R. In this paper, we study properties of discrete Euclidean disks overlappings so as to prove that in any given dimension n, ℳ _R ⁿ tends to the set of visible vectors as R tends to infinity.     

Normal limit theorems for symmetric random matrices

Using the machinery of zonal polynomials, we examine the limiting behavior of random symmetric matrices invariant under conjugation by orthogonal matrices as the dimension tends to infinity. In particular, we give sufficient conditions for the distribution of a fixed submatrix to tend to a normal distribution. We also consider the problem of when the sequence of partial sums of the diagonal elements tends to a Brownian motion. Using these results, we show that if O _n is a uniform random n×n orthogonal matrix, then for any fixed k>0, the sequence of partial sums of the diagonal of O ^k _n tends to a Brownian motion as n→∞. Received: 3 February 1998 / Revised version: 11 June 1998     

On the automorphism conjecture for products of ordered sets

I. Rival and A. Rutkowski conjectured that the ratio of the number of automorphisms of an arbitrary poset to the number of order-preserving maps tends to zero as the size of the poset tends to infinity. We prove this hypothesis for direct products of arbitrary posets P=S ₁××S _n under the condition that max_i|S_i|=0(n/logn).     

Character Formulas for q-Rook Monoid Algebras

The q-rook monoid R _n(q) is a semisimple (q)-algebra that specializes when q 1 to [R _n], where R _n is the monoid of n × n matrices with entries from {0, 1} and at most one nonzero entry in each row and column. We use a Schur-Weyl duality between R _n(q) and the quantum general linear group to compute a Frobenius formula, in the ring of symmetric functions, for the irreducible characters of R _n(q). We then derive a recursive Murnaghan-Nakayama rule for these characters, and we use Robinson-Schensted-Knuth insertion to derive a Roichman rule for these characters. We also define a class of standard elements on which it is sufficient to compute characters. The results for R _n(q) specialize when q = 1 to analogous results for R _n.     

The influence of non-commutativity on limit theorems

Summary We show that the distribution of the composition g ₁...g _nof random elements g ₁,...,g _nof the group SO(3) tends to the uniform distribution in far more general situations, than in the commutative case.     

The young diagrams of a pair of irreducible characters of S n with the same zero set on S n ?

In studying the pairs of irreducible characters of the symmetric group S _n with the same zero set on A _n or S _n ∖ A _n (as well as the pairs of irreducible characters with the same zero set on the alternating group A _n ), the results are important on the connection between the Young diagrams of the characters of these pairs. We prove a theorem that considerably generalizes two previous results of frequent use in this direction. Original Russian Text Copyright ? 2008 Belonogov V. A. The author was supported by the Russian Foundation for Basic Research (Grant 07-01-00148) and the RFBR-NSFC (Grant 05-01-39000). __________ Ekaterinburg. Translated from Sibirskiĭ Matematicheskiĭ Zhurnal, Vol. 49, No. 5, pp. 992–1006, September–October, 2008.     

A nearly degenerate random variable occurring in an occupancy problem

Letn distinguishable balls be placed randomly inton cells. IfM _n denotes the maximal number of balls falling into the same cell, it is shown that asymptoticallyM _n only attains two values: There is a sequencem _n of integers such thatP(M _n=m_n orM _n=m_n+1) tends to 1, asn.m _n is determined explicitly and asymptotically.     

On the convex hull of uniform random points in a simpled-polytope

Denote the expected number of facets and vertices and the expected volume of the convex hullP _n ofn random points, selected independently and uniformly from the interior of a simpled-polytope byE _n (f), E _n (v), andE _n (V), respectively. In this note we determine the sharp constants of the asymptotic expansion ofE _n (f), E _n (v), andE _n (V), asn tends to infinity. Further, some results concerning the expected shape ofP _n are given. The work of F. Affentranger was supported by the Swiss National Foundation.     

On the real roots of Euler polynomials

We show how are located the positive roots of the Euler polynomiale _n of degreen. We give an upper bound and a lower bound for the greatest root. This permits to determine an integerv _(n) such that the number of positive roots ofE _n is eitherv _(n) orv _(n) +2. We also study the behaviour of ther-th positive root ofE _n asn tends to infinity.     

The asymptotic distribution of leaf heights in binary trees

Let ℬ _n be the family of extended binary tress withn internal nodes and assume that eacht ∈ℬ _n has equal probability. We identify the asymptotic distribution of the height of leafi (where the leaves are enumerated from left to right) asi andn tend to infinity, such thati/n tends tox λ]0, 1[, as a Maxwell distribution. A generalization of the used combinatorial resp. probabilistic considerations is indicated.     

Irreducible products of characters inA n

We show that it is possible to find a pair of non-principal irreducible characters ofA _nwhose product is irreducible if and only ifn is a perfect square.     

Hamilton cycles in 3‐out

Let G_3‐out denote the random graph on vertex set [n] in which each vertex chooses three neighbors uniformly at random. Note that G_3‐out has minimum degree 3 and average degree 6. We prove that the probability that G_3‐out is Hamiltonian goes to 1 as n tends to infinity. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Zeta functions related to the group SL2(ℤ p )

An explicit formula is given for the number of subgroups of indexp ⁿ in the principle congruence subgroups of SL₂(ℤ _p ) (for odd primesp), and for the zeta function associated with the group. Asymptotically this number iscnp ⁿ , wherec is a constant depending on the congruence subgroup. Also, the zeta function of thei-th congruence subgroup coincides with the partial zeta function of the 3-generated subgroups of thei+1-th congruence subgroup, and for each indexp ⁿ the ratio between 2-generated subgroups and 3-generated subgroups tends top - 1:1, asn tends to infinity. This work is part of the author’s Ph.D. thesis carried out at the Hebrew University of Jerusalem under the supervision of Prof. A. Lubotzky. I wish to thank Prof. Lubotzky for his continual interest and encouragement without which this paper would not have been published.     

Complete Asymptotic Expansion for Generalized Favard Operators

In the present paper we consider a generalization _boxclose F_{n,\sigma_{n}} of the Favard operators and study the local rate of convergence for smooth functions. As a main result we derive the complete asymptotic expansion for the sequence ( F_n,snf)( x)( F_{n,\sigma _{n}}f)( x) as n tends to infinity. Furthermore, we consider a truncated version of these operators. Finally, all results were proved for simultaneous approximation.     

Criteria for Convergence of the Number of Near Maxima for Long Tails

Let M_n denote the maximum of a random sample of size n and K_n(a) be the number of near maxima, i.e. the number of sample observations in the fixed-width window (M_n – a, M_n]. There is a known integral criterion for almost sure convergence (to unity) of K_n(a), and we establish a similar criterion for complete convergence. We obtain simple but quite general sufficient conditions on the survivor function for satisfying the integral criteria. Further insight is obtained by seeking the rate at which P(K_n(a > 1)) tends to zero.AMS 2000 Subject Classification. 62G30, 60F15     

Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges

For a given convex body K in \Bbb R³{\Bbb R}^3 with C ² boundary, let P ^c _n be the circumscribed polytope of minimal volume with at most n edges, and let P ⁱ _n be the inscribed polytope of maximal volume with at most n edges. Besides presenting an asymptotic formula for the volume difference as n tends to infinity in both cases, we prove that the typical faces of P ^c _n and P ⁱ _n are asymptotically regular triangles and squares, respectively, in a suitable sense.     

On the central limit theorem in R p when p→∞

Summary Let X ₁ , X ₂ , ..., X _n be i.i.d. random vectors in R ^p where p tends to infinity. A theorem is presented showing that the Central Limit Theorem should hold if p ²/n tends to zero. Furthermore, an example is presented with X _i having a mixed multivariate normal distribution (with finite moment generating function) for which a uniform normal approximation to the distribution of the sample mean can not hold if p ²/n does not tend to zero. Research supported in part by National Science Foundation Grants MCS 80-02340, MCS 83-01834, and DMS 85-03785     

Some remarks about embeddings ofl 1 k in finite-dimensional spaces

The spanX _n of functionsx _i(t)=±1,i=1, …,n, on a setT in the supremum norm is considered. It is proved, for example, thatX _n contains an isometric copy ofl ₁ ^k fork≧cM _n ² /n logn whereM _n is the Rademacher average of {x _i} ₁ ⁿ . This generalizes a result of Pisier for characters. The proof uses a new combinatorial tool.