Helly Theorem and Related Results

By using the classical Helly theorem, one cannot obtain information about a family of convex compact sets in the n-dimensional Euclidean space if it is known that only subfamilies consisting of k elements, 0 < k n, have nonempty intersections. We modify the Helly theorem to fix this issue and investigate the behavior of generalized convex families.     

Intersections of spherically convex sets

New theorems of Helly type are proved concerning the intersection of convex cones with a common vertex or, equivalently, the intersection of sets on a sphere which are convex in the sense of Robinson. The proofs of these theorems are based on a lemma which is a spherical analog and generalization of Radon's theorem.     

A note on the colorful fractional Helly theorem

Helly’s theorem is a classical result concerning the intersection patterns of convex sets in ${\mathbb{R}}^d$. Two important generalizations are the colorful version and the fractional version. Recently, Bárány et al. combined the two, obtaining a colorful fractional Helly theorem. In this paper, we give an improved version of their result.     

On Finite Linear Systems Containing Strict Inequalities

This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.     

Generalized projections onto convex sets

This paper introduces the notion of projection onto a closed convex set associated with a convex function. Several properties of the usual projection are extended to this setting. In particular, a generalization of Moreau’s decomposition theorem about projecting onto closed convex cones is given. Several examples of distances and the corresponding generalized projections associated to particular convex functions are presented.     

Fixed points,coincidence points and maximal elements with applications to generalized equilibrium problems and minimax theory

In this paper, using a generalization of the Fan–Browder fixed point theorem, we obtain a new fixed point theorem for multivalued maps in generalized convex spaces from which we derive several coincidence theorems and existence theorems for maximal elements. Applications of these results to generalized equilibrium problems and minimax theory will be given in the last sections of the paper.     

Generalized skew bisubmodularity: A characterization and a min–max theorem

Huber, Krokhin, and Powell (2013) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain. In this paper we consider a natural generalization of the concept of skew bisubmodularity and show a connection between the generalized skew bisubmodularity and a convex extension over rectangles. We also analyze the dual polyhedra, called skew bisubmodular polyhedra, associated with generalized skew bisubmodular functions and derive a min–max theorem that characterizes the minimum value of a generalized skew bisubmodular function in terms of a minimum-norm point in the associated skew bisubmodular polyhedron.     

Quantitative (p,q) theorems in combinatorial geometry

We show quantitative versions of classical results in discrete geometry, where the size of a convex set is determined by some non-negative function. We give versions of this kind for the selection theorem of Bárány, the existence of weak epsilon-nets for convex sets and the $(p,q)$ theorem of Alon and Kleitman. These methods can be applied to functions such as the volume, surface area or number of points of a discrete set. We also give general quantitative versions of the colorful Helly theorem for continuous functions.     

Motzkin’s theorem of the alternative: a continuous-time generalization

We revisit Zalmai’s theorem, which is a partial generalization of Motzkin’s theorem of the alternative in the continuous-time setting. In particular, we provide two simple examples demonstrating that its existing proof is incorrect, and we demonstrate that a suitably modified variant of Zalmai’s theorem, concerned with the inconsistency of systems of convex inequalities and affine equalities, can be verified. We also derive two generalized variants of Motzkin’s theorem of the alternative in the continuous-time setting.     

Attractive force search algorithm for piecewise convex maximization problems

We consider mathematical programming problems with the so-called piecewise convex objective functions. A solution method for this interesting and important class of nonconvex problems is presented. This method is based on Newton??s law of universal gravitation, multicriteria optimization and Helly??s theorem on convex bodies. Numerical experiments using well known classes of test problems on piecewise convex maximization, convex maximization as well as the maximum clique problem show the efficiency of the approach.     

Discrete and Lexicographic Helly-Type Theorems

Helly’s theorem says that if every d+1 elements of a given finite set of convex objects in ℝ ^d have a common point, then there is a point common to all of the objects in the set. We define three new types of Helly theorems: discrete Helly theorems—where the common point should belong to an a-priori given set, lexicographic Helly theorems—where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We study the relations between the different types of the Helly theorems. We obtain several new discrete and lexicographic Helly numbers. An extended abstract containing parts of this work appeared in the proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science (FOCS) 2004. This work is part of the author’s Ph.D. thesis, prepared in the school of mathematical sciences at Tel Aviv University, under the supervision of Professor Arie Tamir.     

