Seven Problems Around Tverberg’s Theorem

Imre Barany, Rade Zivaljevic, Helge Tverberg, and Sinisa Vrecica

Recall the beautiful theorem of Tverberg: (We devoted two posts (I, II) to its background and proof.)

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$.

The (much easier) case $r=2$ of Tverberg’s theorem is Radon’s theorem.

1. Eckhoff’s Partition Conjecture

Eckhoff raised the possibility of finding a purely combinatorial proof of Tverberg’s theorem based on Radon’s theorem. He considered replacing the operation : “taking the convex hull of a set $A$” by an arbitrary closure operation.

Let $X$  be a set endowed with an abstract closure operation $X \to cl(X)$. The only requirements of the closure operation are:

(1) $cl(cl (X))=cl(X)$ and

(2) $A \subset B$ implies $cl(A) \subset cl (B)$.

Define $t_r(X)$ to be the largest size of a (multi)set in $X$ which cannot be partitioned into $r$ parts whose closures have a point in common.

Eckhoff’s Partition Conjecture: For every closure operation $t_r \le t_2 \cdot (r-1).$

If $X$ is the set of subsets of $R^d$ and $cl(A)$ is the convex hull operation then Radon’s theorem asserts that $t_2(X)=d+1$ and Eckhoff’s partition conjecture would imply Tverberg’s theorem. Update (December 2010): Eckhoff’s partition conjecture was refuted by Boris Bukh. Here is the paper.

2. The dimension of Tverberg’s points

For a set $A$, denote by $T_r(A)$ those points in $R^d$ which belong to the convex hull of $r$ pairwise disjoint subsets of $X$. We call these points Tverberg points of order $r$.

Conjecture (Kalai, 1974): For every $A \subset R^d$ , $\sum_{r=1}^{|A|} {\rm dim} T_r(A) \ge 0$.

Question: Let $Q_n=[-\frac 12,\frac 12]^n\subseteq {\bf R}^n$ be the cube in ${\bf R}^n$ centered at the origin and having $n$-dimensional volume equal to one.  What is the maximum $(n-1)$-dimensional volume $M(d)$ of $(H\cap Q_n)$ when $H \subseteq {\bf R}^n$ is a hyperplane?

Can you guess the behavior of $M(n)$ when $n \to \infty$? Can you guess the plane which maximizes the area of intersection for $n=3$?

Sarkaria’s Proof of Tverberg’s Theorem 2

Karanbir Sarkaria

4. Sarkaria’s proof:

Tverberg’s theorem (1965): Let $v_1, v_2,\dots, v_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 (v_i: i \in S_j) \ne \emptyset$.

Proof: We can assume that $m=(r-1)(d+1)+1$. First suppose that the points $v_1, v_2,\dots,v_m$ belong to the $d$-dimensional affine space $H$ in $V=R^{d+1}$ of points with the property that the sum of all coordinates is 1. Next consider another $(r-1)$-dimensional vector space $W$ and $r$ vectors in $W$, $w_1,w_2, \dots, w_r$  such that $w_1+w_2+\dots +w_r = 0$  is the only linear relation among the $w_i$s. (So we can take $w_1,\dots w_{r-1}$ as the standard basis in $R^{r-1}$ and $w_r=-w_1-w_2-\dots-w_r$. )

Now we consider the tensor product $V \otimes W$.

Nothing to be scared of: $U=V \otimes W$ can be regarded just as the $(d+1)(r-1)$-dimensional vector space of d+1  by $r-1$ matrices. We can define the tensor product  $x \otimes y$ of two vectors $x = (x_1,x_2,\dots,x_{d+1}) \in V$ and $y =(y_1,y_2,\dots,y_{r-1}) \in W$, as the (rank-one) matrix $(x_i \cdot y_j)_{1 \le i \le d+1,1 \le j \le r-1}$.

Consider in U the following sets of points:

$S_1 = \{v_1 \otimes w_j: j=1,2,\dots r \}$

$S_2 = \{v_2 \otimes w_j: j=1,2,\dots r \}$

$S_i = \{v_i \otimes w_j: j=1,2,\dots r \}$

$S_m = \{v_m \otimes w_j: j=1,2,\dots r \}.$

Note that 0 is in the convex hull of every $S_i$. Indeed it is the sum of the elements in $S_j$. (And thus $0=1/r(v_i \otimes w_1+ v_i \otimes w_2 + \dots + v_i \otimes w_r)$. )

By the Colorful Caratheodory Theorem we can  Continue reading

Sarkaria’s Proof of Tverberg’s Theorem 1

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: 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 $\lambda$s 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_j$s 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_j$s. Ahla.

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, Cayley, Hypertrees, and Weighted Enumeration III

