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 p-intersection representations

For a graph G = (V,E) and integer p, a p-intersection representation is a family F = {S_x: × E V} of subsets of a set S with the property that |S_u ∩ S_ν| ≥ p ∩ {u, ν} E E. It is conjectured in [1] that θ_p(G) ≤ θ (K_n/2,n/2) (1 + o(1)) holds for any graph with n vertices. This is known to be true for p = 1 by [4]. In [1], θ (K_n/2,n/2) ≥ (n² + (2p− 1n)n)/4p is proved for any n and p. Here, we show that this is asymptotically best possible. Further, we provide a bound on θp(G) for all graphs with bounded degree. In particular, we prove θp(G) ≤ O(n^1/p) for any graph Gwith the maximum degree bounded by a constant. Finally, we also investigate the value of θ_p for trees. Improving on an earlier result of M. Jacobson, A. Kézdy, and D. West, (The 2-intersection number of paths and bounded-degree trees, preprint), we show that θ₂(T) ≤ O(d√n) for any tree T with maximum-degree d and θ₂(T) ≤ O(n^3/4) for any tree on n vertices. We conjecture that our results can be further improved and that θ₂(T) ≤ O(d√n) as long as Δ(T) ≤ √n. If this conjecture is true, our method gives θ₂(T) ≤ O(n^3/4) for any tree T which would be the best possible. © 1996 John Wiley & Sons, Inc.     

How quadratic are the natural numbers?

