Generalized moments of additive functions

Elliott's generalization of the Turán-Kubilius inequality is further generalized by establishing an upper bound for the sum Σ_n≤xF(∣f(n) ? A∣), where f is a complex-valued additive arithmetical function, A an arbitrary number and F an arbitrary nonnegative-valued increasing function. A connected problem for group-valued functions is also considered.     

On the domination number of the generalized Petersen graphs

Graph domination numbers and algorithms for finding them have been investigated for numerous classes of graphs, usually for graphs that have some kind of tree-like structure. By contrast, we study an infinite family of regular graphs, the generalized Petersen graphs G(n). We give two procedures that between them produce both upper and lower bounds for the (ordinary) domination number of G(n), and we conjecture that our upper bound ⌈3n/5⌉ is the exact domination number. To our knowledge this is one of the first classes of regular graphs for which such a procedure has been used to estimate the domination number.     

Uniform approximation by some Hermite interpolating splines

In this paper some upper bound for the error ∥ s-f ∥_∞ is given, where f ε C¹[a,b], but s is a so-called Hermite spline interpolant (HSI) of degree 2q ?1 such that f(x_i) = s(x_i), f′(rmx_i) = s′(x_i), s^(j) (x_i) = 0 (i = 0, 1, …, n; j = 2, 3, …, q ?1; n > 0, q > 0) and the knots x_i are such that a = x₀ < x₁ < … < x_n = b. Necessary and sufficient conditions for the existence of convex HSI are given and upper error bound for approximation of the function fε C¹[a, b] by convex HSI is also given.     

Estimates for a solution to one differential inequality

In a domain D = Ω × (?T,T) we consider a differential inequality whose left-hand side contains a linear second-order hyperbolic operator with coefficients depending only on x ∈ ? ⁿ, n ≥ 2, and the right-hand side contains the modulus of the gradient of the sought function. We supplement the inequality with the Cauchy data on the lateral part of the boundary of D and consider the problem of estimating a solution to the differential inequality satisfying the Cauchy data. We establish the estimate under some assumptions that involves the upper bound of the sectional curvatures of the Riemannian space associated with the differential operator, the Riemannian diameter of Ω, and the length of the interval (?T,T). The result is generalized to the case of compact domains bounded from above and below by characteristic surfaces.     

An asymptotic property of gap series. III

Takahashi [4] gave a concrete upper bound estimate of the law of the iterated logarithm for Σf(n _k x). We extend this result and prove the best possibility of this bound.     

Tight bounds on the spectral radius of asymmetric nonnegative matrices

For an arbitrary asymmetric nonnegative n × n matrix A we identify a pair of symmetric matrices whose largest eigenvalues bound the spectral radius of A. Furthermore, we show that these bounding matrices are best possible by characterizing matrices A which attain equality with either the upper or the lower bounding matrix. The lower bound may be extended to some matrices with negative entries provided they have no negative cycles.     

Markov-Bernstein inequalities for generalized Gegenbauer weight

The Markov-Bernstein inequalities for generalized Gegenbauer weight are studied. A special basis of the vector space Pn of real polynomials in one variable of degree at most equal to n is proposed. It is produced by quasi-orthogonal polynomials with respect to this generalized Gegenbauer measure. Thanks to this basis the problem to find the Markov-Bernstein constant is separated in two eigenvalue problems. The first has a classical form and we are able to give lower and upper bounds of the Markov-Bernstein constant by using the Newton method and the classical qd algorithm applied to a sequence of orthogonal polynomials. The second is a generalized eigenvalue problem with a five diagonal matrix and a tridiagonal matrix. A lower bound is obtained by using the Newton method applied to the six term recurrence relation produced by the expansion of the characteristic determinant. The asymptotic behavior of an upper bound is studied. Finally, the asymptotic behavior of the Markov-Bernstein constant is O(n²) in both cases.     

The equivariant LS-category of polar actions

We will provide a lower bound for arbitrary proper actions in terms of the stratification by orbit types, and an upper bound for proper polar actions in terms of the equivariant LS-category of its generalized Weyl group. As an application we reprove a theorem of Singhof that determines the classical Lusternik-Schnirelmann category for U(n) and SU(n).     

On Dirichlet's approximation theorem

