On the structure of small strength‐2 covering arrays

A covering array $\text{CA}\left(N;t,k,v\right)$ of strength $t$ is an $N\times k$ array of symbols from an alphabet of size $v$ such that in every $N\times t$ subarray, every $t$‐tuple occurs in at least one row. A covering array is optimal if it has the smallest possible $N$ for given $t$, $k$, and $v$, and uniform if every symbol occurs $?N∕v?$ or $?N∕v?$ times in every column. Before this paper, the only known optimal covering arrays for $t=2$ were orthogonal arrays, covering arrays with $v=2$ constructed from Sperner's Theorem and the Erd?s‐Ko‐Rado Theorem, and 11 other parameter sets with $v>2$ and $N>v^2$. In all these cases, there is a uniform covering array with the optimal size. It has been conjectured that there exists a uniform covering array of optimal size for all parameters. In this paper, a new lower bound as well as structural constraints for small uniform strength‐2 covering arrays is given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength‐2 covering array with $v>2$ and $N>v^2$ is now known for 21 parameter sets. Our constructive results continue to support the conjecture.     

Lower bounds on covering codes via partition matrices

Let Kq(n,R) denote the minimal cardinality of a q-ary code of length n and covering radius R. Let σq(n,s;r) denote the minimal cardinality of a q-ary code of length n, which is s-surjective with radius r. In order to lower-bound Kq(n,n−2) and σq(n,s;s−2) we introduce partition matrices and their transversals. Our approach leads to a short new proof of a classical bound of Rodemich on Kq(n,n−2) and to the new bound Kq(n,n−2)?3q−2n+2, improving the first iff 5?n<q?2n−4. We determine Kq(q,q−2)=q−2+σ₂(q,2;0) if q?10. Moreover, we obtain the new powerful recursive bound Kq+1(n+1,R+1)?min{2(q+1),Kq(n,R)+1}.     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998     

On a new class of nonlinear set covering problems arising in wireless network design

This is a summary of the author’s PhD thesis, supervised by Edoardo Amaldi and defended on 28 April 2006 at Politecnico di Milano, Dipartimento di Matematica. The thesis is written in English and is available from the author upon request. The thesis investigates a class of nonlinear set covering variants arising from the problem of designing single-frequency Wireless Local Area Networks (WLANs) with maximum efficiency. In the first part of the thesis a basic hyperbolic formulation of the problem is considered. After a complexity and approximability study, the problem is tackled by linearization techniques, and by Lagrangean and Dantzig–Wolfe decompositions. The second part of the thesis focuses on variants accounting for various relevant features of the WLAN application. A Branch-and-Price algorithm is presented, and extensions to the multiple-frequency WLAN design problem are considered.      

Global existence and bounds for blow‐up time in a class of nonlinear pseudo‐parabolic equations with a memory term

In this article, we consider the initial boundary value problem for a class of nonlinear pseudo‐parabolic equations with a memory term: Under suitable assumptions, we obtain the local and global existence of the solution by Galerkin method. We prove finite‐time blow‐up of the solution for initial data at arbitrary energy level and obtain upper bounds for blow‐up time by using the concavity method. In addition, by means of differential inequality technique, we obtain a lower bound for blow‐up time of the solution if blow‐up occurs.     

Lower bounds for the axial three-index assignment problem

This paper describes new bounding methods for the axial three-index assignment problem (3AP). For calculating 3AP lower bounds, we use a projection method followed by a Hungarian algorithm, based on a new Lagrangian relaxation. We also use a cost transformation scheme, which iteratively transforms 3AP costs in a series of equivalent 3APs, which provides the possibility of improving the 3AP lower bound. These methods produce efficiently computed relatively tight lower bound.     

Lower bounds in communication complexity based on factorization norms

We introduce a new method to derive lower bounds on randomized and quantum communication complexity. Our method is based on factorization norms, a notion from Banach Space theory. This approach gives us access to several powerful tools from this area such as normed spaces duality and Grothendiek's inequality. This extends the arsenal of methods for deriving lower bounds in communication complexity. As we show, our method subsumes most of the previously known general approaches to lower bounds on communication complexity. Moreover, we extend all (but one) of these lower bounds to the realm of quantum communication complexity with entanglement. Our results also shed some light on the question how much communication can be saved by using entanglement. It is known that entanglement can save one of every two qubits, and examples for which this is tight are also known. It follows from our results that this bound on the saving in communication is tight almost always. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Tight bounds for the vertices of degree k in minimally k‐connected graphs

For minimally k‐connected graphs on n vertices, Mader proved a tight lower bound for the number of vertices of degree k in dependence on n and k. Oxley observed 1981 that in many cases a considerably better bound can be given if is used as additional parameter, i.e. in dependence on m, n, and k. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long‐standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case.     

Lower bounds for the Chvátal-Gomory rank in the 0/1 cube

We revisit the method of Chvátal, Cook, and Hartmann to establish lower bounds on the Chvátal-Gomory rank, and develop a simpler method. We provide new families of polytopes in the 0/1 cube with high rank, and we describe a deterministic family achieving a rank of at least (1+1/e)n−1>n. Finally, we show how integrality gaps lead to lower bounds.     

Lower bounds for covering times for reversible Markov chains and random walks on graphs

