Combinatorics: Zuzana Patakova (HUJI), "Multilevel polynomial partitions"

Speaker: Zuzana Patakova, HU
Title: Multilevel polynomial partitions
The polynomial partitioning method of Guth and Katz partitions a given finite point set P in R^d using the zero set Z(f) of a suitable d-variate polynomial f.
Applications of this result are often complicated by the problem, what should be done with the points of P lying within Z(f)? A natural approach is to partition these points with another polynomial and continue further in a similar manner.
As a main result, we provide a polynomial partitioning method with up to d polynomials
in dimension d, which allows for a complete decomposition of the given point set.
The inductive proof is based on the following lemma:
Suppose we are given r > 1, a k-dimensional complex variety V in C^d whose all irreducible components have dimension k as well, and a finite set P of n real points contained in V. Under these assumptions we show that there exists a real polynomial f of degree at most O(r^{1/k}) that does not vanish on any of the irreducible components of V and moreover, every connected component of R^d \ Z(f) contains at most n/r points of P.
Joint work with Jirka Matoušek.


Mon, 16/11/2015 - 11:00 to 13:00


B221 Rothberg (CS and Engineering building)