The seminar meets on Mondays, 14:10-15:10, in -101

Spring 2018 meetings

Mar 5, 14:00–15:00 Constructive Polynomial Partitioning for Lines in R^3 and its Applications Esther Ezra (Bar Ilan)

A recent extension of Guth (2015) to the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial, for a given set of $k$-dimensional varieties in ${\reals}^d$, which subdivides space into open cells each of which meeting only a small fraction of the total number of varieties. For most instances, it is unknown how to efficiently obtain an explicit representation of such a partitioning polynomial. This, in particular, applies to the(simple) case of lines in 3-space. In this work we present an efficient algorithmic (but somewhat suboptimal) construction for this setting. We then revisit the problem of eliminating depth cycles among $n$ non-vertical pairwise disjoint triangles in $3$-space, recently been studied by Aronov etal. (2017) and de Berg (2017). Our main result is an algorithmic $O(n^{5/3+\eps})$ bound, for any $\eps > 0$, on the number of pieces one needs to cut the triangles such that the depth relation they induce does not contain cycles. The running time of our algorithm is comparable with the combinatorial bound.

Joint work with Boris Aronov.

Mar 12 Conical partitions for point sets Gabor Damasdi (HUJI)

Mass partition theorems like the Ham-Sandwich theorem have been extensively studied in recent decades. Conical partitions have been mainly considered in the planar case, but some higher dimensional results have been obtained by Vrecica and Zivaljevic and by Makeev. The proof of mass partition theorems usually follows the configuration space/test map procedure or some degree theoretic method, both of which heavily rely on topological results. This is especially true for results in higher dimensions, where our combinatorial tools are limited. We show a completely combinatorial proof for a discrete version of a theorem of Vrecica and Zivaljevic concerning conical partitions, and we show an equivalent result on the number of regions in a conical decomposition.

Seminar run by Dr Charles Wolf