Combinatorics and Topology Theorem Insights

The Cascade Conjecture, Tverberg sTheorem, Topology and the Four-Color Theorem Gil Kalai Hebrew University of Jerusalem and Reichman University Cascade Lectures in Combinatorics December 14, 2024

TverbergsTheorem (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 ? = 2 is Radon s theorem.)

Sarkariasproof (1993) Colorful Caratheodory (Barany 1978): Let ?1,?2, ,??+1be sets in ??and suppose that 0 ???? ?1 ???? ?2 ???? ( ??+1) Then we can choose ?1 ?1,?2 ?2, ??+1 ??+1such 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 ? ? = ??+1so 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.

The Turan ladder If ? is a ? uniform hypergraph on n vertices and ? has more than (? 1) ? ? edges then : (a) ? contains a subhypergraph ? such that for every set ? of ? vertices is included in no edge or in at least ? edges. Follows (with better bounds) using the polynomial or exterior algebra method. (b) ? contains ? subhypergraph ?1,?2, ,?? such that for every set ? of ? vertices is included in no edge of each or in at least one edge in each. Follows using Tverberg s theoren (c) ? contains a subhypergraph ? such that for every set ? of ? vertices is included in 0 (mod ?) edges. Follows using Chavaley-Warning theorem

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

The minimum number of Tverbergs partition 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.)

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.

The maximum number of Tverbergs partition What is the maximum number of Tverberg s ?-partitions of a (generic) set of (? 1)(? + 1) + 1 points in ?? ? Given ?(? 1) + 1 Gaussian points in ??. The expected number of linear Tverberg partitions is ? 1 ?! ? 2 (There is ?? gap (? ?/2) between the (conjectured) minimum and the expectation, and perhaps the maximum.)

Sylvester problem Problem (Sylvester, 1865): Let K 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? (A year earlier Sylvester published a vaguer version.)

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);