Small eigenvalues of geometrically finite manifolds

Let M be a complete geometrically finite manifold of bounded negative curvature, infinite volume, and dimension at least 3.We give both a lower bound for the bottom of the spectrum of M and an upper bound for the number of the small eigenvalues of M. These bounds only depend on the dimension, curvature bounds and the volume of the oneneighborhood of the convex core.     

The Willmore functional and the containment problem in R4

Let ∑ be a convex hypersurface in the Euclidean space R4 with mean curvature H. We obtain a geometric lower bound for the Willmore functional f∑ H2dσ. This bound is an invariant involving the area of ∑, the volume and Minkowski quermassintegrals of the convex body that ∑bounds. We also obtain a sufficient condition for a convex body to contain another in the Euclidean space R4.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

Cores and large cores when population varies

In a TU cooperative game with populationN, a monotonic core allocation allocates each surplusv (S) among the agents of coalitionS in such a way that agenti's share never decreases when the coalition to which he belongs expands.We investigate the property of largeness (Sharkey [1982]) for monotonic cores. We show the following result. Given a convex TU game and an upper bound on each agent' share in each coalition containing him, if the upper bound depends only upon the size of the coalition and varies monotonically as the size increases, then there exists a monotonic core allocation meeting this system of upper bounds. We apply this result to the provision of a public good problem.     

Convex interval interpolation with cubic splines,II

The problem of convex interval interpolation with cubicC ¹-splines has an infinite number of solutions, if it is solvable at all. For selecting one of the solutions a regularized mean curvature is minimized. The arising finite dimensional constrained program is solved numerically by means of a dualization approach.Dedicated to Professor Julius Albrecht on the occasion of his 65th birthday.     

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.     

Polynomial systems with few real zeroes

We study some systems of polynomials whose support lies in the convex hull of a circuit, giving a sharp upper bound for their numbers of real solutions. This upper bound is non-trivial in that it is smaller than either the Kouchnirenko or the Khovanskii bounds for these systems. When the support is exactly a circuit whose affine span is ℤⁿ, this bound is 2n+1, while the Khovanskii bound is exponential in n². The bound 2n+1 can be attained only for non-degenerate circuits. Our methods involve a mixture of combinatorics, geometry, and arithmetic. Part of work done at MSRI was supported by NSF grant DMS-9810361. Work of Sottile is supported by the Clay Mathematical Institute. Sottile and Bihan were supported in part by NSF CAREER grant DMS-0134860. Bertrand is supported by the European research network IHP-RAAG contract HPRN-CT-2001-00271.     

Global C2‐Estimates for Convex Solutions of Curvature Equations

We establish a C² a priori estimate for convex hypersurfaces whose principal curvatures κ=(κ₁,…, κ_n) satisfy σ_k(κ(X))=f(X,ν(X)), the Weingarten curvature equation. We also obtain such an estimate for admissible 2‐convex hypersurfaces in the case k=2. Our estimates resolve a longstanding problem in geometric fully nonlinear elliptic equations.© 2015 Wiley Periodicals, Inc.     

Fast deterministic approximation for the multicommodity flow problem

In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ε ⁻² + logk) logn) 1-commodity minimum-cost flow computations, wherek is the number of commodities,n is the number of nodes, andε is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995) the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem. A preliminary version of this paper appeared inProceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, 1995, pp. 486–492.     

The curvature of the Sasaki metric of tangent sphere bundles

We study the sectional curvaturesK of the Sasaki metric of tangent sphere bundles over spaces of constant curvatureK(T ₁(M ⁿ, K)). We give precise bounds on the variation of the Ricci curvature and a bound on the scalar curvature ofT ₁ (M ⁿ, K) that is uniform onK. In an appendix we calculate and give lower bounds for the lengths of closed geodesics onT ₁ S ⁿ. titles.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 132–145.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

On the fundamental groups of manifolds with integral curvature bounds

In this paper, we give an upper bound on the growth of π₁(M) for a class of manifolds with integral Ricci curvature bounds. This generalizes the main theorem of [8] to the case where the negative part of Ricci curvature is small in an averaged L¹- sense.Received: 19 July 2004     

The Willmore functional and the containment problem in R4

Let Σ be a convex hypersurface in the Euclidean space R ⁴ with mean curvature H. We obtain a geometric lower bound for the Willmore functional ∫_Σ H ² dσ. This bound is an invariant involving the area of Σ, the volume and Minkowski quermassintegrals of the convex body that Σ bounds. We also obtain a sufficient condition for a convex body to contain another in the Euclidean space R ⁴.     

Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

Convexity preserving interpolation by algebraic curves and surfaces

The problem of interpolation by a convex curve to the vertices of a convex polygon is considered. A natural 1-parameter family ofC algebraic curves solving this problem is presented. This is extended to a solution, of a general Hermite-type problem, in, which the curve also interpolates to one or two prescribedtangents at any desired vertices of the polygon. The construction of these curves is a generalization of well known methods for generatingconic sections. Several properties of this family of algebraic curves are discussed. In addition, the method is generalized to convexC interpolation of strictly convex data sets inR ³ by algebraicsurfaces.     

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.     

Conformal upper bounds for the eigenvalues of the Laplacian and Steklov problem

In this paper, we find upper bounds for the eigenvalues of the Laplacian in the conformal class of a compact Riemannian manifold (M,g). These upper bounds depend only on the dimension and a conformal invariant that we call “min-conformal volume”. Asymptotically, these bounds are consistent with the Weyl law and improve previous results by Korevaar and Yang and Yau. The proof relies on the construction of a suitable family of disjoint domains providing supports for a family of test functions. This method is interesting for itself and powerful. As a further application of the method we obtain an upper bound for the eigenvalues of the Steklov problem in a domain with C¹ boundary in a complete Riemannian manifold in terms of the isoperimetric ratio of the domain and the conformal invariant that we introduce.     

On the geometry of subsets of positive reach

We prove that sets of positive reach in Riemannian manifolds and more generally, almost convex subsets in spaces with an upper curvature bound have an upper curvature bound with respect to the inner metric.Mathematics Subject Classification (2000): 53C20     

On Linear Programming Bounds for Spherical Codes and Designs

We investigate universal bounds on spherical codes and spherical designs that could be obtained using Delsartes linear programming methods. We give a lower estimate for the LP upper bound on codes, and an upper estimate for the LP lower bound on designs. Specifically, when the distance of the code is fixed and the dimension goes to infinity, the LP upper bound on codes is at least as large as the average of the best known upper and lower bounds. When the dimension n of the design is fixed, and the strength k goes to infinity, the LP bound on designs turns out, in conjunction with known lower bounds, to be proportional to k^n-1.     

Convex interval interpolation with cubic splines

A necessary and sufficient criterion is presented under which the problem of the convex interval interpolation with cubicC ¹-splines has at least one solution. The criterion is given as an algorithm which turns out to be effective.Dedicated to Professor Julius Albrecht on the occasion of his 60th birthday.