Near-Subconvexlikeness in Vector Optimization with Set-Valued Functions

A new class of generalized convex set-valued functions, termed nearly-subconvexlike functions, is introduced. This class is a generalization of cone-subconvexlike maps, nearly-convexlike set-valued functions, and preinvex set-valued functions. Properties for the nearly-subconvexlike functions are derived and a theorem of the alternative is proved. A Lagrangian multiplier theorem is established and two scalarization theorems are obtained for vector optimization.     

A generalization of Jung's theorem

Jung's theorem establishes a relation between circumradius and diameter of a convex body. Half of the diameter can be interpreted as the maximum of circumradii of all 1-dimensional sections or 1-dimensional orthogonal projections of a convex body. This point of view leads to two series of j-dimensional circumradii, defined via sections or projections. In this paper we study some relations between these circumradii and by this we find a natural generalization of Jung's theorem.I would like to thank Prof. Dr J. M. Wills, who called my attention to these generalized circumradii.     

On the helly property working as a compactness criterion on graphs

The study of combinatorial topology and of the most important methods in algebraic topology (simplicial complexes, discretization) leads to the idea that it may be useful to translate some of the most classical problems in topology into a discrete context. Following this principle, several authors have already tried to study fixed point and retraction problems inside the theory of partially ordered sets. We try here to make a special study about the extension of homomorphisms and the fixed point problems on graphs. We introduce here, using the Helly property, a kind of compactness tool working on graphs, and we prove a generalization of Sperner's lemma which is used in the proof of the Brouwer fixed-point theorem by Kuratowski.     

Methods for the Elimination of Unknowns from Systems of Linear Inequalities and Their Applications

We study methods for the elimination of an unknown or a group of unknowns from systems of linear inequalities. We justify these methods by using the Helly theorem. The methods considered are applied to the calculation of streams in networks with a generalized conservation law.     

A generalization of the Helly theorem for functions with values in a uniform space

In this paper we consider sequences of functions that are defined on a subset of the real line and take on values in a uniform Hausdorff space. For such sequences we obtain a sufficient condition for the existence of pointwise convergent subsequences. We prove that this generalization of the Helly theorem includes many results of the recent research. In addition, we prove that the sufficient condition is also necessary for uniformly convergent sequences of functions. We also obtain a representation for regular functions whose values belong to the uniform space.     

Fixed-Point Theorems for Generalized Nonexpansive Mappings

Using the concept of asymptotic center we obtain the existence of fixed points having preassigned location for a wider class of asymptotic nonexpansive mappings in a uniformly convex Banach space. This generalization leads us to get a recent result of Alfuraidan and Khamsi for continuous monotone asymptotic nonexpansive mappings as well as the classical fixed-point result of Geobel and Kirk for asymptotic nonexpansive mappings in a uniformly convex Banach space. Also we prove a fixed-point theorem for order preserving continuous maps on a quasiordered closed convex subset of a uniformly convex Banach sapce having monotone norm.     

Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner

The problem of the partition-numbersJ _?(p, q), considered by Hadwiger and Debrunner for the family ?=C ⁿ of convex bodies, is extended to simplicial complexes and arbitrary families assuming only the validity of Helly’s theorem. We obtain results similar to those of Hadwiger and Debrunner. Further we show the existence of all partition-numbers for the family? = H ⁿC of homothets of a convex body and we get new informations on the partition-numbers for the family of parallel rectangles.     

Asymptotic stability in linear thermoviscoelasticity

We examine a notion of duality which appears to be useful in situations where the usual convex duality theory is not appropriate because the functional to be minimized is not convex. The principle is a generalization of a duality theorem derived previously (J. F. Toland, University of Essex Fluid Mechanics Research Institute, Report No. 77, November 1976, Arch. Rational Mech. Analysis (in press)), for nonconvex problems. The generalization is considerable, since no assumptions are made on the functional to be minimized, other than that it can be embedded in a family of perturbed problems. If such an embedding is possible, then the main theorem depends only on some rather well-known results in the theory of conjugate convex functions. We develop all the previously derived abstract results in this more general framework. The earlier work is seen to be a special case of this generalized duality theory. We treat abstract problems which are typical of those arising in the calculus of variations, and some applications are considered.