Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture

Kazhdan’s Basic Notion Seminar is back!

The “basic notion seminar” is an initiative of David Kazhdan who joined the Hebrew University math department  around 2000. People give series of lectures about basic mathematics (or not so basic at times). Usually, speakers do not talk about their own research and not even always about their field. My first lecture series around 2004 was about computational complexity theory, and another one on extremal combinatorics developed into a series of posts (I,II,III,IV,VI). Since then I talked in the seminar about various other topics like convex polytopes, generalization of planar graphs, and Boolean functions. The seminar did not operate for a few years and we were all very happy to have it back last spring!

Helly-type theorems

I just finished two lectures on Helly-type theorems in the basic notions seminar. which is the topic of my doctoral thesis. (I am interested in Helly type theorems since I was an undergraduate student.) Recently, Helly-type theorems where involved in the study of high dimensional expanders and other topics in high dimensional combinatorics. Alex Lubotzky and Tali Kaufman are running now a special year at the IIAS devoted to high dimensional combinatorics so I thought it would be nice to devote a basic notion seminar to this topic.

My first talk followed quite closely these two posts (I,II). Let me devote this post to the “cascade conjecture” which is a generalization of Tverberg’s theorem.

Tverberg’s theorem (1965): Let v_1, v_2,\dots, v_m be points in \mathbb 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.

The Cascade Conjecture

Given a set X of points  in \mathbb R^d, X= \{ x_1,x_2,\dots ,x_n \} we let  T_r(X) be the set of  points in \mathbb R^d which belong to the convex hull of r pairwise disjoint subsets of X. (We may allow repetitions among the elements of X.) Thus, T_1(X) is just the convex hull of X.

Let \bar t_r(X)=\dim T_r(X)+1.

Radon’s theorem:  If \bar t_1(X) < |X| then \bar t_2(X)>0.

Radon theorem is a simple consequence of the fact that d+2 points in an affine space of dimension d are affinely dependent. (Note that t_1(X) is one plus the dimension of the affine span of X.)

It seems that the following conjecture requires some “higher linear algebra”

Conjecture 1: If \bar t_1(X)+ \bar t_2(X) < |X| then \bar t_3(X)>0.

Conjecture 1 is wide open. It is a special case of the following more general conjecture

Conjecture 2 (The Cascade Conjecture): If \bar t_1(X)+ \bar t_2(C) +\cdots+\bar t_r(X) < |X| then \bar t_{r+1}(X)>0.

Another formulation of Conjecture 2 is

The Cascade Conjecture: \sum_{i=1}^{|X|} \bar t_i(X) \ge |X|.

Of course, the cascade conjecture implies Tverberg’s theorem since given (r-1)(d+1)+1 points in \mathbb R^d, we have that \sum_{i=1}^{r-1} \bar t_i(X) \le (d+1)(r-1) < |X|, and therefore the conjecture implies that T_r(X) \ne \emptyset.

For the 5-point configuration on the left \bar t_1=3 and \bar t_2=2. For the configuration on the right \bar t_1=3 and \bar t_2=1. Indeed also \bar t_3=1

There are two facts about the cascade conjecture that are separately quite innocuous but combined are mind blogging. The first fact is that the conjecture was made in 1974, namely 43 years ago. The second fact is that the conjecture was made by me!

Remarks: 1) Instead of talking about convex hulls we can consider a set of points that do not positively span the origin. Then we can define S_r(X) be the set of  points in \mathbb R^d which belong to the positive hull of r pairwise disjoint subsets of X. and let s_r(X)=\dim S_r(X).

The Cascade conjecture asserts in this form that if s_1(X)+ s_2(C) +\cdots+s_r(X) < |X| then s_{r+1}(X)>0 (or in other words \sum_{i=1}^{|X|} s_i(X) \ge |X|.)

2) Conjecture 1 can be seen as a special case of the following more general problem.

Problem 3: Find conditions on the Radon partitions and Radon points of a point configuration X in \mathbb R^d that guarantee that T_3(X) \ne \emptyset.

Edge coloring of cubic graphs

Let G be a cubic graph with n vertices \{1,2,\dots ,n\}. Associate to G a point configuration X in \mathbb R^n: for every edge \{i,j\} associate e_i+e_j where e_1,e_2,\dots ,e_n is the standard basis. X is a point configuration in a (n-1)-dimensional real space, and Shmuel Onn first observed that T_3(X) \ne \emptyset if and only if G is 3-edge colorable.

Problem 4: Study Radon partitions and Radon points of point configuration based on cubic graphs.

Of special interest are bipartite cubic graphs, planar cubic graphs, and 4-edge colorable planar graphs like the Petersen graph.

Of course, a major problem for me is simply to understand Tverberg’s theorem. The topological Tverberg conjecture suggested  a topological explanation and Eckhoff’s partition conjecture suggested a purely combinatorial explanation (see this post). Both these conjectures were refuted.

Weak epsilon nets, fractional Helly, and nerves of convex Sets

My second lecture in the basic notion seminar started with the cascade conjecture and next discussed the existence of weak epsilon nets and the basic question about finding bounds for their size. My first ever blog post over Terry Tao’s blog was about weak epsilon nets and since then there were exciting developments that I hope to return to soon. Then I moved to talk about fractional Helly theorems and the last topic was what can be said about nerves of convex sets in \mathbb R^d.

Here are earlier posts related to  Helly type theorems, and a paper devoted to Imre Barany’s birthday with various Helly-type open problems.

This entry was posted in Combinatorics, Convexity, Open problems and tagged , , . Bookmark the permalink.

4 Responses to Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture

  1. shacharlovett says:

    Thanks for the post. For conjecture 1, is a weaker version known?

    • Gil Kalai says:

      Dear Shachar, The case d=2 of the cascade conjecture was proved by Akiva Kadari around 1980. I am not aware of known weaker versions of Conjecture 1. It will be nice to prove the conjecture even if you replace \dim T_r(X) by \dim conv (T_r(X)) but also this is unknown.

  2. Bobito says:

    Kazhdan left (not joined) Harvard around 2000.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s