Topological Insights and Conjectures

Helly-Type Problems Gil Kalai Hebrew University of Jerusalem and Reichman University Happy birthday, Micha

Micha and I Subexponential randomized pivot rules for LP Drawing lines on the blackboard 16 Many conferences Videotaped interview last year

Bulletin AMS

1) A peculiar generalization of Hellys Theorem Consider a family of ? + 2 sets in ?-dimensional space, such that the intersection of every ?,1 ? ? + 1 is the union of two disjoint convex compact sets. Then the intersection of all members in the family is non-empty. (Stronger form: the intersection is the union of two disjoint convex compact sets.) Two can perhaps be replaced by three . It cannot be replaced by "48". Perhaps ? + 2 can be replaced by any ? > ? + 1.

2) A Proposed Generalization of the Nerve Theorem We have a family ? of compact sets (or open sets) such that every non- empty intersection is homotopically (homologically) equivalent to ?. Let ? be the nerve of ?. Under which conditions, the union of the sets in F is homotopically (homologically) equivalent to ? ? This is the nerve theorem when ? =point. In general, it does not hold always. The conjecture is that it is true when all intersections are nice . Intersections are nice, if the Meyer-Vietoris long exact sequence splits into short exact sequences in each dimension.

3) Topological VC-dimension and Fractional Helly Conjecture (Kalai and Meshulam): Let ? > 0 be a positive number. Let ? be the hereditary family of simplicial complexes defined by the property that for every simplicial complex ? ? with ? vertices, ?(?) ???. (?(?) is the sum of the Betti numbers of ?). Then for every ? > 0 there is ? = ?(?,?) > 0 such that ? ? and ??(?) ?( ??+1) imply dim(?) ??. The conclusion of the conjecture is referred to as the fractional Helly property of degree ?. We further conjectured that the conclusion holds even if one replaces ?(?) with |?(?)|, where ?(?) is the Euler characteristics of K.

4) Around Katchalskis theorem

5) A conjecture by Gao, Landberg, and Schulman (I will skip it)

6) Mutual position of convex sets

7) An Extension of Radons theorem Estimate ? = ?(?,?,?) the minimum integer such that every set ? of f points in ??can be partitioned into two parts ? and ? such that every union of ? convex sets containing ? intersect every union of ? convex sets containing ?. Estimate ? = ?(?,?,?)

Tverbergs Theorem (1965) Theorem (Tverberg, 65): Let v1,v2, ,??be points in ??, ? ? + 1 ? 1 + 1, then there is a partition ?1,?2, ??of ? such that ???? ??: i ?1 ???? ??,:? ?2 ???? ??:? ?? (The case ? = 2is Radon s theorem.)

Sarkarias proof (1993) Colorful Caratheodory (Barany 1978): Let ?1,?2, ,??+1 be sets in ??and suppose that 0 ???? ?1 ???? ?2 ???? ( ??+1) Then we can choose ?1 ?1,?2 ?2, ??+1 ??+1 such that 0 ???? (?1,?2, ,??+1)

Theorem (Tverberg, 65): Let v1,v2,,??be points in ??, ? = ? + 1 ? 1 + 1. Then there is a partition ?1,?2, ??of ? such that ???? ??: i ?1 ???? ??,:? ?2 ???? ??:? ?? The Proof Organize the points in ? ? = ??+1 so that the sum of coordinates is 1. Let ? = ?? 1, and let ?1,?2, ?? be ? vectors spanning ? whose sum is 0. Now consider the sets ?1, ,?? and apply colorful Caratheodory.

Seven problems 1. Eckhof s partition conjecture(disproved by Boris Bukh, 2010) 2. The Cascade Conjecture (Beautiful conjecture from 1974, wide open with some nice related results by Patrick Schnider.) 3. The minimum number of Tverberg s partitions 4. The topological Tverberg conjecture (Disproved by Florian Frick, based on work by Issak Mabillard and Uli Wagner) 5. Reay s Relaxed Tverberg Condition (Some partial results by Perles and Sidron) 6. Colorful Tverberg theorems (Proved, for prime cases, by Pavle Blagojevic, Benjamin Matschke, and Gunter Ziegler) 7. The computational complexity of Tverberg s theorem

