Speaker: Zuzana Patakova, HU

Title: Multilevel polynomial partitions

Abstract:

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.

Title: Multilevel polynomial partitions

Abstract:

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.

## Date:

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

## Location:

B221 Rothberg (CS and Engineering building)