We generalize the seminal polynomial partitioning theorems of Guth and Katz to a set of semi-Pfaffian sets. Specifically, given a set $\Gamma \subseteq \mathbb{ R}^n$ of $k$-dimensional semi-Pfaffian sets, where each $\gamma \in \Gamma$ is defined by a fixed number of Pfaffian functions, and each Pfaffian function is in turn defined with respect to a Pfaffian chain $\vec{ q}$ of length $r$, for any $D \ge 1$, we prove the existence of a polynomial $P \in \mathbb{ R}[X_1, \ldots, X_n]$ of degree at most $D$ such that each connected component of $\mathbb{ R}^n \setminus Z(P)$ intersects at most $\sim \frac{ |\Gamma|}{ D^{ n - k - r}}$ elements of $\Gamma$. Also, under some mild conditions on $\vec{ q}$, for any $D \ge 1$, we prove the existence of a Pfaffian function $P'$ of degree at most $D$ defined with respect to $\vec{ q}$, such that each connected component of $\mathbb{ R}^n \setminus Z(P')$ intersects at most $\sim \frac{ |\Gamma|}{ D^{ n-k}}$ elements of $\Gamma$. To do so, given a $k$-dimensional semi-Pfaffian set $\mathcal{ X} \subseteq \mathbb{ R}^n$, and a polynomial $P \in \mathbb{ R}[X_1, \ldots, X_n]$ of degree at most $D$, we establish a uniform bound on the number of connected components of $\mathbb{ R}^n \setminus Z(P)$ that $\mathcal{ X}$ intersects; that is, we prove that the number of connected components of $(\mathbb{ R}^n \setminus Z(P)) \cap \mathcal{ X}$ is at most $\sim D^{ k+r}$. Finally as applications, we derive Pfaffian versions of Szemer\'edi-Trotter type theorems, and also prove bounds on the number of joints between Pfaffian curves.
Categories: math.LO math.AG math.CO