Partitioning Theorems for Sets of Semi-Pfaffian Sets, with Applications
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909992290877440 |
|---|---|
| author | Lotz, Martin Natarajan, Abhiram Vorobjov, Nicolai |
| author_facet | Lotz, Martin Natarajan, Abhiram Vorobjov, Nicolai |
| contents | We generalize the seminal polynomial partitioning theorems of Guth and Katz to a set of semi-Pfaffian sets. Specifically, given a set $Γ\subseteq \mathbb{R}^n$ of $k$-dimensional semi-Pfaffian sets, where each $γ\in Γ$ 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{|Γ|}{D^{n - k - r}}$ elements of $Γ$. 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{|Γ|}{D^{n-k}}$ elements of $Γ$. 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édi-Trotter type theorems, and also prove bounds on the number of joints between Pfaffian curves. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02961 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Partitioning Theorems for Sets of Semi-Pfaffian Sets, with Applications Lotz, Martin Natarajan, Abhiram Vorobjov, Nicolai Logic Algebraic Geometry Combinatorics We generalize the seminal polynomial partitioning theorems of Guth and Katz to a set of semi-Pfaffian sets. Specifically, given a set $Γ\subseteq \mathbb{R}^n$ of $k$-dimensional semi-Pfaffian sets, where each $γ\in Γ$ 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{|Γ|}{D^{n - k - r}}$ elements of $Γ$. 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{|Γ|}{D^{n-k}}$ elements of $Γ$. 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édi-Trotter type theorems, and also prove bounds on the number of joints between Pfaffian curves. |
| title | Partitioning Theorems for Sets of Semi-Pfaffian Sets, with Applications |
| topic | Logic Algebraic Geometry Combinatorics |
| url | https://arxiv.org/abs/2412.02961 |