Uniform recursive trees: Branching structure and simple random downward walk

As models for spread of epidemics, family trees, etc., various authors have used a random tree called the uniform recursive tree. Its branching structure and the length of simple random downward walk (SRDW) on it are investigated in this paper. On the uniform recursive tree of size n, we first give the distribution law of ζn,m, the number of m-branches, whose asymptotic distribution is the Poisson distribution with parameter . We also give the joint distribution of the numbers of various branches and their covariance matrix. On Ln, the walk length of SRDW, we first give the exact expression of P(Ln=2). Finally, the asymptotic behavior of Ln is given.     

The structure and distances in Yule recursive trees

Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Y_t is isomorphic to a given rooted tree γ; and then prove that the asymptotic distribution of ζ_t,m, the number of the branches of size m, is the Poisson distribution with parameter λ = 1/m. Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On weak asymptotic isomorphy of memoryless correlated sources

Let {(X _i,Z _i)} be an i.i.d. sequence of random pairs in a finite set × x ℒ; we will call it a discrete memoryless stationary correlated (DMSC) source with generic distribution dist(X ₁,Z ₁). Two DMSC sources {(X _i,Z _i)} and {(X _i′,Z _i′)} are called asymptotically isomorphic in the weak sense if for every ε>0 and sufficiently largen, there exists a joint distribution dist(X ⁿ,Z ⁿ,X′ ⁿ,Z′ ⁿ) ofn-length blocks of the two sources such that . For single sources of equal entropy, McMillan’s theorem implies asymptotic isomorphy in the sense suggested by this definition. For correlated sources, however, no nontrivial cases of weak asymptotic isomorphy are known. We show that some spectral properties of the generic distributions are invariant for weak asymptotic isomorphy, and these properties wholly determine the generic distribution in many cases.     

Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.

Consider the random graph on n vertices 1,…,n. Each vertex i is assigned a type x_i with x₁,…,x_n being independent identically distributed as a nonnegative random variable X. We assume that EX³< ∞. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability \begin{align*}\min \{1, \frac{x_ix_j}{n}\left(1+\frac{a}{n^{1/3}} \right) \}\end{align*}. We study the critical phase, which is known to take place when EX² = 1. We prove that normalized by n^‐2/3the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient \begin{align*}\sqrt{{\textbf{ E}}X{\textbf{ E}}X^3}\end{align*}and drift \begin{align*}a-\frac{{\textbf{ E}}X^3}{{\textbf{ E}}X}s\end{align*}. In particular, we conclude that the size of the largest connected component is of order n^2/3. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486–539, 2013     

Note on the heights of random recursive trees and random m-ary search trees

A process of growing a random recursive tree T_n is studied. The sequence {T_n} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T_n is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)^?1, where γe^1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m-ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union-find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.     

On a paper of Hasse concerning the Eisenstein reciprocity law

In the present paper, necessary and sufficient conditions are given for the equality of the power rezidue symbols ( \fracaa )_n {\left( {\frac{\alpha }{a}} \right)_n} and ( \fracaa )_n {\left( {\frac{\alpha }{a}} \right)_n} in the cyclotomic field ℚ(ζ _n ), 2 ∤ n, for a ∈ ℤ, (a, n) = 1. This result is a generalization of the classical Eisenstein reciprocity law and its continuation in a Hasse’s paper. Bibliography: 3 titles.     

Generalization for Laplacian energy

Let G be a simple graph with n vertices and m edges. Let λ1, λ2,…, λn, be the adjacency spectrum of G, and let μ1, μ2,…, μn be the Laplacian spectrum of G. The energy of G is E（G） = n∑i=1｜λi｜, while the Laplacian energy of G is defined as LE（G） = n∑i=1｜μi-2m/n｜ Let γ1, γ2, ~ …, γn be the eigenvalues of Hermite matrix A. The energy of Hermite matrix as HE（A） = n∑i=1｜γi-tr（A）/n｜ is defined and investigated in this paper. It is a natural generalization of E（G） and LE（G）. Thus all properties about energy in unity can be handled by HE（A）.     

Reduction of symmetric semidefinite programs using the regular \ast-representation

We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix $*$ -representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It implies that cr(K _8,n ) ≥ 2.9299n ² ? 6n, cr(K _9,n ) ≥ 3.8676n ² ? 8n, and (for any m ≥ 9) $$\lim_{n\to\infty}\frac{{\rm cr}(K_{m,n})}{Z(m,n)}\geq 0.8594\frac{m}{m-1},$$ where Z(m,n) is the Zarankiewicz number $\lfloor\frac{1}{4}(m-1)^2\rfloor\lfloor\frac{1}{4}(n-1)^2\rfloor$ , which is the conjectured value of cr(K _m,n ). Here the best factor previously known was 0.8303 instead of 0.8594.     

