Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic

In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}.     

On the increments of the local time of a Wiener sheet

{W(x, y), x≥0, y≥0} be a Wiener process and let η(u, (x, y)) be its local time. The continuity of η in (x, y) is investigated, i.e., an upper estimate of the process η(μ, [x, x + α) × [y, y + β)) is given when αβ is small.     

On the 3-Torsion Part of the Homology of the Chessboard Complex

Let 1 ≤ m ≤ n. We prove various results about the chessboard complex M _m,n , which is the simplicial complex of matchings in the complete bipartite graph K _m,n . First, we demonstrate that there is nonvanishing 3-torsion in [(H)\tilde]_d(\sf M_m,n; \mathbb Z){{\tilde{H}_d({\sf M}_{m,n}; {\mathbb Z})}} whenever \fracm+n-43 ￡ d ￡ m-4{{\frac{m+n-4}{3}\leq d \leq m-4}} and whenever 6 ≤ m < n and d = m − 3. Combining this result with theorems due to Friedman and Hanlon and to Shareshian and Wachs, we characterize all triples (m, n, d ) satisfying [(H)\tilde]_d (\sf M_m,n; \mathbb Z) 1 0{{\tilde{H}_d \left({\sf M}_{m,n}; {\mathbb Z}\right) \neq 0}}. Second, for each k ≥ 0, we show that there is a polynomial f _k (a, b) of degree 3k such that the dimension of [(H)\tilde]_k+a+2b-2 (\sf M_{k+a+3b-1,k+2a+3b-1}; \mathbb Z₃){{\tilde{H}_{k+a+2b-2}}\,\left({{\sf M}_{k+a+3b-1,k+2a+3b-1}}; \mathbb Z_{3}\right)}, viewed as a vector space over \mathbbZ₃{\mathbb{Z}_3}, is at most f _k (a, b) for all a ≥ 0 and b ≥ k + 2. Third, we give a computer-free proof that [(H)\tilde]₂ (\sf M_5,5; \mathbb Z) @ \mathbb Z₃{{\tilde{H}_2 ({\sf M}_{5,5}; \mathbb {Z})\cong \mathbb Z_{3}}}. Several proofs are based on a new long exact sequence relating the homology of a certain subcomplex of M _m,n to the homology of M _m-2,n-1 and M _m-2,n-3.     

Nonparametric Empirical Bayes Estimation of the Matrix Parameter of the Wishart Distribution

We consider independent pairs (X₁, Σ₁), (X₂, Σ₂), …, (X_n, Σ_n), where eachΣ_iis distributed according to some unknown density functiong(Σ) and, givenΣ_i=Σ,X_ihas conditional density functionq(xΣ) of the Wishart type. In each pair the first component is observable but the second is not. After the (n+1)th observationX_n+1is obtained, the objective is to estimateΣ_n+1corresponding toX_n+1. This estimator is called the empirical Bayes (EB) estimator ofΣ. An EB estimator ofΣis constructed without any parametric assumptions ong(Σ). Its posterior mean square risk is examined, and the estimator is demonstrated to be pointwise asymptotically optimal.     

Changing and unchanging of the domination number of a graph

Let G be a graph and γ(G) denote the domination number of G. A dominating set D of a graph G with |D|=γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-fixed if x belongs to every γ-set, (ii) γ-free if x belongs to some γ-set but not to all γ-sets, (iii) γ-bad if x belongs to no γ-set, (iv) γ^--free if x is γ-free and γ(G-x)=γ(G)-1, (v) γ⁰-free if x is γ-free and γ(G-x)=γ(G), and (vi) γ^q-fixed if x is γ-fixed and γ(G-x)=γ(G)+q. In this paper we investigate for any vertex x of a graph G whether x is γ^q-fixed, γ⁰-free, γ^--free or γ-bad when G is modified by deleting a vertex or adding or deleting an edge.     

On the Uniformity of Distribution of the Elliptic Curve ElGamal Signature

We show that, under some natural conditions, the pairs (ρ, σ) produced by the elliptic curve ElGamal signature scheme are uniformly distributed. In particular, this implies that values of ρ and σ are not correlated. The result is based on some new estimates of exponential sums. For the ElGamal signature over a finite field, a similar result has been obtained by the second author.     

The asymptotic behavior of the solutions of the Cauchy problem generated by -accretive operators

The purpose of this paper is to study the asymptotic behavior of the solutions of certain type of differential inclusions posed in Banach spaces. In particular, we obtain the abstract result on the asymptotic behavior of the solution of the boundary value problem

