Improved lower bounds on k-independence

A vertex set Y in a (hyper)graph is called k-independent if in the sub(hyper)-graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k-independent set—in terms of degree sequences—which strengthens and generalizes several previously known results, including Turán's theorem.     

Classification of smooth affine spherical varieties

Let G be a complex reductive group. A normal G-variety X is called spherical if a Borel subgroup of G has a dense orbit in X. Of particular interest are spherical varieties which are smooth and affine since they form local models for multiplicity free Hamiltonian K-manifolds, K a maximal compact subgroup of G. In this paper, we classify all smooth affine spherical varieties up to coverings, central tori, and -fibrations.     

Some upper and lower bounds on PSD-rank

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.     

Exponential bounds on the number of designs with affine parameters

It is well‐known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n≥3, grows exponentially. This result was extended recently [D. Jungnickel, V. D. Tonchev, Des Codes Cryptogr, published online: 23 May, 2009] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2≤d≤n−1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n−1, as well as resolvable designs with these parameters. An exponential lower bound is also proved for the number of non‐isomorphic resolvable 3‐designs with the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, 2), for any 2≤d≤n−1. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 475–487, 2010     

Range of lower bounds

Each of n jobs is to be processed without interruption on a single machine. Each job becomes available for processing at time zero. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times added with maximum weighted tardiness. In this paper we give a general case of the theorem that given in [6]. This theorem shows a relation between the number of efficient solutions, lower bound LB and optimal solution. It restricts the range of the lower bound, which is the main factor to find the optimal solution. Also, the theorem opens algebraic operations and concepts to find new lower bounds.     

Small quasimultiple affine and projective planes: Some improved bounds

We improve the known bounds on r(n): = min {λ| an (n², n, λ)-RBIBD exists} in the case where n + 1 is a prime power. In such a case r(n) is proved to be at most n + 1. If, in addition, n − 1 is the product of twin prime powers, then r(n) ${\ \le \ }{n \over 2}$. We also improve the known bounds on p(n): = min{λ| an (n² + n + 1, n + 1, λ)-BIBD exists} in the case where n² + n + 1 is a prime power. In such a case p(n) is bounded at worst by but better bounds could be obtained exploiting the multiplicative structure of GF(n² + n + 1). Finally, we present an unpublished construction by M. Greig giving a quasidouble affine plane of order n for every positive integer n such that n − 1 and n + 1 are prime powers. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 337–345, 1998     

Circuit lower bounds and linear codes

In 1977, Valiant proposed a graph-theoretical method for proving lower bounds on algebraic circuits with gates computing linear functions. He used this method to reduce the problem of proving lower bounds on circuits with linear gates to proving lower bounds on the rigidity of a matrix, a notion that he introduced in that paper. The largest lower bound for an explicitly given matrix is due to J. Friedman, who proved a lower bound on the rigidity of the generator matrices of error-correcting codes over finite fields. He showed that the proof can be interpreted as a bound on a certain parameter defined for all linear spaces of finite dimension. In this note, we define another parameter that can be used to prove lower bounds on circuits with linear gates. Our parameter may be larger than Friedman’s, and it seems incomparable with rigidity, hence it may be easier to prove a lower bound using this notion. Bibliography: 14 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 188–204.     

Obtaining upper bounds of heat kernels from lower bounds

We show that a near‐diagonal lower bound of the heat kernel of a Dirichlet form on a metric measure space with a regular measure implies an on‐diagonal upper bound. If in addition the Dirichlet form is local and regular, then we obtain a full off‐diagonal upper bound of the heat kernel provided the Dirichlet heat kernel on any ball satisfies a near‐diagonal lower estimate. This reveals a new phenomenon in the relationship between the lower and upper bounds of the heat kernel. © 2007 Wiley Periodicals, Inc.     

Better upper bounds on the QOBDD size of integer multiplication

We show that the middle bit of the multiplication of two n-bit integers can be computed by an ordered binary decision diagram (OBDD) of size less than 2.8·2^6n/5. This improves the previously known upper bound of by Woelfel (New Bounds on the OBDD-size of integer multiplication via Universal Hashing, J. Comput. System Sci. 71(4) (2005) 520-534). The experimental results suggest that our exponent of 6n/5 is optimal or at least very close to optimal. A general upper bound of O(2^3n/2) on the OBDD size of each output bit of the multiplication is also presented.     

Error bounds and strong upper semicontinuity for monotone affine variational inequalities

Global error bounds for possibly degenerate or nondegenerate monotone affine variational inequality problems are given. The error bounds are on an arbitrary point and are in terms of the distance between the given point and a solution to a convex quadratic program. For the monotone linear complementarity problem the convex program is that of minimizing a quadratic function on the nonnegative orthant. These bounds may form the basis of an iterative quadratic programming procedure for solving affine variational inequality problems. A strong upper semicontinuity result is also obtained which may be useful for finitely terminating any convergent algorithm by periodically solving a linear program.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grants CCR-9101801 and CCR-9157632.     

Equilibrium problems with lower and upper bounds

In this paper, we obtain some existence results of equilibrium problems with lower and upper bounds by employing a fixed-point theorem due to Ansari and Yao [1] and Ky Fan Lemma [2], respectively. Our results give answers to the open problem raised by Isac, Sehgal and Singh [3].     

Upper and lower bounds of the valence-functional

For the non-negative integerg let (M, g) denote the closed orientable 2-dimensional manifold of genusg. K-realizationsP of (M, g) are geometric cell-complexes inP with convex facets such that set (P) is homeomorphic toM. ForK-realizationsP of (M, g) and verticesv ofP, val (v,P) denotes the number of edges ofP incident withv and the weighted vertex-number Σ(val(v, P)-3) taken over all vertices ofP is called valence-valuev (P) ofP. The valence-functionalV, which is important for the determination of all possiblef-vectors ofK-realisations of (M, g), in connection with Eberhard's problem etc., is defined byV(g):=min[v(P)|P is aK-realization of (M,g)]. The aim of the note is to prove the inequality 2g+1≦V(g)≦3g+3 for every positive integerg.     

On lower and upper bounds of matrices

Using an approach of Bergh, we give an alternate proof of Bennett's result on lower bounds for non-negative matrices acting on non-increasing non-negative sequences in lp when p?1 and its dual version, the upper bounds when 0<p?1. We also determine such bounds explicitly for some families of matrices.     

Some upper and lower bounds on the coupon collector problem

The classical coupon collector problem is closely related to probabilistic-packet-marking (PPM) schemes for IP traceback problem in the Internet. In this paper, we study the classical coupon collector problem, and derive some upper and lower bounds of the complementary cumulative distribution function (ccdf) of the number of objects (coupons) that one has to check in order to detect a set of different objects. The derived bounds require much less computation than the exact formula. We numerically find that the proposed bounds are very close to the actual ccdf when detecting probabilities are set to the values common to the PPM schemes.     

Lower bounds for lower Ramsey numbers

For any graph G, let i(G) and μ;(G) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers m and n, the lower Ramsey number s(m, n) is the largest integer p so that every graph of order p has i(G) ≤ m or μ;(G) ≤ n. In this paper we give several new lower bounds for s (m, n) as well as determine precisely the values s(1, n).     

Upper and lower bounds on norms of functions of matrices

Given an n by n matrix A, we look for a set S in the complex plane and positive scalars m and M such that for all functions p bounded and analytic on S and throughout a neighborhood of each eigenvalue of A, the inequalities

m·inf{‖f‖_L^∞(S):f(A)=p(A)}?‖p(A)‖?M·inf{‖f‖_L^∞(S):f(A)=p(A)}