Depth Properties of scaled attachment random recursive trees

We study depth properties of a general class of random recursive trees where each node i attaches to the random node \begin{align*}\left\lfloor iX_i\right\rfloor\end{align*} and X₀,…,X_n is a sequence of i.i.d. random variables taking values in [0,1). We call such trees scaled attachment random recursive trees (sarrt). We prove that the typical depth D_n, the maximum depth (or height) H_n and the minimum depth M_n of a sarrt are asymptotically given by D_n ～μ^‐1 log n, H_n ～ α_max log n and M_n ～ α_min log n where μ,α_max and α_min are constants depending only on the distribution of X₀ whenever X₀ has a density. In particular, this gives a new elementary proof for the height of uniform random recursive trees H_n ～ elog n that does not use branching random walks.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

On the Crossing Number of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> □ <Emphasis Type="Italic">P</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(K_m □ P_n), the crossing number of the Cartesian product K_m □ P_n. We prove that for m ≥ 3,n ≥ 1 and cr(K_m □ P_n)≥ (n − 1)cr(K_m+2 − e) + 2cr(K_m+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr(K₆ □ P_n) = 15n + 3. Research supported by NFSC (60373096, 60573022).     

On the rate of convergence of the expected spectral distribution function of a Wigner matrix to the semi-circular law

Let X:= (X _jk ) denote a Hermitian random matrix with entries X _jk which are independent for all 1 ≤ j ≤ k. We study the rate of convergence of the expected spectral distribution function of the matrix X to the semi-circular law under the conditions E X _jk = 0, E X _jk ² = 1, and E|X _jk |^2+η ≤ M _η < ∞, 0 < η ≤ 2. The bounds of order $ O(n^{ - \frac{\eta } {{2 + \eta }}} ) $ O(n^{ - \frac{\eta } {{2 + \eta }}} ) for 1 ≤ η ≤ 2, and those of order $ O(n^{ - \frac{{2\eta }} {{(2 + \eta )(3 - \eta )}}} ) $ O(n^{ - \frac{{2\eta }} {{(2 + \eta )(3 - \eta )}}} ) for 0 < η ≤ 1, are obtained.     

A Poisson * Negative Binomial Convolution Law for Random Polynomials over Finite Fields

Let F _q[X] denote a polynomial ring over a finite field F _q with q elements. Let 𝒫_n be the set of monic polynomials over F _q of degree n. Assuming that each of the qⁿ possible monic polynomials in 𝒫_n is equally likely, we give a complete characterization of the limiting behavior of P(Ω_n=m) as n→∞ by a uniform asymptotic formula valid for m≥1 and n−m→∞, where Ω_n represents the number (multiplicities counted) of irreducible factors in the factorization of a random polynomial in 𝒫_n. The distribution of Ω_n is essentially the convolution of a Poisson distribution with mean log n and a negative binomial distribution with parameters q and q⁻¹. Such a convolution law exhibits three modes of asymptotic behaviors: when m is small, it behaves like a Poisson distribution; when m becomes large, its behavior is dominated by a negative binomial distribution, the transitional behavior being essentially a parabolic cylinder function (or some linear combinations of the standard normal law and its iterated integrals). As applications of this uniform asymptotic formula, we derive most known results concerning P(Ω_n=m) and present many new ones like the unimodality of the distribution. The methods used are widely applicable to other problems on multiset constructions. An extension to Rényi's problem, concerning the distribution of the difference of the (total) number of irreducibles and the number of distinct irreducibles, is also presented. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 17–47, 1998     

Algorithms for Producing and Ordering Lexical and Nonlexical Sequences out of One Element

This paper deals with algorithms for producing and ordering lexical and nonlexical sequences of a given degree. The notion of “elementary operations” on positive α-sequences is introduced. Our main theorem answers the question of when two lexical sequences are adjacent. Given any lexical sequence, α ∈ L _n , we can produce its adjacent successor as follows; apply one elementary operation on the tail of the longest left sequence, of even length, which gives a lexical successor α′ ∈ L _n , then compute the fundamental sequence f = aùa￠ ? L_m{f = \alpha \wedge \alpha\prime \in L_{m}} and conclude for m \nmid n{m \nmid n} that α is adjacent to α′ in L _n . Whereas for m | n, the sequence α is adjacent to a sequence by f and the least element of L _d , where d = \fracnm{{d = \frac{n}{m}}}. Thus, while right sequences control the lexicality property of an α-sequence, it turns out that left sequences control the adjacency property of lexical and nonlexical sequences.     

The impact of poles on the convergence of best rational approximants

The convergence behavior of best uniform rational approximants r _n,m ^* with numerator degree n and denominator degree m on a compact set E is investigated for functions f continuous on E and ray sequences above the diagonal of the Walsh table, i. e. sequences {n,m(n)} _n=1^∞ with

On the Number of Genus Embeddings of Complete Bipartite Graphs

In this paper, on the basis of joint tree model introduced by Liu, by dividing the associated surfaces into segments layer by layer, we show that there are at least ${C_{1}\cdot C_{2}^{\frac{m}{2}}\cdot C_{3}^{\frac{n}{2}}(m-1)^{m-\frac{1}{2}}(n-1)^{n-\frac{1}{2}}}$ distinct genus embeddings for complete bipartite graph K _m,n , where C ₁, C ₂, and C ₃ are constants depending on the residual class of m modular 4 and that of n modular 4.     

Metric results on the approximation of zero by linear combinations of independent and of dependent rationals

We give some “rational analoga” to metric results in the classical theory of the diophantine approximation of zero by linear forms. That is: we study the behaviour of expressions of the form $$\begin{gathered} \lim _{m \to \infty } \frac{1}{{\left| {P_s (m)} \right|}}|\{ (x_1 , \ldots ,x_s ) \in P_s (m): \hfill \\ \parallel a_1 \frac{{x_1 }}{m} + \ldots + a_s \frac{{x_s }}{m}\parallel _m \geqslant \psi (a_1 , \ldots ,a_s ,m) \hfill \\ for all - \frac{m}{2}< a_1 , \ldots ,a_s \leqslant \frac{m}{2}, \hfill \\ with (a_1 , \ldots ,a_s ) \ne (0, \ldots ,0)\} |, \hfill \\ \end{gathered} $$ whereP _s (m) is a certain subset of {1, …,m} ^s , ψ is a certain nonnegative function, and ‖ · ‖ _m means the maximum of 1/m and the distance to the nearest integer. Some of the investigations are also motivated by problems in the theory of uniform distribution and of pseudo-random number generation. The results partly depend on the validity of the generalized Riemann hypothesis.     

On Schwarzian Triangle Functions,Automorphic Forms and a Generalization of Ramanujan’s Triple Differential Equations

Let G be the group of the fractional linear transformations generated by

$$T(\tau ) = \tau + \lambda ,S(\tau ) = \frac{{\tau \cos \frac{\pi }{n} + \sin \frac{\pi }{n}}}{{ - \tau \sin \frac{\pi }{n} + \cos \frac{\pi }{n}}};$$

where

$$\lambda = 2\frac{{\cos \frac{\pi }{m} + \cos \frac{\pi }{n}}}{{\sin \frac{\pi }{n}}};$$

m, n is a pair of integers with either n ≥ 2,m ≥ 3 or n ≥ 3,m ≥ 2; τ lies in the upper half plane H.

A fundamental set of functions f₀, f_i and f_∞ automorphic with respect to G will be constructed from the conformal mapping of the fundamental domain of G. We derive an analogue of Ramanujan’s triple differential equations associated with the group G and establish the connection of f₀, f_i and f_∞ with a family of hypergeometric functions.     

Analytic and Asymptotic Properties of Multivariate Generalized Linnik’s Probability Densities

This paper studies the properties of the probability density function p _α,ν,n (x) of the n-variate generalized Linnik distribution whose characteristic function φ _α,ν,n (t) is given by

Small deviations of modified sums of independent random variables

Let S_n = X₁ + · · · + X _n , n ≥ 1, and S ₀ = 0, where X ₁, X ₂, . . . are independent, identically distributed random variables such that the distribution of S _n/B _n converges weakly to a nondeoenerate distribution F _α as n → ∞ for some positive B _n . We study asymptotic behavior of sums of the form

Estimates of the capacity of orthogonal arrays of large strength

D.G. Fon-Der-Flaass showed that Boolean correlation-immune n-variable functions of order m are resilient for $ m \geqslant \frac{{2n - 2}} {3} $ m \geqslant \frac{{2n - 2}} {3} . In this paper this theorem is generalized to orthogonal arrays. It is shown that orthogonal arrays of strength m not less than $ \frac{{2n - 2}} {3} $ \frac{{2n - 2}} {3} , where n is a number of factors having size at least 2 ⁿ⁻¹ and all arrays of size 2 ⁿ⁻¹, are simple.