On the perturbation of the Q‐factor of the QR factorization

This paper gives normwise and componentwise perturbation analyses for the Q‐factor of the QR factorization of the matrix A with full column rank when A suffers from an additive perturbation. Rigorous perturbation bounds are derived on the projections of the perturbation of the Q‐factor in the range of A and its orthogonal complement. These bounds overcome a serious shortcoming of the first‐order perturbation bounds in the literature and can be used safely. From these bounds, identical or equivalent first‐order perturbation bounds in the literature can easily be derived. When A is square and nonsingular, tighter and simpler rigorous perturbation bounds on the perturbation of the Q‐factor are presented. Copyright © 2011 John Wiley & Sons, Ltd.     

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.     

Class of tight bounds on the Q‐function with closed‐form upper bound on relative error

In this paper, we propose a novel class of parametric bounds on the Q‐function, which are lower bounds for 1 ≤ a < 3 and x > x_t = (a (a‐1) / (3‐a))^1/2, and upper bound for a = 3. We prove that the lower and upper bounds on the Q‐function can have the same analytical form that is asymptotically equal, which is a unique feature of our class of tight bounds. For the novel class of bounds and for each particular bound from this class, we derive the beneficial closed‐form expression for the upper bound on the relative error. By comparing the bound tightness for moderate and large argument values not only numerically, but also analytically, we demonstrate that our bounds are tighter compared with the previously reported bounds of similar analytical form complexity.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Linear Arboricity and Linear k-Arboricity of Regular Graphs

 We find upper bounds on the linear k-arboricity of d-regular graphs using a probabilistic argument. For small k these bounds are new. For large k they blend into the known upper bounds on the linear arboricity of regular graphs. Received: December 21, 1998 Final version received: July 26, 1999     

Automorphism groups of compact bordered Klein surfaces with invariant subsets

In this work we get upper bounds for the order of a group of automorphisms of a compact bordered Klein surface S of algebraic genus greater than 1. These bounds depend on the algebraic genus of S and on the cardinals of finite subsets of S which are invariant under the action of the group. We use our results to obtain upper bounds for the order of a group of automorphism whose action on the set of connected components of the boundary of S is not transitive. The bounds obtained this way depend only on the algebraic genus of S. The author is partially supported by the European Network RAAG HPRN-CT-2001-00271 and the Spanish GAAR DGICYT BFM2002-04797.     

Square function and heat flow estimates on domains

The first purpose of this note is to provide a proof of the usual square function estimate on L^p(Ω). It turns out to follow directly from a generic Mikhlin multiplier theorem obtained by Alexopoulos, and we provide a sketch of its proof in the Appendix for the reader’s convenience. We also relate such bounds to a weaker version of the square function estimate which is enough in most instances involving dispersive PDEs and relies on Gaussian bounds on the heat kernel (such bounds are the key to Alexopoulos’result as well). Moreover, we obtain several useful L^p(Ω;H) bounds for (the derivatives of) the heat flow with values in a given Hilbert space H.     

On the index of the Weierstrass semigroup of a pair of points on a curve

We obtain the exact formulas for the cardinality of the complement of the Weierstrass semigroup of a pair (p, q) of points on a curveC. Using these formulas we obtain lower bounds and upper bounds on the cardinalities of such sets. Moreover, considering examples, we show that these bounds are sharp.Partially supported by Korea Science and Engineering Foundation and by Global Analysis Research Center.     

Transience and capacity of minimal submanifolds

We prove explicit lower bounds for the capacity of annular domains of minimal submanifolds P ^m in ambient Riemannian spaces N ⁿ with sectional curvatures bounded from above. We characterize the situations in which the lower bounds for the capacity are actually attained. Furthermore we apply these bounds to prove that Brownian motion defined on a complete minimal submanifold is transient when the ambient space is a negatively curved Hadamard-Cartan manifold. The proof stems directly from the capacity bounds and also covers the case of minimal submanifolds of dimension m > 2 in Euclidean spaces.     

Global Error Bounds for <Emphasis Type="Italic">γ</Emphasis>-paraconvex Multifunctions

In this paper, error bounds for γ-paraconvex multifunctions are considered. A Robinson-Ursescu type Theorem is given in normed spaces. Some results on the existence of global error bounds are presented. Perturbation error bounds are also studied.     

Improving Hadamard's inequality *

We study several bounds for the determinant of an n × n positive definite Hermitian matrix A. These bounds are the best possible given certain data about A. We find the best bounds in the cases that we are given: (i) the diagonal elements of A: (ii) the traces trA,tr A ² and n and (iii)n, tr A tr A ² and the diagonal elements of A. In case (i) we get the well known Hadamard inequality. The other bounds are Hadamard type bounds. The bounds are found using optimization techniques.     

Lower bounds and upper bounds for chromatic polynomials

In this paper we give lower bounds and upper bounds for chromatic polynomials of simple undirected graphs on n vertices having m edges and girth exceeding g © 1993 John Wiley & Sons, Inc.     

Depths of Powers of the Edge Ideal of a Tree

Lower bounds are given for the depths of R/I ^t for t ≥ 1 when I is the edge ideal of a tree or forest. The bounds are given in terms of the diameter of the tree, or in case of a forest, the largest diameter of a connected component and the number of connected components. These lower bounds provide a lower bound on the power for which the depths stabilize.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

Packing vertices and edges in random regular graphs

In this paper we consider the problem of finding large collections of vertices and edges satisfying particular separation properties in random regular graphs of degree r, for each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the maximal sizes of these sets. The lower bounds are proved by analyzing a class of algorithms that return feasible solutions for the given problems. The analysis uses the differential equation method proposed by Wormald [Lectures on Approximation and Randomized Algorithms, PWN, Wassaw, 1999, pp. 239–298]. The upper bounds are proved by direct combinatorial means. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Bounding Ramsey numbers through large deviation inequalities

We develop a new approach for proving lower bounds for various Ramsey numbers, based on using large deviation inequalities. This approach enables us to obtain the bounds for the off-diagonal Ramsey numbers R(K^r, K^k), r ≤ k, that match the best known bounds, obtained through the local lemma. We discuss also the bounds for a related Ramsey-type problem and show, for example, that there exists a K⁴-free graph G on n vertices in which every cn^3/5 log^1/2 n vertices span a copy of K³. © 1995 John Wiley & Sons, Inc.     

Diagonal dominance characterization of <Emphasis Type="Italic">PM</Emphasis>-and <Emphasis Type="Italic">PH</Emphasis>-matrices

The paper presents new bounds for the inverses of the so-called PM- and PH-matrices. Also bounds for the spectral radii of the inverses to PM- and PH-matrices are obtained, and the monotonicity of these bounds with respect to the underlying partition of the index set is established. Finally, the so-called quasi-PM- and quasi-PH-matrices are introduced, and bounds for the inverses of such matrices are suggested. Bibliography: 10 titles.     

Linear Complexity of the Discrete Logarithm

We obtain new lower bounds on the linear complexity of several consecutive values of the discrete logarithm modulo a prime p. These bounds generalize and improve several previous results.     

Caps in finite projective spaces of odd order

In this paper upper bounds on the number of points of large complete caps in PG(n, q), (q odd,n3) are derived. The previously known bounds of Hirschfeld and Segre are improved using recent bounds on the cardinality of the second largest complete cap in the plane PG(2,q).Research of this author is supported by OTKA Grants Nos. 2505 and T-014105     

A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations

We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.