This page list all events and seminars that take place in the department this week. Please use the form below to choose a different week or date range.

Combinatorics Seminar

Constructive Polynomial Partitioning for Lines in R^3 and its Applications

Mar 5, 14:00-15:00, 2018, -101


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.


Quantitative Helly-type theorems

Mar 6, 14:30-15:30, 2018, Math -101


Khaya Keller (BGU)


The classical Helly’s theorem, dated 1923, asserts that if F is a family of compact convex sets in R^d such that any d+1 sets of F have a non-empty intersection, then all sets of F can be pierced by a single point. Helly’s theorem is a cornerstone in convexity theory, and the need to generalize and extend it has led mathematicians to deep and fascinating new research directions. One of the best-known extensions is the Alon-Kleitman (p,q) theorem (1992) which asserts that for F as above, if among any p sets of F some q intersect (for q>d), then all sets of F can be pierced by a bounded number c(p,q,d) of points.

In this talk we survey the quest for quantitative Helly-type theorems which aim at finding effective bounds on the piercing numbers in various scenarios. We present new bounds on c(p,q,d) for the Alon-Kleitman theorem, which are almost tight for a wide range of parameters. We also show that for several large classes of families, quantitative (p,2) theorems in the plane can be obtained, providing a strong connection between the piercing number of a family to its well-studied packing number, and giving rise to new Ramsey-type theorems.

Based on joint works with Shakhar Smorodinsky and Gabor Tardos.

Research Features

Algebraic Geometry and Number Theory

Equations with singular moduli: effective aspects

Mar 7, 15:10-16:30, 2018, Math -101


Yuri Bilu (University of Bordeaux)


A singular modulus is the j-invariant of an elliptic curve with complex multiplication. André (1998) proved that a polynomial equation F(x,y)=0 can have only finitely many solutions in singular moduli (x,y), unless the polynomial F(x,y) is “special” in a certain precisely defined sense. Pila (2011) extended this to equations in many variables, proving the André-Oort conjecture on C^n. The arguments of André and Pila were non-effective (used Siegel-Brauer).

I will report on a recent work by Allombert, Faye, Kühne, Luca, Masser, Pizarro, Riffaut, Zannier and myself about partial effectivization of these results.

Other Dates