A Helly-Type Theorem for Unions of Convex Sets

We prove that for any d, k ≥ 1 there are numbers q = q(d,k) and h = h(d,k) such that the following holds: Let be a family of subsets of the d-dimensional Euclidean space, such that the intersection of any subfamily of consisting of at most q sets can be expressed as a union of at most k convex sets. Then the Helly number of is at most h. We also obtain topological generalizations of some cases of this result. The main result was independently obtained by Alon and Kalai, by a different method. Received April 14, 1995, and in revised form August 1, 1995.     

关于随机紧凸集的更新定理

该文在讨论了多维更新定理的基础上,重点研究了随机紧凸集的Minkowski和的更新定理,得到了一系列重要结论.     

A Helly-Type Theorem for Hyperplane Transversals to Well-Separated Convex Sets

Let S be a finite collection of compact convex sets in \R ^d . Let D(S) be the largest diameter of any member of S . We say that the collection S is ɛ-separated if, for every 0 < k < d , any k of the sets can be separated from any other d-k of the sets by a hyperplane more than ɛ D(S)/2 away from all d of the sets. We prove that if S is an ɛ -separated collection of at least N(ɛ) compact convex sets in \R ^d and every 2d+2 members of S are met by a hyperplane, then there is a hyperplane meeting all the members of S . The number N(ɛ) depends both on the dimension d and on the separation parameter ɛ . This is the first Helly-type theorem known for hyperplane transversals to compact convex sets of arbitrary shape in dimension greater than one. Received August 10, 2000, and in revised form January 24, 2001. Online publication April 6, 2001.     

Blaschke-Type Theorem and Separation of Disjoint Closed Geodesic Convex Sets

In this paper, we deal with analytic and geometrical properties of geodesic convex sets and geodesic paths. We show that Blaschke’s Theorem for convex sets is also true for geodesic convex sets and geodesic paths in a simple polygon. Some geometrical properties of geodesic triangles are presented. Furthermore, separation of geodesic convex sets is shown.     

On Locally Linearly Convex Domains

We construct a counterexample to the hypothesis on global linear convexity of locally linearly convex domains with everywhere smooth boundary. We refine the theorem on the topological classification of linearly convex domains with smooth boundary.     

A Generalization of the Erdos - Szekeres Theorem to Disjoint Convex Sets

Let F denote a family of pairwise disjoint convex sets in the plane. F is said to be in convex position if none of its members is contained in the convex hull of the union of the others. For any fixed k≥ 3 , we estimate P _k (n) , the maximum size of a family F with the property that any k members of F are in convex position, but no n are. In particular, for k=3 , we improve the triply exponential upper bound of T. Bisztriczky and G. Fejes Tóth by showing that P ₃ (n) < 16 ⁿ . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p437.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received March 27, 1997, and in revised form July 10, 1997.     

Canonical Theorems for Convex Sets

Let F be a family of pairwise disjoint compact convex sets in the plane such that none of them is contained in the convex hull of two others, and let r be a positive integer. We show that F has r disjoint ⌊ c _r n⌋ -membered subfamilies F _i (1 ≤ i ≤ r) such that no matter how we pick one element F _i from each F _i , they are in convex position, i.e., every F _i appears on the boundary of the convex hull of ⋃ _i=1 ^r F _i . (Here c _r is a positive constant depending only on r .) This generalizes and sharpens some results of Erdős and Szekeres, Bisztriczky and Fejes Tóth, Bárány and Valtr, and others. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p427.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received April 30, 1997, and in revised form August 5, 1997.     

Constructible Convex Sets

We investigate when closed convex sets can be written as countable intersections of closed half-spaces in Banach spaces. It is reasonable to consider this class to comprise the constructible convex sets since such sets are precisely those that can be defined by a countable number of linear inequalities, hence are accessible to techniques of semi-infinite convex programming. We also explore some model theoretic implications. Applications to set convergence are given as limiting examples.     

Finding Convex Sets in Convex Position

Let F{\cal{F}} denote a family of pairwise disjoint convex sets in the plane. F{\cal{F}} is said to be in convex position, if none of its members is contained in the convex hull of the union of the others. For any fixed k 3 5k\ge5, we give a linear upper bound on P_k(n)P_k(n), the maximum size of a family F{\cal{F}} with the property that any k members of F{\cal{F}} are in convex position, but no n are.     

Self-Concordant Barriers for Convex Approximations of Structured Convex Sets

We show how to approximate the feasible region of structured convex optimization problems by a family of convex sets with explicitly given and efficient (if the accuracy of the approximation is moderate) self-concordant barriers. This approach extends the reach of the modern theory of interior-point methods, and lays the foundation for new ways to treat structured convex optimization problems with a very large number of constraints. Moreover, our approach provides a strong connection from the theory of self-concordant barriers to the combinatorial optimization literature on solving packing and covering problems.     