This is the third and last part of the journey from a Helly type conjecture of Katchalski and Perles to a Cayley’s type formula for “hypertrees”.  (On second thought I decided to divide it into two devoting the second to probabilistic questions.) This part will include several diversions, open problems, and speculations.

11. How to make it work – the matrix tree theorem

Our high dimensional extension to Cayley’s theorem reads:

$\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), the proof that I know to apply is the one based on the matrix tree theorem.

Consider the signed incidence matrix A’ between all (d+1)-subsets and all d-subsets of {1,2,…,n} that represents the boundary operator of simplicial homology. The rank of this matrix is ${n-1} \choose {d}$, and just like in the ordinary matrix tree theorem you delete rows to be left with linearly independent rows. Here you delete all rows corresponding to sets containing ‘n’ and you are left with a matrix A. Now we compute the determinant of $det (A \cdot A^{tr})$ directly, and compare the result to a computation based on the Cauchy-Binet Formula.

The eigenvalues of $A \cdot A^{tr}$ are the eigenvalues of the d-th Laplacian of the complete d-dimensional simplicial complex with n vertices. It is easy to inspect what they are and the determinant of $A \cdot A^{tr}$ is indeed $n^{{n-2} \choose {d}}$.

The many square determinants correspond to d-dimensional simplicial complexes K on our labelled set of vertices, which satisfy $f_{d-1}(K) = {{n} \choose {d}}$ and $f_d(K) = {{n-1} \choose {d}}$. Now if K has non-vanishing d-th homology, the determinant is zero. If K is a Q-acyclic simplicial complex (i.e., its (reduced) homology groups with rational coefficients are trivial) then it has a non zero determinant. So far, it is like trees, but next comes a surprise. The contribution of K is the square of the number of elements in $H_{d-1}(K)$, the (d-1)th homology group of K. This torsion group is finite, but for d >1 it need not be trivial.

Emily Peters presents the matrix-tree theorem. From The Sarong Theorem Archive” – an electronic archive of images of people proving theorems while wearing sarongs.

12. An even simpler use of Cauchy-Binet worth knowing

Consider the $n \times 2^n$ matrix A, whose columns are all +1 -1 vectors of length n. Computing $det A A^{tr}$, via Cauchy-Binet Formula (or by other easy methods) asserts that the expected value $(det (B))^2$ for all $n \times n$  +1/-1 matrices behaves roughly like $(n!)$. This was observed by Turan and Szekeres who also found a formula for the sum of the fourth powers of all 0-1 n by n matrices. See a leter paper by Turan. (I am not aware of a similar formula for the fourth power of the size of the homology groups for hypertrees.) Much is known about the determinant and related properties of random 0-1 matrices and the analogy between torsion in the homology groups of random complexes and determinants of random matrices looks like a good analogy.

13. Torsion

One consequence of the formula compared to the total number of available simplicial complexes is that the torsion group is typically huge. (For d>1, the expected value of $|H_{d-1}(K,{\bf Z})|^2$ for Q-acyclic complexes counted by the formula, is asymptotically larger than $((d+1)/e)^{{n-2} \choose {d}}$; I am not aware of explicit examples with such a huge torsion group.)

How should we think about torsion in homology? It seems that thinking about the size of the torsion as a behaving like the determinant of a random matrix, may give a good intuition for many cases.

14. Extending other proofs for Cayley’s theorem?

Cayley’s counting trees theorem has many wonderful proofs.  Can any other proof extend to the case of Q-acyclic simplicial complexes? For example, one proof relies on the exponential theorem that relates the exponential generating functions for connected and general graphs with a certain property P. (Followed by the Lagrange inversion formula.) Is there an analog of the exponential formula when connectivity is replaced by higher homology? Is there any analog of Prüfer sequences? I am not aware of any other proof that works.

15. Weights to the rescue of other conjectures?

Can we use subtle weights to save other promising but false enumerative conjectures? The farthest reaching fantasy in this direction 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.

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

Helly’s Theorem, “Hypertrees”, and Strange Enumeration I

1. Helly’s theorem and Cayley’s formula

Helly’s theorem asserts: For a family of n convex sets in $R^d$, n > d, if every d+1 sets in the family have a point in common then all members in the family have a point in common.

Cayley’s formula asserts: The number of  trees on n labelled vertices is $n ^{n-2}$.

In this post (in two parts) we will see how an extension of Helly’s theorem has led to high dimensional analogs of Cayley’s theorem.

left: Helly’s theorem demonstrated in the Stanford Encyclopedia of Philosophy (!), right: a tree

2. Background

This post is based on my lecture at Marburg. The conference there was a celebration of new doctoral theses Continue reading