From: lrudolph@panix.com (Lee Rudolph) Subject: Re: Minimal number of elements in a convex combination Date: 6 Mar 2000 03:00:01 -0600 Newsgroups: sci.math.research Summary: Caratheodory's Theorem [Dagnab it, simply removing "NO", "SPAM", and ".invalid" from the following address didn't work: the server exists but it claims that the user is unknown. If people must do this sort of spoofing, they really should include despoofing clues in their .sigs or something, if they want replies.] Pedro "Tern" writes: >Let K be a compact subset of R^n. Then any point of its convex >hull, denoted coK, can be put as a convex combination of at most >(n+1) points of K. (I was taught this to be "Caratheodory's >Theorem") > >My question is: Can the number (n+1) be reduced under additional >hypotheses on K? > >I'm working with some sets having a complicated expression, so I >don't know exactly which of their particular properties could be >relevant to this. These sets are images of the closed unit ball >by some continuous functions. > >What I think (what I "wish", anyway) is that maybe the fact that >they are connected (particularly that each two points of K can be >joined by an arc) is enough to enable us to put each point of coK >as a convex combination of only 2 points of K. ... That wish, at least, can't be granted. Consider a 3-frame in R^3 (say, the union of the unit intervals on each of the three axes). It's connected (and the image of the ball by a continuous map, too). No interior point of the triangle with vertices at the 3 endpoints is a convex combination of only 2 points of the frame (because any such combination lies in one of the coordinate planes), though of course all such points are in the convex hull. I could be making a silly mistake, but it seems to me that the obvious generalization shows that in R^n you may need up to n points. I don't know if you ever need n+1, but I bet you do (and I'll bet it's well known to those who know it well). Lee Rudolph ============================================================================== From: hrubin@stat.purdue.edu (Herman Rubin) Subject: Re: Minimal number of elements in a convex combination Date: 6 Mar 2000 03:00:11 -0600 Newsgroups: sci.math.research In article <11429f39.a13d44a5@usw-ex0104-026.remarq.com>, Pedro "Tern" wrote: >Let K be a compact subset of R^n. Then any point of its convex >hull, denoted coK, can be put as a convex combination of at most >(n+1) points of K. (I was taught this to be "Carathodory's >Theorem") >My question is: Can the number (n+1) be reduced under additional >hypotheses on K? >I'm working with some sets having a complicated expression, so I >don't know exactly which of their particular properties could be >relevant to this. These sets are images of the closed unit ball >by some continuous functions. >What I think (what I "wish", anyway) is that maybe the fact that >they are connected (particularly that each two points of K can be >joined by an arc) is enough to enable us to put each point of coK >as a convex combination of only 2 points of K. >Even if this is false, I'm still interested in knowing some >conditions under which the number (n+1) can be taken smaller. For connected sets, the number can be reduced to n. The proof is not difficult. For points parametrized by 1, x, ... , x^n, the number is a little more than n/2; see a book on the geometry of moments for the proof; it is a little harder. End points count as 1/2 point in the complete theorem. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 ============================================================================== From: israel@math.ubc.ca (Robert Israel) Subject: Re: Minimal number of elements in a convex combination Date: 6 Mar 2000 03:00:14 -0600 Newsgroups: sci.math.research In article <11429f39.a13d44a5@usw-ex0104-026.remarq.com>, Pedro "Terán" wrote: [See above -- djr] Two points are not enough. Consider, for example, a "tripod" K in R^3 consisting of three non-coplanar line segments joined at one vertex. Any point that is a convex combination of two points of the tripod is on one of the three planes determined by pairs of segments. So you need at least three points of K to get any of the other points of coK. However, it is true that you can get by with n points if K is connected. Suppose p is a convex combination of n+1 points x_0, x_1, ..., x_n of K, but not of fewer than n+1. Let V = { x in K: p is a convex combination of x, x_1, ..., x_n}. Then V is compact and contains x_0 but no other x_i. Since K is connected, K\V is not closed. So some point of V is the limit of a sequence y_j in K\V. For convenience, I'll assume x_0 is such a point. Now for each y_j, p can be separated from y_j, x_1,...,x_n by a hyperplane, i.e. there is a unit vector v_j such that v_j.(y_j-p) and v_j.(x_i-p) for i=1...n are all positive. Taing a limit point as j -> infinity, there is a unit vector v such that v.(x_i-p) for i=0...n are all non-negative. Now if any v.(x_i-p) > 0, in any expression of p as a convex combination of x_0 ... x_n the coefficient of x_i must be 0 (which leaves p as a convex combination of n points). On the other hand, if all v.(x_i-p) = 0, then we can apply Caratheodory's result to the hyperplane containing p and the x_i, to find again that p is a convex combination of n of the points x_i. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: =?iso-8859-2?Q?Szymon_W=B1sowicz?= Subject: Re: Minimal number of elements in a convex combination Date: 6 Mar 2000 03:10:03 -0600 Newsgroups: sci.math.research > My question is: Can the number (n+1) be reduced under additional > hypotheses on K? > > What I think (what I "wish", anyway) is that maybe the fact that > they are connected (particularly that each two points of K can be > joined by an arc) is enough to enable us to put each point of coK > as a convex combination of only 2 points of K. I don't know what to think on your idea. First I supposed that this is not true and as a counterexample I tried to take a simplex in R^3 with its skeleton as K. But in that case your idea works. I know a theorem on reducing Caratheodory's n+1 points to at most n points. As I know, some results of that spirit can be found in a book "Convex Sets" by F.A. Valentine, Mc Graw-Hill, 1964. One of them is the following (page 169, Prop. 3.3) proposition due to Hanner and Radstrom (A Generalization of a Theorem of Fenchel, Proc. Amer. Math. Soc. 2(1951), 589-593): Let S be a subset of R^n and suppose that either (a) S is the union of n connected sets or (b) S is compact and no hyperplane in R^n exists which strictly separates two nonempty disjoint subsets S_1,S_2 of S such that S_1 \cup S_2 = S. Then each point of coS is a convex combination of n or fewer points of S. In my opinion a theorem on reducing the length of a convex combination to 2 would be excellent. It would be an useful tool to prove new sandwich theorems. What I understand as a sandwich theorem? We have two real functions f \leq g and we ask under which conditions there exists a function h with some special properties such that f \leq h\leq g (for ex. it is known that if f is concave and g is convex and f and g are defined on a real interval then they can be separated by affine function). -- Best regards, Szymon swasowicz@pb.bielsko.pl ============================================================================== From: Ronald Bruck Subject: Re: Minimal number of elements in a convex combination Date: 6 Mar 2000 11:00:03 -0600 Newsgroups: sci.math.research In article <11429f39.a13d44a5@usw-ex0104-026.remarq.com>, Pedro "Terán" wrote: [See above -- djr] I don't quite see how you expect something like this to be true. The number of points of K required to give a convex combination is a function of the DIMENSION of K, and joining points by arcs does nothing to reduce dimension, unless you know more about the curves. Probably not relevant to your question, but who knows: there are results in certain infinite-dimensional spaces (specifically, B-convex Banach spaces) which assure that for each eps > 0 there exists an integer n > 0 such that each point of co K can be approximated within eps by a combination of no more than n points of K. (K has to be bounded, and n will depend on the diameter of K as well as eps.) In "nice" spaces, e.g. as I recall uniformly convex Banach spaces [which are automatically B-convex], n is in principle constructable. In this way, if you allow some "slop" eps, you can replace arbitrary convex combinations by convex combinations of a fixed size. I proved this in the Israel J. Math. 38 (1981), 304-314 (although the main point of that paper was something else). --Ron Bruck -- Due to University fiscal constraints, all .sigs must be only one line. ============================================================================== From: "Alexander Borisov" Subject: Re: Minimal number of elements in a convex combination Date: Wed, 8 Mar 2000 18:35:31 -0500 Newsgroups: sci.math.research Hi, I tried to post this, in a slightly different form, a few days ago, but for some reasons it didn't go through. There is at least one example of the situation when the number of points can be reduced to less than $n$ for the cpnnected sets. Namely, consider a convex polyhedron $P$ in $R^3$. Consider the compact connected set $K$ of points on its edges and vertices. Then every point in the convex hull of $K$ actually belongs to some segment with vertices in $K$. So the minimal number of points is 2 rather than 3. The proof is fairly simple. For points on the boundary of $P$ it is trivial. So suppose $O$ is a point inside $P$. Take the anti-projection of $K$ through $O$ to the boundary of $P$ (i.e. for every point in $K$ take the line that connects it with $O$ and find the other intersection with the boundary of $P$. Because $P$ is convex the image of the anti-projection is not entirely contained in any face of $P$. So, because it is convex, it must intersect $K$. This gives a segment that contains $O$. I am sure that your situation is quite different. But maybe the proof is of some interest. Alexander Borisov borisov@math.wustl... [Original post quoted again; see above --djr]