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.

Sarkaria’s Proof of Tverberg’s Theorem 1

Helge Tverberg

Helge Tverberg

Ladies and gentlemen, this is an excellent time to tell you about the beautiful theorem of Tverberg and the startling proof of Sarkaria to Tverberg’s theorem (two parts). A good place to start is Radon’s theorem.

1. The theorems of Radon, Helly, and Caratheodory.

Radon’s theorem

Radon’s theorem: Let x_1,x_2,\dots, x_m be points in R^d, m \ge d+2. Then there is a partition S,T of \{1,2,\dots,m\} such that conv(x_i: i \in S) \cap conv(x_i: i \in T) \ne \emptyset.  (Such a partition is called a Radon partition.)

Proof: Since m>d+1 the points x_1,x_2, \dots, x_m are affinely dependent. Namely, there are coefficients, not all zero,  \lambda_1,\lambda_2,\dots,\lambda_m such that \sum _{i=1}^m \lambda_i x_i = 0 and \sum _{i=1}^m \lambda_i=0. Now we can write S=\{i:\lambda_i >0\} and T = \{i: \lambda_i \le 0\}, and note that

(*) \sum_{i \in S} \lambda_i x_i = \sum _{i \in T} (-\lambda_i) x_i,

and also \sum _{i \in S} \lambda_i = \sum_{i \in T} (-\lambda_i). This last sum is positive because not all the \lambdas are equal to zero. We call it t.

To exhibit a convex combination of x_i: i\in S which is equal to a convex combination in x_i: i \in T just divide relation (*) by t. Walla.

This trick of basing a partition on the signs of the coefficients repeats in other proofs. Take note!

Radon used his theorem to prove Helly’s theorem.

Helly’s theorem

Helly’s theorem: For a family K_1,K_2,\dots, K_n, n \ge d+1, of convex sets in R^d, if every d+1 of the sets have a point in common then all of the sets have a point in common.

Proof: It is enough to show that when n> d+1 if every n-1 of the sets have a point in common then there is a point in common to them all. Let x_k \in \cap\{K_j: 1\le j\le n, j \ne k\}. In words, x_k is a point that belongs to all the K_js except perhaps to K_k. We assumed that such a point x_k exists for every k.

Now we can apply Radon’s theorem: Consider the Radon partition of the points, namely a partition S,T of \{1,2,\dots,m\} such that conv(x_i: i \in S) \cap conv(x_i: i \in T) \ne \emptyset.  Let z \in conv(x_i: i \in S) \cap conv (x_i: i \in T). Since z belongs to the convex hull of  conv (x_i: i \in S) and every x_i for i \in S belongs to every K_j for every j not in S we obtain that z belongs to every K_j for j not in S. By the same argument z belongs to every K_j for j not in T. Since S and T are disjoint, the point z belongs to all K_js. Ahla.

helly

The proof of Helly’s theorem from Radon’s theorem as described on the cover of a book by Steven R. Lay

Caratheodory’s theorem

Caratheodory’s theorem: For S \subset R^d, if x \in conv (S) then x \in conv (R) for some R \subset S, |R| \le d+1.

Like for Radon’s theorem, there is a simple linear algebra proof. We can assume that S is finite; we start with a presentation of x as a convex combination of vectors in S, and if |S|>d+1 we can use an affine dependency among the vectors in S to change the convex combination, forcing one coefficient to vanish.

Without further ado here is Tverberg’s theorem.

2. Tverberg’s Theorem

Tverberg Theorem (1965):Let x_1,x_2,\dots, x_m be points in R^d, m \ge (r-1)(d+1)+1. Then there is a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that \cap _{j=1}^rconv (x_i: i \in S_j) \ne \emptyset.

So Tverberg’s theorem is very similar to Radon’s theorem except that we want more than two parts! Continue reading

Helly’s Theorem, “Hypertrees”, and Strange Enumeration II: The Formula

In the first part of this post we discussed an appealing conjecture regaring an extension of Cayley’s counting trees formula. The number of d-dimensional “hypertrees” should somehow add up  to n^{{n-2} \choose {d}}. But it was not clear to us which complexes we want to count and how. This counting problem started from a Helly type conjecture proposed by Katchalski and Perles.
For d=2 n=6 the situation was confusing. We had 46608 complexes that were collapsible. Namely, for these complexes it is possible to delete all triangles one at a time by removing in each step a triangle T and an edge E which is contained only in T. Once all triangles are removed we are left with a spanning tree on our 6 vertices. (Five out of the 15 edges survive).  In addition, there were 12 simplicial complexes representing 6-vertex triangulations of the real projective plane. 
We will continue the discussion in this part, show how the conjecture can be saved and at what cost. We will also discuss the solution of the Perles-Katchalski conjecture –  a Helly’s type conjecture that we started with.   In the third part we will explain the proof and mention further related results and problems, discuss higher Laplacians and their spectrum, and mention a few related probabilistic problems.  
 
 

 We ended part one with the question “What can we do?”

8. How to make the conjecture work

With such a nice conjecture we should not take no for an answer. To make the conjecture work we need to count each of the twelve 6-vertex triangulations of the real projective plane, four times. Four is the square of the number of elements in H_1(RP^2). This is the difference in higher dimensions, a Q-acyclic complex need not be Z-acyclic. Homology groups can have non trivial torsion.  In our case H_{d-1}(K) can be a non trivial finite group.
Here is the theorem:   

\sum |H_{d-1}(K,{\bf Z})|^2 = n^{{n-2} \choose {d}},

where the sum is over all d-dimensional simplicial complexes K on n labelled vertices, with a complete (d-1)-dimensional skeleton, and which are Q-acyclic, namely all their (reduced) homology groups with rational coefficients vanish.  
Looking at the various proofs of Cayley’s formula (there are many many many beautiful proofs and more), which one (or more) would you expect to extend to the high dimensional case? We will answer this question in part III. Can you guess? Continue reading