摘要 :
In this paper, we consider finite families of convex sets in R-d such that every d or fewer sets of the family have a common point. For some families of this type, we give upper bounds on the size of a finite set intersecting all ...
展开
In this paper, we consider finite families of convex sets in R-d such that every d or fewer sets of the family have a common point. For some families of this type, we give upper bounds on the size of a finite set intersecting all sets of the family.
收起
摘要 :
This paper presents a new variation of Tverberg's theorem. Given a discrete set S of R-d, we study the number of points of S needed to guarantee the existence of an m-partition of the points such that the intersection of the m con...
展开
This paper presents a new variation of Tverberg's theorem. Given a discrete set S of R-d, we study the number of points of S needed to guarantee the existence of an m-partition of the points such that the intersection of the m convex hulls of the parts contains at least k points of S. The proofs of the main results require new quantitative versions of Helly's and Caratheodory's theorems.
收起
摘要 :
In 1940, Luis Santalo proved a Helly-type theorem for line transversals to boxes in Rrf. An analysis of bis proof reveals a convexity structure for ascending lines in ]Rrf that is iso-morphic to the ordinary notion of convexity in...
展开
In 1940, Luis Santalo proved a Helly-type theorem for line transversals to boxes in Rrf. An analysis of bis proof reveals a convexity structure for ascending lines in ]Rrf that is iso-morphic to the ordinary notion of convexity in a convex subset of IR~2d-2. This isomorphism is through a Cremona transformation on the Grassmannian of lines in IPd, which enables a precise description of the convex hull and affine span of up to d ascending lines: the lines in such an affine span turn out to be the rulings of certain classical determinantal varieties. Finally, we relate Cremona convexity to a new convexity structure that we call frame convexity, which extends to arbitrary-dimensional flats in TR.d.
收起
摘要 :
We introduce a notion of halfspace for Hadamard manifolds that is natural in the context of convex optimization. For this notion of halfspace, we generalize a classic result of Grünbaum, which itself is a corollary of Helly's the...
展开
We introduce a notion of halfspace for Hadamard manifolds that is natural in the context of convex optimization. For this notion of halfspace, we generalize a classic result of Grünbaum, which itself is a corollary of Helly's theorem. Namely, given a probability distribution on the manifold, there is a point for which all halfspaces based at this point have at least 1/n+1 of the mass. As an application, the subgradient oracle complexity of convex optimization is polynomial in the size of the parameters defining the problem.
收起
摘要 :
We describe a connection between the combinatorics of generators for certain groups and the combina-torics of Helly's 1913 theorem on convex sets. We use this connection to prove fixed point theorems foractions of these groups on ...
展开
We describe a connection between the combinatorics of generators for certain groups and the combina-torics of Helly's 1913 theorem on convex sets. We use this connection to prove fixed point theorems foractions of these groups on nonpositively curved metric spaces. These results are encoded in a property thatwe introduce called "property FAr", which reduces to Serre's property FA when r = 1. The method appliesto S-arithmetic groups in higher Q-rank, to simplex reflection groups (including some nonarithmetic ones),and to higher rank Chevalley groups over polynomial and other rings (for example SLn (Z[x , , xd]),n > 2).
收起
摘要 :
We prove two colorful Caratheodory theorems for strongly convex hulls, generalizing the colorful Caratheodory theorem for ordinary convexity by Imre Barany, the non-colorful Caratheodory theorem for strongly convex hulls by the se...
展开
We prove two colorful Caratheodory theorems for strongly convex hulls, generalizing the colorful Caratheodory theorem for ordinary convexity by Imre Barany, the non-colorful Caratheodory theorem for strongly convex hulls by the second author, and the "very colorful theorems" by the first author and others. We also investigate if the assumption of a "generating convex set" is really needed in such results and try to give a topological criterion for one convex body to be a Minkowski summand of another.
收起
摘要 :
Let F-1,..., Fd+1 be d + 1 families of convex sets in R-d. The Colorful Helly Theorem (see (Discrete Math. 40 (1982) 141)) asserts that if boolean AND(i=1)(d+1) F(i)not equal0 for all choices of F-1 is an element of F-1,..., Fd+1 ...
展开
Let F-1,..., Fd+1 be d + 1 families of convex sets in R-d. The Colorful Helly Theorem (see (Discrete Math. 40 (1982) 141)) asserts that if boolean AND(i=1)(d+1) F(i)not equal0 for all choices of F-1 is an element of F-1,..., Fd+1 is an element of Fd+1 then there exists an 1 less than or equal to i less than or equal to d + 1 such that boolean AND(Fis an element ofF1) Fnot equal0.Our main result is both a topological and a matroidal extension of the colorful Helly theorem. A simplicial complex X is d-Leray if H-i(Y;Q) = 0 for all induced subcomplexes Y subset of X and i greater than or equal to d.Theorem. Let X be a d-Leray complex on the vertex set V. Suppose M is a matroidal complex on the same vertex set V with rank function p. If M subset of X then there exists a simplex tau is an element of X such that rho(V - tau) less than or equal to d. (C) 2004 Elsevier Inc. All rights reserved.
收起
摘要 :
E. Helly's theorem asserts that any bounded sequence of monotone real functions contains a pointwise convergent subsequence. We reprove this theorem in a generalized version in terms of monotone functions on linearly ordered sets....
展开
E. Helly's theorem asserts that any bounded sequence of monotone real functions contains a pointwise convergent subsequence. We reprove this theorem in a generalized version in terms of monotone functions on linearly ordered sets. We show that the cardinal number responsible for this generalization is exactly the splitting number. We also show that a positive answer to a problem of S. Saks is obtained under the assumption of the splitting number being strictly greater than the first uncountable cardinal.
收起
摘要 :
A Helly-type theorem for diameter provides a bound on the diameter of the intersection of a finite family of convex sets in R-d given some information on the diameter of the intersection of all sufficiently small subfamilies. We p...
展开
A Helly-type theorem for diameter provides a bound on the diameter of the intersection of a finite family of convex sets in R-d given some information on the diameter of the intersection of all sufficiently small subfamilies. We prove fractional and colorful versions of a long-standing conjecture by Barany, Katchalski, and Pach. We also show that a Minkowski norm admits an exact Helly-type theorem for diameter if and only if its unit ball is a polytope and prove a colorful version for those that do. Finally, we prove Helly-type theorems for the property of "containing k colinear integer points."
收起
摘要 :
Much work has been done to identify which binary codes can be represented by collections of open convex or closed convex sets. While not all binary codes can be realized by such sets, here we prove that every binary code can be re...
展开
Much work has been done to identify which binary codes can be represented by collections of open convex or closed convex sets. While not all binary codes can be realized by such sets, here we prove that every binary code can be realized by convex sets when there is no restriction on whether the sets are all open or closed. We achieve this by constructing a convex realization for an arbitrary code with k nonempty codewords in Rk-1. This result justifies the usual restriction of the definition of convex neural codes to include only those that can be realized by receptive fields that are all either open convex or closed convex. We also show that the dimension of our construction cannot in general be lowered. (C) 2018 Elsevier Inc. All rights reserved.
收起
原文获取