Though we cannot improve on the upper bound in Dirichlet's approximation theorem,Kaindl has shown that the upper bound can be lowered fromt ⁿ tot ⁿ ?t ^n?1?t ^n?2?...?t?1, if we admit equality. We show thatKaindl's upper bound is lowest possible in this case. The result is then generalized to linear forms.     

The Kth largest eigenvalue of a tree

Let λ_k(T) be the kth eigenvalue of a tree, [x] the largest integer not greater than x. It is shown that a tree with n vertices has λ_k(T)⩽√[(n-2)/k] for 2⩽k⩽[n/2], and this upper bound is best possible for n≡1 mod k.     

Note on upper bound graphs and forbidden subposets

In the upper bound graph of a poset P, the vertex set is V(P) and xy is an edge if there exists an m∈V(P) with x,y≤_Pm. We show some characterizations on split upper bound graphs, threshold upper bound graphs and difference upper bound graphs in terms of m-subposets and canonical posets.     

A note on Stewart's theorem for definite matrix pairs

Let A and B be n×n Hermitian matrices. The matrix pair (A, B) is called definite pair and the corresponding eigenvalue problem βAx = αBx is definite if c(A, B) ≡ inf_{6x6= 1}{|^H(A+iB)x|} > 0. In this note we develop a uniform upper bound for differences of corresponding eigenvalues of two definite pairs and so improve a result which is obtained by G.W. Stewart [2]. Moreover, we prove that this upper bound is a projective metric in the set of n × n definite pairs.     

Code constructions and existence bounds for relative generalized Hamming weight

The relative generalized Hamming weight (RGHW) of a linear code C and a subcode C ¹ is an extension of generalized Hamming weight. The concept was firstly used to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. It was also applied to the wiretap network II for secrecy control of network coding and to trellis-based decoding algorithms for complexity estimation. For RGHW, bounds and code constructions are two related issues. Upper bounds on RGHW show the possible optimality for the applications, and code constructions meeting upper bounds are for designing optimal schemes. In this article, we show indirect and direct code constructions for known upper bounds on RGHW. When upper bounds are not tight or constructions are hard to find, we provide two asymptotically equivalent existence bounds about good code pairs for designing suboptimal schemes. Particularly, most code pairs (C, C ¹) are good when the length n of C is sufficiently large, the dimension k of C is proportional to n and other parameters are fixed. Moreover, the first existence bound yields an implicit lower bound on RGHW, and the asymptotic form of this existence bound generalizes the usual asymptotic Gilbert–Varshamov bound.     

Approximating Fixed Points of Weakly Contracting Mappings

We consider the problem of approximating fixed points of contractive functions whose contraction factor is close to 1. In a previous paper (1993, K. Sikorski et al., J. Complexity9, 181–200), we proved that for the absolute error criterion, the upper bound on the number of function evaluations to compute ε-approximations is O(n³(ln(1/ε)+ln(1/(1−q))+ln n)) in the worst case, where 0<q<1 is the contraction factor in the Euclidean norm and n is the dimension of the problem. This upper bound is achieved by the circumscribed ellipsoid (CE) algorithm combined with a dimensional deflation process. In this paper we present an inscribed ellipsoid (IE) algorithm that enjoys O(n(ln(1/ε)+ln(1/(1−q)))) bound. For q close to 1, the IE algorithm thus runs in many fewer iterations than the simple iteration method, that requires ⌈ln(1/ε)/ln(1/q)⌉ function evaluations. Our analysis also implies that: (1) The dimensional deflation procedure in the CE algorithm is not necessary and that the resulting “plain” CE algorithm enjoys O(n²(log(1/ε)+log(1/(1−q)))) upper bound on the number of function evaluations. (2) The IE algorithm solves the problem in the residual sense, i.e., computes x such that 6f(x)−x6⩽δ, with O(n ln(1/δ)) function evaluations for every q⩽1.     

An upper bound on the number of high-dimensional permutations