Abstract. For natural numbers n we inspect all factorizations n = ab of n with a ￡ ba \le b in \Bbb N\Bbb N and denote by n=a_n b_nn=a_n b_n the most quadratic one, i.e. such that b_n - a_nb_n - a_n is minimal. Then the quotient k(n) : = a_n/b_n\kappa (n) := a_n/b_n is a measure for the quadraticity of n. The best general estimate for k(n)\kappa (n) is of course very poor: 1/n ￡ k(n) ￡ 11/n \le \kappa (n)\le 1. But a Theorem of Hall and Tenenbaum [1, p. 29], implies(logn)^-d-e ￡ k(n) ￡ (logn)^-d(\log n)^{-\delta -\varepsilon } \le \kappa (n) \le (\log n)^{-\delta } on average, with d = 1 - (1+log₂  2)/log2=0,08607 ?\delta = 1 - (1+\log _2 \,2)/\log 2=0,08607 \ldots and for every e > 0\varepsilon >0. Hence the natural numbers are fairly quadratic.¶k(n)\kappa (n) characterizes a specific optimal factorization of n. A quadraticity measure, which is more global with respect to the prime factorization of n, is k^*(n): = ?_{1 ￡ a ￡ b, ab=n} a/b\kappa ^*(n):= \textstyle\sum\limits \limits _{1\le a \le b, ab=n} a/b. We show k^*(n) ~ \frac 12\kappa ^*(n) \sim \frac {1}{2} on average, and k^*(n)=W(2^{\frac 12(1-e) log n/log ₂n})\kappa ^*(n)=\Omega (2^{\frac {1}{2}(1-\varepsilon ) {\log}\, n/{\log} _2n})for every e > 0\varepsilon>0.     

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn^{1-(v_H-2)/(e_H-1)}(logn)^1/(e_H-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K _r,r with r≥5. When H is a complete graph K _s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn^2/(s+1)(logn)^1-1/(e_H-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.     

Blow up of subcritical quantities at the first singular time of the mean curvature flow

Consider a family of smooth immersions F(·,t) : Mⁿ? \mathbbRⁿ⁺¹{F(\cdot,t)\,:\,{M^n\to \mathbb{R}^{n+1}}} of closed hypersurfaces in \mathbbRⁿ⁺¹{\mathbb{R}^{n+1}} moving by the mean curvature flow \frac?F(p,t)?t = -H(p,t)·n(p,t){\frac{\partial F(p,t)}{\partial t} = -H(p,t)\cdot \nu(p,t)}, for t ? [0,T){t\in [0,T)}. We show that at the first singular time of the mean curvature flow, certain subcritical quantities concerning the second fundamental form, for example ò₀^tò_Ms\frac|A|^{n + 2} log (2 + |A|) dmds,{\int_{0}^{t}\int_{M_{s}}\frac{{\vert{\it A}\vert}^{n + 2}}{ log (2 + {\vert{\it A}\vert})}} d\mu ds, blow up. Our result is a log improvement of recent results of Le-Sesum, Xu-Ye-Zhao where the scaling invariant quantities were considered.     

Joint asymptotic distribution of exceedances point process and partial sum of stationary Gaussian sequence

Let {X _i } _i=1^∞ be a standardized stationary Gaussian sequence with covariance function r(n) = EX ₁ X _n+1, S _n = Σ _i=1 ⁿ X _i , and $\bar X_n = \tfrac{{S_n }} {n} $\bar X_n = \tfrac{{S_n }} {n} . And let N _n be the point process formed by the exceedances of random level $(\tfrac{x} {{\sqrt {2\log n} }} + \sqrt {2\log n} - \tfrac{{\log (4\pi \log n)}} {{2\sqrt {2\log n} }})\sqrt {1 - r(n)} + \bar X_n $(\tfrac{x} {{\sqrt {2\log n} }} + \sqrt {2\log n} - \tfrac{{\log (4\pi \log n)}} {{2\sqrt {2\log n} }})\sqrt {1 - r(n)} + \bar X_n by X ₁,X ₂,…, X _n . Under some mild conditions, N _n and S _n are asymptotically independent, and N _n converges weakly to a Poisson process on (0,1].     

Absolutely convergent fourier series. An improvement of the Beurling-Helson theorem

We consider the space A(\mathbbT)A(\mathbb{T}) of all continuous functions f on the circle \mathbbT\mathbb{T} such that the sequence of Fourier coefficients [^(f)] = { [^(f)]( k ), k ? \mathbbZ }\hat f = \left\{ {\hat f\left( k \right), k \in \mathbb{Z}} \right\} belongs to l ¹(ℤ). The norm on A(\mathbbT)A(\mathbb{T}) is defined by || f ||_A(\mathbbT) = || [^(f)] ||_{l¹ (\mathbbZ)}\left\| f \right\|_{A(\mathbb{T})} = \left\| {\hat f} \right\|_{l^1 (\mathbb{Z})}. According to the well-known Beurling-Helson theorem, if f:\mathbbT ? \mathbbT\phi :\mathbb{T} \to \mathbb{T} is a continuous mapping such that || e^inf ||_A(\mathbbT) = O(1)\left\| {e^{in\phi } } \right\|_{A(\mathbb{T})} = O(1), n ∈ ℤ then φ is linear. It was conjectured by Kahane that the same conclusion about φ is true under the assumption that || e^inf ||_A(\mathbbT) = o( log| n | )\left\| {e^{in\phi } } \right\|_{A(\mathbb{T})} = o\left( {\log \left| n \right|} \right). We show that if $\left\| {e^{in\phi } } \right\|_{A(\mathbb{T})} = o\left( {\left( {{{\log \log \left| n \right|} \mathord{\left/ {\vphantom {{\log \log \left| n \right|} {\log \log \log \left| n \right|}}} \right. \kern-\nulldelimiterspace} {\log \log \log \left| n \right|}}} \right)^{1/12} } \right)$\left\| {e^{in\phi } } \right\|_{A(\mathbb{T})} = o\left( {\left( {{{\log \log \left| n \right|} \mathord{\left/ {\vphantom {{\log \log \left| n \right|} {\log \log \log \left| n \right|}}} \right. \kern-\nulldelimiterspace} {\log \log \log \left| n \right|}}} \right)^{1/12} } \right), then φ is linear.     

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.     

Orlicz-Hardy spaces and their duals

We establish the theory of Orlicz-Hardy spaces generated by a wide class of functions.The class will be wider than the class of all the N-functions.In particular,we consider the non-smooth atomic decomposition.The relation between Orlicz-Hardy spaces and their duals is also studied.As an application,duality of Hardy spaces with variable exponents is revisited.This work is different from earlier works about Orlicz-Hardy spaces H(Rn)in that the class of admissible functions is largely widened.We can deal with,for example,(r)≡(rp1(log(e+1/r))q1,0r 6 1,rp2(log(e+r))q2,r1,with p1,p2∈(0,∞)and q1,q2∈(.∞,∞),where we shall establish the boundedness of the Riesz transforms on H(Rn).In particular,is neither convex nor concave when 0p11p2∞,0p21p1∞or p1=p2=1 and q1,q20.If(r)≡r(log(e+r))q,then H(Rn)=H(logH)q(Rn).We shall also establish the boundedness of the fractional integral operators I of order∈(0,∞).For example,I is shown to be bounded from H(logH)1./n(Rn)to Ln/(n.)(log L)(Rn)for 0n.     

Estimating the distance to a monotone function

In standard property testing, the task is to distinguish between objects that have a property 𝒫 and those that are ε‐far from 𝒫, for some ε > 0. In this setting, it is perfectly acceptable for the tester to provide a negative answer for every input object that does not satisfy 𝒫. This implies that property testing in and of itself cannot be expected to yield any information whatsoever about the distance from the object to the property. We address this problem in this paper, restricting our attention to monotonicity testing. A function f : {1,…,n} ↦ R is at distance ε_f from being monotone if it can (and must) be modified at ε_fn places to become monotone. For any fixed δ > 0, we compute, with probability at least 2/3, an interval [(1/2 − δ)ε,ε] that encloses ε_f. The running time of our algorithm is O(ε_f⁻¹ log log ε_f^{− 1} log n), which is optimal within a factor of loglog ε_f⁻¹ and represents a substantial improvement over previous work. We give a second algorithm with an expected running time of O(ε_f⁻¹ log nlog log log n). Finally, we extend our results to multivariate functions. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

The complexity and depth of Boolean circuits for multiplication and inversion in some fields <Emphasis Type="Italic">GF</Emphasis>(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

Let n = (p − 1) · p ^k , where p is a prime number such that 2 is a primitive root modulo p, and 2 ^p−1 − 1 is not a multiple of p ². For a standard basis of the field GF(2 ⁿ ), a multiplier of complexity O(log log p)n log n log log _p n and an inverter of complexity O(log p log log p)n log n log log _p n are constructed. In particular, in the case p = 3 the upper bound

On Approximate Spectral Factorization of Matrix Functions

It is proved that if positive definite matrix functions (i.e. matrix spectral densities) S _n , n=1,2,… , are convergent in the L ₁-norm, ||S_n-S||_L1? 0\|S_{n}-S\|_{L_{1}}\to 0, and ò₀^2plogdetS_n(e^iq) dq?ò₀^2plogdetS(e^iq) dq\int_{0}^{2\pi}\log \mathop{\mathrm{det}}S_{n}(e^{i\theta})\,d\theta\to\int_{0}^{2\pi}\log \mathop{\mathrm{det}}S(e^{i\theta})\,d\theta, then the corresponding (canonical) spectral factors are convergent in L ₂, ||S⁺_n-S⁺||_L2? 0\|S^{+}_{n}-S^{+}\|_{L_{2}}\to 0. The formulated logarithmic condition is easily seen to be necessary for the latter convergence to take place.     

Asymptotic normality of H-L estimators based on dependent data

LetX ₁,X ₂, ... be a strictly stationary φ-mixing sequence of r.v.'s with a common continuous cdfF. Let θ be a location parameter ofF. We prove the asymptotic normality of a class of Hodges-Lehmann estimators of θ under various regularity conditions on the mixing number φ and the underlyingF. We also establish the asymptotic linearity of signed rank statistics in the parameter θ. Our results also enable us to study the effect of φ-dependence on the asymptotic power of signed rank tests for testingH ₀: θ=0 againstH _n :θ=θ ₀ n ^?1/2,θ ₀≠0. Finally these results are shown to remain valid for strongly mixing processes {X _i } also.     

Precise asymptotics in Chung’s law of the iterated logarithm

Let X, X1, X2,... be i.i.d, random variables with mean zero and positive, finite variance σ^2, and set Sn = X1 ＋... ＋ Xn, n≥1. The author proves that, if EX^2I{｜X｜≥t} = 0（（log log t）^-1） as t→∞, then for any a〉-1 and b〉 -1,lim ε↑1/√1＋a（1/√1＋a-ε）b＋1 ∑n=1^∞（logn）^a（loglogn）^b/nP{max κ≤n｜Sκ｜≤√σ^2π^2n/8loglogn（ε＋an）}=4/π（1/2（1＋a）^3/2）^b＋1 Г（b＋1）,whenever an = o（1/log log n）. The author obtains the sufficient and necessary conditions for this kind of results to hold.     

The Boundedness of Monge-Ampère Singular Integral Operators

We first define molecules for Hardy spaces H¹_F(\mathbbRⁿ)H^{1}_{\mathcal{F}}(\mathbb{R}^{n}) associated with a family F\mathcal{F} of sections which is closely related to the Monge-Ampère equation and prove their molecular characters. As an application, we show that Monge-Ampère singular operators are bounded on H¹_F(\mathbbRⁿ)H^{1}_{\mathcal{F}}(\mathbb{R}^{n}).     

Internal geometry of hypersurfaces in projectively metric space

In this paper, we study the internal geometry of a hypersurface V _n−1 embedded in a projectively metric space K _n , n ≥ 3, and equipped with fields of geometric-objects { G_nⁱ,G_i } \left\{ {G_n^i,{G_i}} \right\} and { H_nⁱ,G_i } \left\{ {H_n^i,{G_i}} \right\} in the sense of Norden and with a field of a geometric object { H_nⁱ,H_n } \left\{ {H_n^i,{H_n}} \right\} in the sense of Cartan. For example, we have proved that the projective-connection space P _n−1,n−1 induced by the equipment of the hypersurface V_{n - 1}   ì   K_n,  n 3 3 {V_{n - 1}}\; \subset \;{K_n},\;n \geq 3 , in the sense of Cartan with the field of a geometrical object { H_nⁱ,H_n } \left\{ {H_n^i,{H_n}} \right\} is flat if and only if its normalization by the field of the object { H_nⁱ,G_i } \left\{ {H_n^i,{G_i}} \right\} in the tangent bundle induces a Riemannian space R _n−1 of constant curvature K = −1/c.     

Precise Rates in the Law of Iterated Logarithm for the Moment of I.I.D. Random Variables

Let{X,Xn;n≥1} be a sequence of i,i.d, random variables, E X = 0, E X^2 = σ^2 〈 ∞.Set Sn=X1＋X2＋…＋Xn,Mn=max k≤n│Sk│,n≥1.Let an=O（1/loglogn）.In this paper,we prove that,for b〉-1,lim ε→0 →^2（b＋1）∑n=1^∞ （loglogn）^b/nlogn n^1/2 E{Mn-σ（ε＋an）√2nloglogn}＋σ2^-b/（b＋1）（2b＋3）E│N│^2b＋3∑k=0^∞ （-1）k/（2k＋1）^2b＋3 holds if and only if EX=0 and EX^2=σ^2〈∞.     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

Some finitely additive versions of the strong law of large numbers

LetX be a non-empty set,H= X{su\t8, \gs = \lj{in1}x\lj{in2}x,σ=γ ₁×γ ₂×… be an independent strategy onH, and {Y _n} be a sequence of coordinate mappings onH. The following strong law in a finitely additive setting is proved: For some constantr≧1, if \GS _n=1 ^\t8 {\GS(\vbY _n \vb^2r )n ¹⁺ⁿ < \t8 andσ(Y _n)=0 for alln=1, 2, …, then \1n\gS{inj-1}/{sun} Y{inj}Y _jconverges to 0 withσ-measure 1 asn → ∞. The theorem is a generalization of Chung’s strong law in a coordinate representation process. Finally, Kolmogorov’s strong law in a finitely additive setting is proved by an application of the theorem. This research was based in part on the author’s doctoral dissertation submitted to the University of Minnesota, and was written with the partial support of the United States Army Grant DA-ARO-D-31-124-70-G-102.     

The cores of random hypergraphs with a given degree sequence

We study random r‐uniform n vertex hypergraphs with fixed degree sequence d = (d₁…,d_n), maximum degree Δ = o(n^1/24) and total degree θn, where θ is bounded. We give the size, number of edges and degree sequence of the κ ≥ 2) up to a whp error of O(n^2/3 Δ^4/3 log n). In the case of graphs (r = 2) we give further structural details such as the number of tree components and, for the case of smooth degree sequences, the size of the mantle. We give various examples, such as the cores of r‐uniform hypergraphs with a near Poisson degree sequence, and an improved upper bound for the first linear dependence among the columns in the independent column model of random Boolean matrices. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 25, 2004