For simple random walk on aN-vertex graph, the mean time to cover all vertices is at leastcN log(N), wherec>0 is an absolute constant. This is deduced from a more general result about stationary finite-state reversible Markov chains. Under weak conditions, the covering time for such processes is at leastc times the covering time for the corresponding i.i.d. process.     

Lower bounds for the logarithmic Sobolev constant avoiding uniform lower bounds on the Ricci curvature

In this paper we obtain a lower bound for the logarithmic Sobolev constant of the operator on C^∞(M) given by L^U f = Δ f - (?U|?f), where U ? C^∞(M), M being a finite dimensional compact Riemannian manifold without boundary, in terms of the spectral gap of L^U and the lowest eigenvalue of the operator -L^U + V, where V is a function related to U and the Ricci curvature of M. Under suitable conditions and being U ≡ 0, this result improves a previous one by J.-D. DEUSCHEL and D.W. STROOCK (J. Funct. Anal. 92 (1990), 30–48).     

Upper bounds on the general covering number Cλ(v,k, t,m)

A collection of k‐subsets (called blocks) of a v‐set X (v) = {1, 2,…, v} (with elements called points) is called a t‐(v, k, m, λ) covering if for every m‐subset M of X (v) there is a subcollection of with such that every block K ∈ has at least t points in common with M. It is required that v ≥ k ≥ t and v ≥ m ≥ t. The minimum number of blocks in a t‐(v, k, m, λ) covering is denoted by C_λ(v, k, t, m). We present some constructions producing the best known upper bounds on C_λ(v, k, t, m) for k = 6, a parameter of interest to lottery players. © 2004 Wiley Periodicals, Inc.     

Lower and upper bounds of Dirichlet eigenvalues for totally characteristic degenerate elliptic operators

Let λkbe the k-th Dirichlet eigenvalue of totally characteristic degenerate elliptic operator-ΔB defined on a stretched cone B0 ■ [0,1) × X with boundary on {x1 = 0}. More precisely,ΔB=(x1αx1)2+ α2x2+ + α2xnis also called the cone Laplacian. In this paper,by using Mellin-Fourier transform,we prove thatλk Cnk2 n for any k 1,where Cn=(nn+2)(2π)2(|B0|Bn)-2n,which gives the lower bounds of the Dirchlet eigenvalues of-ΔB. On the other hand,by using the Rayleigh-Ritz inequality,we deduce the upper bounds ofλk,i.e.,λk+1 1 +4n k2/nλ1. Combining the lower and upper bounds of λk,we can easily obtain the lower bound for the first Dirichlet eigenvalue λ1 Cn(1 +4n)-12n2.     

Updating lower bounds when using Karmarkar's projective algorithm for linear programming

We give two results related to Gonzaga's recent paper showing that lower bounds derived from the Todd-Burrell update can be obtained by solving a one-variable linear programming problem involving the centering direction and the affine direction. We show how these results may be used to update the primal solution when using the dual affine variant of Karmarkar's algorithm. This leads to a dual projective algorithm.This research was partially supported by ONR Grant Number N00014-90-J-1714.     

Uniform bounds on growth in o‐minimal structures

We prove that a function definable with parameters in an o‐minimal structure is bounded away from ∞ as its argument goes to ∞ by a function definable without parameters, and that this new function can be chosen independently of the parameters in the original function. This generalizes a result in [1]. Moreover, this remains true if the argument is taken to approach any element of the structure (or ±∞), and the function has limit any element of the structure (or ±∞) (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Lower bounds for multicolor classical Ramsey numbers

A method is put forward to establish the lower bounds for somen-color classical Ramsey numbers . With this method six new explicit lower boundsR ₄(4) ≥458,R ₃(5) ≥ 242,R ₃(6)≥1070,R ₃(7) ≥ 1214,R ₃(8) ≥2834 andR ₃(9) ≥ 5282 are obtained using a computer. Project supported by Guangxi Natural Science Foundation     

New lower bounds for t‐coverings

Fisher proved in 1940 that any 2‐ design with has at least v blocks. In 1975, Ray‐Chaudhuri and Wilson generalized this result by showing that every t‐ design with has at least blocks. By combining methods used by Bose and Wilson in proofs of these results, we obtain new lower bounds on the size of t‐ coverings. Our results generalize lower bounds on the size of 2‐ coverings recently obtained by the first author.     

Lower bounds for the first eigenvalue of the magnetic Laplacian

We consider a Riemannian cylinder Ω endowed with a closed potential 1-form A and study the magnetic Laplacian ${\mathrm{\Delta }}_A$ with magnetic Neumann boundary conditions associated with those data. We establish a sharp lower bound for the first eigenvalue and show that the equality characterizes the situation where the metric is a product. We then look at the case of a planar domain bounded by two closed curves and obtain an explicit lower bound in terms of the geometry of the domain. We finally discuss sharpness of this last estimate.     

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.     

A correction method for finding lower bounds of eigenvalues of the second‐order elliptic and Stokes operators

In this paper, for the second‐order elliptic and Stokes eigenvalue problems with variable coefficients, we propose a correction method to nonconforming eigenvalue approximations and prove that the corrected eigenvalues converge to the exact ones asymptotically from below. In particular, the asymptotic lower bound property of corrected eigenvalues is always valid whether the eigenfunctions are smooth or singular. Finally, we prove that the convergence order of corrected eigenvalues is still the same as that of uncorrected eigenvalues.