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!
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.
Tverberg’s theorem (1965): Let be points in , . Then there is a partition of such that .
The Cascade Conjecture
Given a set of points in , we let be the set of points in which belong to the convex hull of pairwise disjoint subsets of . (We may allow repetitions among the elements of .) Thus, is just the convex hull of .
Radon’s theorem: If then .
Radon theorem is a simple consequence of the fact that points in an affine space of dimension are affinely dependent. (Note that is one plus the dimension of the affine span of .)
It seems that the following conjecture requires some “higher linear algebra”
Conjecture 1: If then .
Conjecture 1 is wide open. It is a special case of the following more general conjecture
Conjecture 2 (The Cascade Conjecture): If then .
Another formulation of Conjecture 2 is
The Cascade Conjecture: .
Of course, the cascade conjecture implies Tverberg’s theorem since given points in , we have that , and therefore the conjecture implies that .
For the 5-point configuration on the left and . For the configuration on the right and . Indeed also
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 be the set of points in which belong to the positive hull of pairwise disjoint subsets of . and let .
The Cascade conjecture asserts in this form that if then (or in other words .)
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 in that guarantee that .
Edge coloring of cubic graphs
Let be a cubic graph with vertices . Associate to a point configuration in : for every edge associate where is the standard basis. is a point configuration in a -dimensional real space, and Shmuel Onn first observed that if and only if 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 .
Here are earlier posts related to Helly type theorems, and a paper devoted to Imre Barany’s birthday with various Helly-type open problems.