Colorful Caratheodory Revisited

caratheodory-colored

 

Janos Pach wrote me:   “I saw that you several times returned to the colored Caratheodory and Helly theorems and related stuff, so I thought that you may be interested in the enclosed paper by Holmsen, Tverberg and me, in which – to our greatest surprise – we found that the right condition in the colored Caratheodory theorem is not that every color class contains the origin in its convex hull, but that the union of every pair of color classes contains the origin in its convex hull. This already guarantees that one can pick a point of each color so that the simplex induced by them contains the origin. A similar version of the colored Helly theorem holds. Did you know this?”

I did not know it. This is very surprising! The paper of Holmsen, Pach and Tverberg mentions that this extension was discovered independently by  J. L. Arocha, I. B´ar´any, J. Bracho, R. Fabila and L. Montejano.

Let me just mention the colorful Caratheodory agai. (we discussed it among various Helly-type theorems in the post on Tverberg’s theorem.)

The Colorful Caratheodory Theorem: Let S_1, S_2, \dots S_{d+1} be d+1 sets in R^d. Suppose that x \in conv(S_1) \cap conv (S_2) \cap conv (S_3) \cap \dots \cap conv (S_{d+1}). Then there are x_1 \in S_1, x_2 \in S_2, \dots x_{d+1} \in S_{d+1} such that x \in conv (x_1,x_2,\dots,x_{d+1}).

And the strong theorem is:

The Strong Colorful Caratheodory Theorem: Let S_1, S_2, \dots S_{d+1} be d+1 sets in R^d. Suppose that x \in conv(S_i \cup S_j)  for every 1 \le i <j \le d+1. Then there are x_1 \in S_1, x_2 \in S_2, \dots x_{d+1} \in S_{d+1} such that x \in conv (x_1,x_2,\dots,x_{d+1}).

Janos, whom I first met thirty years ago,  and who gave the second-most surprising introduction to a talk I gave, started his email with the following questions:

“Time to time I visit your lively blog on the web, although I am still not quite sure what a blog is… What is wordpress? Do you need to open an account with them in order to post things? Is there a special software they provide online which makes it easy to include pictures etc? How much time does it take to maintain such a site?”

These are excellent questions that may interest others and I promised Janos that I will reply on the blog. So I plan comments on these questions in some later post. Meanwhile any comments from the floor are welcome.

About these ads
This entry was posted in Convexity and tagged . Bookmark the permalink.

2 Responses to Colorful Caratheodory Revisited

  1. Edna says:

    What is the first most surprising introduction? I hope it’s not the answer I am afraid you will give…

  2. Gil says:

    Dear Edna, there is nothing to be afraid of. Indeed Avi’s introduction was the most surprising ever, and quite hilarious. As Avi promised to put it in writing for the back cover of my book, it will reach the large audience it deserves. Even now people who listened to that introduction ask me about the imortal translation to English to “where is Pluto” and some subtelties of the “cut its head/cut its tail” game.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s