Integral Representations in Linearly Convex Polyhedra

We introduce the notion of mixed Levian (Levi determinant) of a system of k Hermitian and k linear forms. In terms of these Levians we obtain an integral formula for holomorphic functions in linearly convex polyhedra.Original Russian Text Copyright © 2005 Krivokolesko V. P. and Tsikh A. K.The first author was supported by a grant of the President of the Russian Federation and the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-1212.2003.1); the second author was supported by the Ministry for Education of the Russian Federation (St. Petersburg, Grant 02-1-138).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 3, pp. 579–593, May–June, 2005.     

Translating Finite Sets into Convex Sets

Let X be a reflexive Banach space, and let C X be a closed,convex and bounded set with empty interior. Then, for every > 0, there is a nonempty finite set F X with an arbitrarilysmall diameter, such that C contains at most .|F| points ofany translation of F. As a corollary, a separable Banach spaceX is reflexive if and only if every closed convex subset ofX with empty interior is Haar null. 2000 Mathematics SubjectClassification 46B20 (primary), 28C20 (secondary).     

A Ramsey-Type Result for Convex Sets

Given a family of n convex compact sets in the plane, one canalways choose n of them which are either pairwise disjoint orpairwise intersecting. On the other hand, there exists a familyof n segments in the plane such that the maximum size of a subfamilywith pairwise disjoint or pairwise intersecting elements inn^log2/log5 n^0·431.     

Sets satisfying the Central Sets Theorem

Central subsets of a discrete semigroup S have very strong combinatorial properties which are a consequence of the Central Sets Theorem . We investigate here the class of semigroups that have a subset with zero Følner density which satisfies the conclusion of the Central Sets Theorem. We show that this class includes any direct sum of countably many finite abelian groups as well as any subsemigroup of (?,+) which contains ?. We also show that if S and T are in this class and either both are left cancellative or T has a left identity, then S×T is in this class. We also extend a theorem proved in (Beiglböck et al. in Topology Appl., to appear), which states that, if p is an idempotent in β? whose members have positive density, then every member of p satisfies the Central Sets Theorem. We show that this holds for all commutative semigroups. Finally, we provide a simple elementary proof of the fact that any commutative semigroup satisfies the Strong Følner Condition.     

Extremal Convex Planar Sets

Each convex planar set K has a perimeter C, a minimum width E, an area A, and a diameter D. The set of points (E,C, A^1/2, D) corresponding to all such sets is shown to occupy a cone in the non-negative orthant of R⁴with its vertex at the origin. Its three-dimensional cross section S in the plane D = 1 is investigated. S lies in a rectangular parallelepiped in R³. Results of Lebesgue, Kubota, Fukasawa, Sholander, and Hemmi are used to determine some of the boundary surfaces of S, and new results are given for the other boundary surfaces. From knowledge of S, all inequalities among E, C ,A, and D can be found.     

Inexact Alternating-Direction-Based Contraction Methods for Separable Linearly Constrained Convex Optimization

Alternating direction method of multipliers has been well studied in the context of linearly constrained convex optimization. In the last few years, we have witnessed a number of novel applications arising from image processing, compressive sensing and statistics, etc., where the approach is surprisingly efficient. In the early applications, the objective function of the linearly constrained convex optimization problem is separable into two parts. Recently, the alternating direction method of multipliers has been extended to the case where the number of the separable parts in the objective function is finite. However, in each iteration, the subproblems are required to be solved exactly. In this paper, by introducing some reasonable inexactness criteria, we propose two inexact alternating-direction-based contraction methods, which substantially broaden the applicable scope of the approach. The convergence and complexity results for both methods are derived in the framework of variational inequalities.     

拟共形映照和线性局部连通集

本文证明了Ｒｎ中线性局部连通集定义中的两个性质分别在保持无穷远点不变的拟共形映照下是不变的，并且指出保持无穷远点不变的条件是必不可少的．反过来，设ｆ是Ｒｎ上的同胚，ｆ（　）＝　，若线性局部连通集定义中的任意一条性质在ｆ下不变，则ｆ必是拟共形映照．     

Convex Sets in Acyclic Digraphs

A non-empty set X of vertices of an acyclic digraph is called connected if the underlying undirected graph induced by X is connected and it is called convex if no two vertices of X are connected by a directed path in which some vertices are not in X. The set of convex sets (connected convex sets) of an acyclic digraph D is denoted by and its size by co(D) (cc(D)). Gutin et al. (2008) conjectured that the sum of the sizes of all convex sets (connected convex sets) in D equals Θ(n · co(D)) (Θ(n · cc(D))) where n is the order of D. In this paper we exhibit a family of connected acyclic digraphs with and . We also show that the number of connected convex sets of order k in any connected acyclic digraph of order n is at least n − k + 1. This is a strengthening of a theorem of Gutin and Yeo.