Gil Kalai’s blog

## Colorful Caratheodory Revisited

Posted on March 15, 2009 by

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.

### Like this:

This entry was posted in Convexity and tagged Helly type theorems. 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.

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 17, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9397937059402466, "perplexity_flag": "middle"}