8) The minimum number of Tverbergs partition Sierksma s Duch Cheese Problem Sierksma s Conjecture: The number of Tverberg s?-partitions of a set of (? 1)(? + 1) + 1 points in ?? is at least ?. ? 1 ! Example of equality: ? 1 copies of the vertices of the regular simplex and one point in its center. (Quite a few other examples.)

Results by White, Bukh, Loh, & Nivasch, and Por Theorem (White, 2015): For any partition ?1,?2, ,??: 1 ?? ? + 1 of ?, there exists a set ? ?? of ? points, such that every Tverberg partition of ? induces the same partition on ? given by the parts ?1, ,??. Moreover, the number of Tverberg s partitions of X is ? 1 !? Theorem (Tverberg, 65): Let v1,v2, ,??be points in ??, ? = ? + 1 ? 1 + 1. Then there is a partition ?1,?2, ??of ? such that ???? ??: i ?1 ???? ??,:? ?2 ???? ??:? ??

Results by White, Bukh, Loh, & Nivasch, and Por Theorem (Bukh, Loh, and Nivasch, 2017): Let ? be a tree-like ?-uniform simple hypergraph with ? + 1 edges and ? = (? + 1)(? 1) + 1 vertices. It is possible to associate to the vertices of each such hypergraph ? a set ? of ? points in ?? so that the Tverberg partitions of ? correspond precisely to rainbow coloring of the hypergraph ?. Moreover, the number of rainbow coloring is ? 1 !?. (Here, we consider two colorings as the same if they differ by a permutation of the colors.) Theorem(Por s universality result, 2018): Every long enough sequence of points in ?? in general position contains a subsequence of length ? whose Tverberg partitions are exactly the so called rainbow partitions.

Bukh, Loh, & Nivaschs theorem (? = 4,? = 3) Theorem (Bukh, Loh, and Nivasch, 2017): Let ? be a tree-like ?- uniform simple hypergraph with ?+1 edges and ?=(?+1)(? 1)+1 vertices. It is possible to associate to the vertices of each such hypergraph ? a set ? of ? points in ?^? so that the Tverberg partitions of ? correspond precisely to rainbow coloring of the hypergraph ?. Moreover, the number of rainbow coloring is (? 1)!^?. (Here, we consider two colorings as the same if they differ by a permutation of the colors.)

9) The maximum number of Tverbergs partition

10) The Cascade Conjecture Given a set ? of points ? ={?1,?2, ,??} 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, ?1(?) is just the convex hull of ?. Let ??(?) = dim ??(?) + 1. The cascade conjecture: The cascade conjecture: ?1? + ?2? + + ??? |?|

The Cascade Conjecture Given a set ? of points ? ={?1,?2, ,??} we let ??? be the set of points in ?? which belong to the convex hull of ? pairwise disjoint subsets of ?. Let ??(?) = dim ??(?) + 1. The cascade conjecture: The cascade conjecture: IF ?1? + ?2? + + ??? < |?| Then ??+1X

The Cascade Conjecture (m=1) Given a set ? of points ? ={?1,?2, ,??} we let ??? be the set of points in ?? which belong to the convex hull of ? pairwise disjoint subsets of ?. Let ??(?) = dim ??(?) + 1. The cascade conjecture (m= The cascade conjecture (m=1 1): ): IF ?1? < |?| Then ?2X This is Radon Theorem

The Cascade Conjecture (m=2) Given a set ? of points ? ={?1,?2, ,??} we let ??? be the set of points in ?? which belong to the convex hull of ? pairwise disjoint subsets of ?. Let ??(?) = dim ??(?) + 1. The cascade conjecture (m= The cascade conjecture (m=2 2): OPEN ): OPEN IF ?1? + ?2? < |?| Then ?3X