where Ω is a bounded open domain in with smooth boundary ∂Ω, f(t,x) is a given L¹-function on ]0,∞[×Ω, γ1 and 1p<∞. Δ_p represents the p-Laplacian operator, is the associated Neumann boundary operator and β a maximal monotone graph in with 0β(0).     

Bootstrap of the offspring mean in the critical process with a non-stationary immigration

In applications of branching processes, usually it is hard to obtain samples of a large size. Therefore, a bootstrap procedure allowing inference based on a small sample size is very useful. Unfortunately, in the critical branching process with stationary immigration the standard parametric bootstrap is invalid. In this paper, we consider a process with non-stationary immigration, whose mean and variance vary regularly with nonnegative exponents α and β, respectively. We prove that 1+2α is the threshold for the validity of the bootstrap in this model. If β<1+2α, the standard bootstrap is valid and if β>1+2α it is invalid. In the case β=1+2α, the validity of the bootstrap depends on the slowly varying parts of the immigration mean and variance. These results allow us to develop statistical inferences about the parameters of the process in its early stages.     

Asymptotic distribution of the increase of the largest canonical correlation when one of the vectors is augmented

Let r₁ > r₂ > … be the sample canonical correlations in a sample of size n from a multivariate normal population partitioned into two subvectors with population canonical correlations ₁ > ₂ > …. Let one of the subvectors be augmented by adding one or more variables to it. For the increase in the largest canonical correlation, Δr in the sample and Δ in the population, it is shown that √n(Δr − Δ) → ^DN(0, σ²) and a formula for σ² is derived.     

On the approximate behavior of the posterior distribution for an extreme multivariate observation

The behavior of the posterior for a large observation is considered. Two basic situations are discussed; location vectors and natural parameters.Let X = (X₁, X₂, …, X_n) be an observation from a multivariate exponential distribution with that natural parameter Θ = (Θ₁, Θ₂, …, Θ_n). Let θ_x^* be the posterior mode. Sufficient conditions are presented for the distribution of Θ − θ_x^* given X = x to converge to a multivariate normal with mean vector 0 as |x| tends to infinity. These same conditions imply that E(Θ | X = x) − θ_x^* converges to the zero vector as |x| tends to infinity.The posterior for an observation X = (X₁, X₂, …, X_n is considered for a location vector Θ = (Θ₁, Θ₂, …, Θ_n) as x gets large along a path, γ, in Rⁿ. Sufficient conditions are given for the distribution of γ(t) − Θ given X = γ(t) to converge in law as t → ∞. Slightly stronger conditions ensure that γ(t) − E(Θ | X = γ(t)) converges to the mean of the limiting distribution.These basic results about the posterior mean are extended to cover other estimators. Loss functions which are convex functions of absolute error are considered. Let δ be a Bayes estimator for a loss function of this type. Generally, if the distribution of Θ − E(Θ | X = γ(t)) given X = γ(t) converges in law to a symmetric distribution as t → ∞, it is shown that δ(γ(t)) − E(Θ | X = γ(t)) → 0 as t → ∞.     

Pseudoprime values of the Fibonacci sequence, polynomials and the Euler function

We show that if α > 1 is any fixed integer, then for a sufficiently large x > 1, the nth Fibonacci number F_n is a base α pseudopfime only for at most (4 + o(1))π(x) of posifive integers n x. The same result holds for Mersenne numbers 2ⁿ — 1 and for one more general class of Lucas sequences. A slight modification of our method also leads to similar results for polynomial sequences f(n), where f ∊ [X]. Finally, we use a different technique to get a much sharper upper bound on the counting fimction of the positive integers n such that φ(n) is a base α pseudoprime, where φ is the Euler function.     

Adaptive Semiparametric Estimation of the Memory Parameter

In Giraitis, Robinson, and Samarov (1997), we have shown that the optimal rate for memory parameter estimators in semiparametric long memory models with degree of “local smoothness” β is n^−r(β), r(β)=β/(2β+1), and that a log-periodogram regression estimator (a modified Geweke and Porter-Hudak (1983) estimator) with maximum frequency m=m(β)n^2r(β) is rate optimal. The question which we address in this paper is what is the best obtainable rate when β is unknown, so that estimators cannot depend on β. We obtain a lower bound for the asymptotic quadratic risk of any such adaptive estimator, which turns out to be larger than the optimal nonadaptive rate n^−r(β) by a logarithmic factor. We then consider a modified log-periodogram regression estimator based on tapered data and with a data-dependent maximum frequency m=m(β), which depends on an adaptively chosen estimator β of β, and show, using methods proposed by Lepskii (1990) in another context, that this estimator attains the lower bound up to a logarithmic factor. On one hand, this means that this estimator has nearly optimal rate among all adaptive (free from β) estimators, and, on the other hand, it shows near optimality of our data-dependent choice of the rate of the maximum frequency for the modified log-periodogram regression estimator. The proofs contain results which are also of independent interest: one result shows that data tapering gives a significant improvement in asymptotic properties of covariances of discrete Fourier transforms of long memory time series, while another gives an exponential inequality for the modified log-periodogram regression estimator.     

Mappings of finite distortion: the degree of regularity

This paper investigates the self-improving integrability properties of the so-called mappings of finite distortion. Let K(x)1 be a measurable function defined on a domain ΩRⁿ, n2, and such that exp(βK(x))L_loc¹(Ω), β>0. We show that there exist two universal constants c₁(n),c₂(n) with the following property: Let f be a mapping in W_loc^1,1(Ω,Rⁿ) with |Df(x)|ⁿK(x)J(x,f) for a.e. xΩ and such that the Jacobian determinant J(x,f) is locally in L¹ log^−c₁(n)βL. Then automatically J(x,f) is locally in L¹ log^c₂(n)βL(Ω). This result constitutes the appropriate analog for the self-improving regularity of quasiregular mappings and clarifies many other interesting properties of mappings of finite distortion. Namely, we obtain novel results on the size of removable singularities for bounded mappings of finite distortion, and on the area distortion under this class of mappings.     

Omega result for the mean square of the Riemann zeta function

A recent method of Soundararajan enables one to obtain improved Ω-result for finite series of the form ∑_nf(n) cos (2πλ_nx+β) where 0≤λ₁≤λ₂≤. . . and β are real numbers and the coefficients f(n) are all non-negative. In this paper, Soundararajan’s method is adapted to obtain improved Ω-result for E(t), the remainder term in the mean-square formula for the Riemann zeta-function on the critical line. The Atkinson series for E(t) is of the above type, but with an oscillating factor (−1)ⁿ attached to each of its terms.     

A geometric proof of the combinatorial bounds for the number of optimal solutions for the Euclidean 2-center problem

We provide lower and upper bounds for γ(n), the number of optimal solutions for the two-center problem: “Given a set S of n points in the real plane, find two closed discs whose union contains all of the points such that the radius of the larger disc is minimized.”The main result of the paper shows the matching upper and lower bounds for the two-center problem and demonstrates that γ(n)=n.     

Bounding the Compression Loss of the FGK Algorithm

An important issue related to coding schemes is their compression loss. A simple measure ε of the compression loss due to a coding scheme different than Huffman coding is defined by ε = A_C − A_H where A_H is the average code length of a static Huffman encoding and A_C is the average code length of an encoding based on the compression scheme C. When the scheme C is the FGK algorithm, Vitter conjectured that ε ≤ K for some real constant K. Here, we use an amortized analysis to prove this conjecture. We show that ε < 2. Furthermore, we show through an example that our bound is asymptotically tight. This result explains the good performance of FGK that many authors have observed through practical experiments.     

On the Spectrum of Frobenius–Perron Operators

We prove more results on the spectrum of the Frobenius–Perron operator P: L¹ → L¹ associated with a nonsingular transformation S: X → X on a σ-finite measure space (X, Σ, μ).     

A simple proof of the uniqueness theorem in impedance tomography

Let·(σ(x)u)= 0 in D R³, where D is a bounded domain with a smooth boundary. Suppose that σ ≥ m> 0, σ H³(D), where H^ℓ is the Sobolev space. Let the set {u, σu_N} be given on Γ for all u H^3/2(Γ), where u_N is the normal derivative of u on Γ.     

Companions of the inequalities of Fejér--Jackson and Young

Summary Applications of some well-known theorems of Jackson and Young lead to the sharp inequalities -1<ⁿ_k-1Σ(cos(kx)+sin(kx))/k (n ≥1; 1<x<π) and -1/2Si(π)<ⁿ_k-1Σ(cos(kx)·sin(kx))/k (n ≥1; xЄR) We prove that the following counterpart is valid for all integers n ≥1 and real numbers xЄ (0, π): -3/2≤ⁿ_k-1Σ(cos(kx)-sin(kx))/k where the sign of equality holds if and only if n =2 and x = π /2.     

Tests for the mean direction of the Langevin distribution with large concentration parameter

In this paper we study the asymptotic behaviors of the likelihood ratio criterion (T_L^(s)), Watson statistic (T_W^(s)) and Rao statistic (T_R^(s)) for testing H_0s: μ (a given subspace) against H_1s: μ , based on a sample of size n from a p-variate Langevin distribution M_p(μ, κ) when κ is large. For the case when κ is known, asymptotic expansions of the null and nonnull distributions of these statistics are obtained. It is shown that the powers of these statistics are coincident up to the order κ⁻¹. For the case when κ is unknown, it is shown that T_R^(s) T_L^(s) T_W^(s) in their powers up to the order κ⁻¹.