What is the higher-dimensional analog of a permutation? If we think of a permutation as given by a permutation matrix, then the following definition suggests itself: A d-dimensional permutation of order n is an n×n×...×n=[n] ^d+1 array of zeros and ones in which every line contains a unique 1 entry. A line here is a set of entries of the form {(x ₁,...,x _i?1,y,x _i+1,...,x _d+1)|n≥y≥1} for some index d+1≥i≥1 and some choice of x _j ∈ [n] for all j ≠ i. It is easy to observe that a one-dimensional permutation is simply a permutation matrix and that a two-dimensional permutation is synonymous with an order-n Latin square. We seek an estimate for the number of d-dimensional permutations. Our main result is the following upper bound on their number $$\left( {(1 + o(1))\frac{n} {{e^d }}} \right)^{n^d } .$$ We tend to believe that this is actually the correct number, but the problem of proving the complementary lower bound remains open. Our main tool is an adaptation of Brégman’s [1] proof of the Minc conjecture on permanents. More concretely, our approach is very close in spirit to Schrijver’s [11] and Radhakrishnan’s [10] proofs of Brégman’s theorem.     

Upper bounds for permanents of (1, − 1)-matrices

Let Ω _n denote the set of alln×n (1, ? 1)-matrices. In 1974 E. T. H. Wang posed the following problems: Is there a decent upper bound for |perA| whenAσΩ _n is nonsingular? We recently conjectured that the best possible bound is the permanent of the matrix with exactlyn?1 negative entries in the main diagonal, and affirmed that conjecture by the study of a large class of matrices in Ω _n . Here we prove that this conjecture also holds for another large class of (1, ?1)-matrices which are all nonsingular. We also give an upper bound for the permanents of a class of matrices in Ω _n which are not all regular.     

An improved upper bound in the maximum dispersal problem

For integral? m?2, let x₁,…, x_m be any unit vectors in R_n, the real Euclidean space of n dimensions. We obtain an upper bound for the quantity min_i≠j|x_i-x_j| which, though not as simple, is uniformly sharper than one recently obtained by the author. The result has application to the so-called maximum-dispersal problem, an open problem recently popularized by Klee.     

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

The threshold degree of a function f: {0,1} ⁿ → {?1,+1} is the least degree of a real polynomial p with f(x) ≡ sgnp(x). We prove that the intersection of two halfspaces on {0,1} ⁿ has threshold degree Ω(n), which matches the trivial upper bound and solves an open problem due to Klivans (2002). The best previous lower bound was Ω({ie73-1}). Our result shows that the intersection of two halfspaces on {0,1} ⁿ only admits a trivial {ie73-2}-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas.     

The minimum span of L(2,1)-labelings of certain generalized Petersen graphs

In the classical channel assignment problem, transmitters that are sufficiently close together are assigned transmission frequencies that differ by prescribed amounts, with the goal of minimizing the span of frequencies required. This problem can be modeled through the use of an L(2,1)-labeling, which is a function f from the vertex set of a graph G to the non-negative integers such that |f(x)-f(y)|? 2 if xand y are adjacent vertices and |f(x)-f(y)|?1 if xand y are at distance two. The goal is to determine the λ-number of G, which is defined as the minimum span over all L(2,1)-labelings of G, or equivalently, the smallest number k such that G has an L(2,1)-labeling using integers from {0,1,…,k}. Recent work has focused on determining the λ-number of generalized Petersen graphs (GPGs) of order n. This paper provides exact values for the λ-numbers of GPGs of orders 5, 7, and 8, closing all remaining open cases for orders at most 8. It is also shown that there are no GPGs of order 4, 5, 8, or 11 with λ-number exactly equal to the known lower bound of 5, however, a construction is provided to obtain examples of GPGs with λ-number 5 for all other orders. This paper also provides an upper bound for the number of distinct isomorphism classes for GPGs of any given order. Finally, the exact values for the λ-number of n-stars, a subclass of the GPGs inspired by the classical Petersen graph, are also determined. These generalized stars have a useful representation on Möebius strips, which is fundamental in verifying our results.     

A bound on the generalized competition index of a primitive matrix using Boolean rank

For a positive integer m where 1?m?n, the m-competition index (generalized competition index) of a primitive digraph is the smallest positive integer k such that for every pair of vertices x and y, there exist m distinct vertices v₁,v₂,…,v_m such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. The m-competition index is a generalization of the scrambling index and the exponent of a primitive digraph. In this study, we determine an upper bound on the m-competition index of a primitive digraph using Boolean rank and give examples of primitive Boolean matrices that attain the bound.