Topological (speculative) Idea The complex of radon partitions Radon poset of Radon rartitions, (ordered by inclusion) Vertices correspond to minimal radon partitions. (It has a geometric description.) If n=d+2+k then Radon Radon is a ?-dimensional sphere with a ?/2? action. Radon The chain complex of the We have a ?/2?-equivariant map ? from Radon Idea: There is a topological index of ?,?????(?) such that if ?????(?) = 0 then ?3? . Radon to ??

Configuration arising from cubic graphs Let G be a cubic graph with vertices {1,2, ,?}. Associate to every edge {i,j} the characteristic vector: 1 in coordinates i and j , 0 in all other coordinates. This gives us a configuration of 3?/2 points in ?? 1 Observation (Shmuel Onn): The configuration has a Tverberg partition into three parts iff the graph is 3-edge connected.

Research Project Study the complex of Radon partition and the Radon points for configuration arising from (planar and non-planar) cubic graphs Speculative research program: find a connection to the 4CT.

11) Reays conjecture Proposal of Micha Perles: Use the probabilistic method to show that every 2? + 2 points in ?? (maybe even (2 ?)? points) admit a partition into 3 parts such that the convex hull pairwise intersect.

12) Around Sylvester four points problem Problem (Sylvester, 1864,1865): What is the probability that four points in the plane are in convex position? Problem (Sylvester, 1865): Let ? be a convex body in the plane. what is the probability that the convex hull of four randomly distributed points of K are in convex position?

Gaussian Random Points What can be said about Radon and Tverberg partitions for Gaussian random points? Consider ? + 2 points in ?? and let ?? be the probability that the first k points and the last ? + 2 ? points form a Radon partition. Theorem: (Swee Hong Chan, K., Bhargav Narayanan, Natasha Ter- Saakov, Moshe White): The sequence ?? is unimodal.

7 points in ?2

9 points in ?3 We ran 10000000 trials of 9 points in dimension 3, and found: The expected number of Tverberg partitions is 9.7556917, of these: 2242555 trials had 8 partitions; 2377924 trials had 9 partitions; 2581841 trials had 10 partitions; 1658390 trials had 11 partitions; 774253 trials had 12 partitions; 270798 trials had 13 partitions; 74468 trials had 14 partitions; 16391 trials had 15 partitions; 2887 trials had 16 partitions; 435 trials had 17 partitions; 55 trials had 18 partitions; 3 trials had 19 partitions; 6.387536 are of type (2, 3, 4); 3.0308683 are of type (3, 3, 3); 0.3372874 are of type (1, 4, 4);

9 points in ?3 (cont.); 8 partitions 678834 trials had 6 partitions of type (2, 3, 4) and 2 partitions of type (3, 3, 3); 634875 trials had 4 partitions of type (2, 3, 4) and 4 partitions of type (3, 3, 3); 398612 trials had 8 partitions of type (2, 3, 4); 251621 trials had 2 partitions of type (2, 3, 4) and 6 partitions of type (3, 3, 3); 106192 trials had 8 partitions of type (3, 3, 3); 45417 trials had 4 partitions of type (1, 4, 4) and 4 partitions of type (2, 3, 4); 39034 trials had 2 partitions of type (1, 4, 4) and 6 partitions of type (2, 3, 4); 28652 trials had 2 partitions of type (1, 4, 4) and 4 partitions of type (2, 3, 4) and 2 partitions of type (3, 3, 3); 24057 trials had 6 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4); 16728 trials had 8 partitions of type (1, 4, 4); 15896 trials had 4 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4) and 2 partitions of type (3, 3, 3); 1576 trials had 2 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4) and 4 partitions of type (3, 3, 3); 1061 trials had 4 partitions of type (1, 4, 4) and 4 partitions of type (3, 3, 3); 926617 trials had 6 partitions of type (2, 3, 4) and 3 partitions of type (3, 3, 3); 677478 trials had 8 partitions of type (2, 3, 4) and 1 partitions of type (3, 3, 3);

9 points in ?3 (cont.); 9 partitions 447207 trials had 4 partitions of type (2, 3, 4) and 5 partitions of type (3, 3, 3); 100714 trials had 2 partitions of type (1, 4, 4) and 6 partitions of type (2, 3, 4) and 1 partitions of type (3, 3, 3); 86204 trials had 2 partitions of type (2, 3, 4) and 7 partitions of type (3, 3, 3); 61533 trials had 4 partitions of type (1, 4, 4) and 4 partitions of type (2, 3, 4) and 1 partitions of type (3, 3, 3); 43518 trials had 2 partitions of type (1, 4, 4) and 4 partitions of type (2, 3, 4) and 3 partitions of type (3, 3, 3); 18329 trials had 6 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4) and 1 partitions of type (3, 3, 3); 13244 trials had 4 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4) and 3 partitions of type (3, 3, 3); 3080 trials had 2 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4) and 5 partitions of type (3, 3, 3);

9 points in ?3 (cont.); 10 partitions 913887 trials had 8 partitions of type (2, 3, 4) and 2 partitions of type (3, 3, 3); 784893 trials had 6 partitions of type (2, 3, 4) and 4 partitions of type (3, 3, 3); 277831 trials had 4 partitions of type (2, 3, 4) and 6 partitions of type (3, 3, 3); 176131 trials had 10 partitions of type (2, 3, 4); 116697 trials had 2 partitions of type (1, 4, 4) and 6 partitions of type (2, 3, 4) and 2 partitions of type (3, 3, 3); 75548 trials had 2 partitions of type (1, 4, 4) and 8 partitions of type (2, 3, 4); 53813 trials had 4 partitions of type (1, 4, 4) and 4 partitions of type (2, 3, 4) and 2 partitions of type (3, 3, 3); 52279 trials had 4 partitions of type (1, 4, 4) and 6 partitions of type (2, 3, 4); 48139 trials had 2 partitions of type (2, 3, 4) and 8 partitions of type (3, 3, 3); 37685 trials had 2 partitions of type (1, 4, 4) and 4 partitions of type (2, 3, 4) and 4 partitions of type (3, 3, 3); 14878 trials had 4 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4) and 4 partitions of type (3, 3, 3); 9822 trials had 6 partitions of type (1, 4, 4) and 4 partitions of type (2, 3, 4); 6367 trials had 6 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4) and 2 partitions of type (3, 3, 3); 6181 trials had 10 partitions of type (3, 3, 3); 5220 trials had 2 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4) and 6 partitions of type (3, 3, 3); 1931 trials had 4 partitions of type (1, 4, 4) and 6 partitions of type (3, 3, 3); 538 trials had 8 partitions of type (1, 4, 4) and 2 partitions of type (2, 3, 4); 1 trials had 8 partitions of type (1, 4, 4) and 2 partitions of type (3, 3, 3);

9 points in ?3 (cont.); 18,19 partitions 25 trials had 12 partitions of type (2, 3, 4) and 6 partitions of type (3, 3, 3); 19 trials had 14 partitions of type (2, 3, 4) and 4 partitions of type (3, 3, 3); 7 trials had 10 partitions of type (2, 3, 4) and 8 partitions of type (3, 3, 3); 4 trials had 2 partitions of type (1, 4, 4) and 10 partitions of type (2, 3, 4) and 6 partitions of type (3, 3, 3); 2 trials had 14 partitions of type (2, 3, 4) and 5 partitions of type (3, 3, 3); 1 trials had 12 partitions of type (2, 3, 4) and 7 partitions of type (3, 3, 3);

Higher order types