Cutting lemma and Zarankiewicz's problem in distal structures
Artem Chernikov
David Galvin
Sergei Starchenko
DistalCuttingLemma.tex
% ----------------------------------------------------------------
% AMS-LaTeX Paper ************************************************
% **** -----------------------------------------------------------
\documentclass[12pt]{amsart}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{mathtools}
\usepackage{esvect}
\usepackage{tikz}
\usepackage[shortlabels]{enumitem}
\setlist{leftmargin=*}

\usepackage{amsfonts}
\usepackage{todonotes}
\gdef\dtodo#1{\todo[color=green!40]{#1}}
\gdef\stodo#1{\todo[color=blue!20!white]{\tiny #1}}
\gdef\stodoin#1{\todo[inline,color=blue!20!white]{ #1}}

\usepackage[colorlinks=true, linkcolor=blue]{hyperref}



\usepackage[sorted]{amsrefs}


\include{declar}
\include{localdef}
\title[Cutting lemma in distal structures]{Cutting lemma and Zarankiewicz's problem in distal structures}
 
\author{Artem Chernikov} \address{Department of Mathematics, 
University of California Los Angeles,
Los Angeles, CA 90095-1555} \email{chernikov@math.ucla.edu}

\author{David Galvin} \address{Department of Mathematics, University of Notre Dame, Notre Dame,
  IN 46556} \email{dgalvin1@nd.edu}

\author{Sergei Starchenko} \address{Department of Mathematics, University of Notre Dame, Notre Dame,
  IN 46556} \email{Starchenko.1@nd.edu}
  


\thanks{\hspace*{-1.6em} Chernikov was supported by the NSF Research Grant DMS-1600796 and by an Alfred P. Sloan Fellowship.\\ 
Galvin was supported by the Simons Foundation.\\
Starchenko was  supported by the NSF Research Grant DMS-1500671.\\
}




\begin{document}

{\abstract We establish a cutting lemma for definable families of sets in distal structures, as well as the optimality of the distal cell decomposition for definable families of sets on the plane in $o$-minimal expansions of fields. Using it, we generalize the results in \cite{zaran} on the semialgebraic planar Zarankiewicz problem to arbitrary $o$-minimal structures, in particular obtaining an $o$-minimal generalization of the Szemer\'edi-Trotter theorem.}

\maketitle


\section{Introduction}

The so called \emph{cutting lemma} is a very useful combinatorial partition tool with numerous applications in computational and incidence geometry and related areas (see e.g. \cite[Sections 4.5, 6.5]{mbook} or \cite{cuttings} for a survey). In it's simplest form it can be stated as follows (see e.g. \cite[Lemma 4.5.3]{mbook}).

\begin{fact}
For every set $L$ of $n$ lines in the real plane and every $1< r < n$ there exists a $\frac{1}{r}$-cutting for $L$ of size $O(r^2)$. That is, there is a subdivision	of the plane into generalized triangles (i.e. intersections of three half-planes)
 $\Delta_1, \ldots, \Delta_t$ so that the interior of each $\Delta_i$ is intersected by at most $\frac{n}{r}$ lines in $L$, and we have $t \leq C r^2$ for a certain constant $C$ independent of $n$ and $r$.\end{fact}

This result provides a method to analyze intersection patterns in families of lines, and it has many generalizations to higher dimensional sets and/or to families of sets of more complicated shape than lines, for example for families of algebraic or semialgebraic curves of bounded complexity \cite{chaz}. The proofs of these generalizations  typically combine some kind of geometric ``cell decomposition'' result with the so-called random sampling technique of Clarkson and Shor \cite{13}. 

The aim of this article is to establish a rather general version of the cutting lemma for definable (in the sense of first-order logic) families of sets in a certain model-theoretically tame class of structures (namely, for distal structures --- see Section \ref{sec: prelims and distality} for the definition), as well as to apply it to generalize some of the results in the area from the semialgebraic context  to arbitrary $o$-minimal structures. This work can be viewed as a continuation and refinement of the work started in \cite{distal}, where the connection of model-theoretic distality with a weak form of the cutting lemma was discovered (we don't assume familiarity with that paper, but recommend its introduction for an expanded discussion of the model theoretic preliminaries).  We believe that distal structures provide the most general natural setting for investigating questions in ``generalized incidence combinatorics''.

Let us describe the main results of the paper. Our first theorem establishes a cutting lemma for a definable family of sets in a distal structure, with the bound corresponding to the bound on the size of its distal cell decomposition. This is a generalized form of Matou\v{s}ek's axiomatic treatment of Clarkson's random sampling method discussed in \cite[Section 6.5]{mbook}.
The proof relies in particular on Lemma \ref{lem-set_system_corr} on correlations in set-systems to deal with the lack of the corresponding notion of ``being in a general position''.
\begin{thm*}(Theorem \ref{lem-r_cut}, Distal cutting lemma) Let $\varphi(x;y)$ be a formula admitting a distal cell decomposition $\CT$ (given by a finite set of formulas $\Psi(x; \bar{y})$ --- see Definition \ref{def: def cell decomp}) with 
$|\CT(S)| = O(|S|^d)$  (i.e. for some constant $C\in \RR$, for any \textbf{non-empty} 
finite $S\subseteq M^{|y|}$ we have $|\CT(S)| \leq C|S|^d$). 

Then for any finite $H \subseteq M^{|y|}$ of size $n$ and any real $r$ satisfying $1 < r < n$,  there are subsets $X_1, \ldots, X_t$ of $M^{|x|}$  covering $M^{|x|}$ with
$$
t \leq Cr^d
$$
for some constant $C = C(\varphi)$ (and independent of $H$, $r$ and $n$), and with each $X_i$ crossed by at most $n/r$ of the formulas $\{\varphi(x;a): a \in H\}.$ 

Moreover, each $X_i$ is the intersection of at most two sets $\Psi$-definable over $H$ (see Definition \ref{def: definable, crossing}).



\end{thm*}

While every formula in a distal structure admits a distal cell decomposition (see Fact \ref{fac: char of distality}), establishing optimal bounds in dimension higher than $1$ is non-trivial. In our second theorem, we demonstrate that formulas in $o$-minimal structures admit distal cell decompositions of optimal size ``on the plane''.

\begin{thm*}(Theorem \ref{thm:cell-dec})
Let $\CM$ be an $o$-minimal expansion of a real closed field. 
For any  formula $\varphi(x;y)$ with $|x|=2$ there is a distal cell decomposition $\CT$ with 
$|\CT(S)| = O(|S|^2)$.
\end{thm*}

In our proof, we show that a version of the vertical cell decomposition can be generalized to arbitrary $o$-minimal theories. This gives an optimal bound for subsets of $M^2$, but determining the exact bounds for distal cell decompositions in higher dimensions remains open, even in the semialgebraic case.

Finally, in Section \ref{sec: Zarank} we apply these two theorems to generalize the results in \cite{zaran} on the semialgebraic Zarankiewicz problem to arbitrary $o$-minimal structures, in the planar case (our result is more general and applies to arbitrary definable families admitting a quadratic distal cell decomposition, see Section \ref{sec: Zarank} for the precise statements).

\begin{thm*} (Theorem \ref{thm: everything o-min})
Let $\CM$ be an $o$-minimal expansion of a real closed field and let $E(x,y) \subseteq M^2 \times M^d$ be a definable relation. 

\begin{enumerate}
\item For every $k \in \mathbb{N}$ there is a constant $c = c(E,k)$ such that for any finite $P \subseteq M^2, Q \subseteq M^d$, $|P|=m, |Q| = n$, if $E \cap (P \times Q)$ does not contain a copy of $K_{k,k}$ (the complete bipartite graph with two parts of size $k$), then we have 
	$$ |E(P,Q)| \leq c \left( m^{\frac{d}{2d-1}} n^{\frac{2d-2}{2d-1}} + m + n \right).$$

	\item There is some $k' \in \mathbb{N}$ and formulas $\varphi(x,v), \psi(y,w)$ depending only on $E$ such that if $E$ contains a copy of $K_{k',k'}$, then there are some parameters $b \in M^v, c \in M^w$ such that both $\varphi(M,b)$ and $ \psi(M,c)$ are infinite and $\varphi(M,b) \times \psi(M,c) \subseteq E$.
\end{enumerate}
\end{thm*}

Combining the two parts, it follows that either $E$ contains a product of two infinite definable sets, or the upper bound on the number of edges in part (1) holds for all finite sets $P,Q$ with some fixed constant $c =c (E)$.

The special case with $d = 2 $ can be naturally viewed as a generalization of the classical Szemer\'edi-Trotter theorem for $o$-minimal structures.
\begin{cor}\label{cor: Sz-Trot}
	Let $\CM$ be an $o$-minimal expansion of a real closed field. Then for every definable relation $E(x,y) \subseteq M^2 \times M^2$ there is a constant $c$ and some formulas $\varphi(x,v), \psi(y,w)$ depending only on $E$ such that exactly one of the following occurs:

\begin{enumerate}
	\item For any finite $P \subseteq M^2, Q \subseteq M^2$, $|P|=m, |Q| = n$ we have $$ |E(P,Q)| \leq c \left( m^{\frac{2}{3}} n^{\frac{2}{3}} + m + n \right),$$
	\item there are some parameters $b \in M^v, c \in M^w$ such that both $\varphi(M,b)$ and $ \psi(M,c)$ are infinite and $\varphi(M,b) \times \psi(M,c) \subseteq E$.
\end{enumerate}

\begin{rem}
While this paper was in preparation, we have learned that Basu and Raz \cite{basu2016minimal} have obtained a special case of Corollary \ref{cor: Sz-Trot} using different methods.
\end{rem}


\end{cor}




\section{Preliminaries and the distal cell decomposition}\label{sec: prelims and distality}

Let $\CM$ be an arbitrary first-order structure in a language $\CL$. At this point we don't make any additional assumptions on $\CM$, e.g. we may work in ``set theory'',
i.e. in a structure where every subset is definable.  
We introduce some basic notation and terminology. Given a tuple of variables $x$, we let $|x|$ denote its length. For each $n \in \mathbb{N}$, $M^n$ denotes the corresponding cartesian power of $M$, the underlying set of $\CM$.
For a fixed formula $\varphi(x;y) \in \CL$ with two groups of variables $x$ and $y$, given $b \in M^{|y|}$ we write $\varphi(M;b)$ to denote the set $\{ a \in M^{|x|} : \CM \models \varphi(a;b)  \}$. Hence the formula $\varphi(x;y)$ can be naturally associated with the definable family of sets $\{ \varphi(M;b) : b \in M^{|y|}\}$. E.g., if $\CM$ is the field of reals, all sets in such a family for a fixed $\varphi(x;y)$ are semialgebraic of description complexity bounded by some $d = d(\varphi)$ and conversely, the  family of all semialgebraic sets of description complexity bounded by some fixed $d$ can be obtained in this way for an appropriate choice of the formula $\varphi(x;y)$. We refer to  \cite{distal} for a more detailed introduction and examples of the relevant model-theoretic terminology.

\begin{defn}
For sets $A,X \subseteq M^{d}$ 
we say that $A$ \emph{crosses} $X$ if both 
$X\cap A$ and $X\cap \neg A$ are nonempty.
\end{defn}


We extend the above definition to a set of formulas. 

\begin{defn}\label{def: definable, crossing} Let $\Phi(x;y)$ be a set of $\CL$-formulas of the form $\varphi(x;y) \in \CL$ and $S\subseteq
  M^{|y|}$.
 \begin{enumerate}
  \item We say that a subset $A\subseteq M^{|x|}$ is \emph{$\Phi(x;S)$-definable}
    if $A=\varphi(M;s)$ for some $\varphi(x;y)\in \Phi$ and $s\in S$. 
  \item For a set $X\subseteq M^{|x|}$ we say that \emph{$\Phi(x;S)$ 
    crosses $X$} if some $\Phi(x;S)$-definable set crosses $X$. In
  other words $\Phi(x;S)$ does not cross $X$ if for any $\varphi(x;y)
  \in \Phi(x;y)$ and $s\in S$ the formula  $\varphi(x;s)$ has a constant truth
  value on $X$. 
  \end{enumerate}
\end{defn}


We define a very general combinatorial notion of an abstract cell decomposition for formulas (equivalently, for definable families of sets).

\begin{defn}\label{def: cell decomp}Let $\Phi(x;y)$ be a finite set of formulas. 
  \begin{enumerate}
  \item Given a finite set $S \subseteq M^{|y|}$, a family $\CF$ of subsets of $M^{|x|}$ is
    called \emph{ an abstract  cell decomposition for $\Phi(x;S)$} if $M^{|x|}=\cup
      \CF$  and every $\Delta\in \CF$ is not crossed by $\Phi(x;S)$. 
    \item  \emph{An abstract cell decomposition for  $\Phi(x;y)$} is  an assignment $\CT$ that to each finite
set $S\subseteq M^{|y|}$ assigns an abstract  cell decomposition  $\CT(S)$ for $\Phi(x;S)$.
  \end{enumerate}
\end{defn}

\begin{rem}
  In the above definition, the term ``cell decomposition'' is understood in a very weak sense. Firstly, the ``cells'' in $\CT(S)$ are not required to have any ``geometric'' properties, and  secondly, we don't require the family
  $\CT(S)$ to partition $M^{|x|}$, but only ask for it to be a covering.
 \end{rem}

Every $\Phi(x;y)$ admits an obvious abstract cell decomposition, with $\CT(S)$ consisting of the atoms in the Boolean algebra generated by the $\Phi(x;S)$-definable sets. In general, defining these cells would require longer and longer formulas when $S$ grows, and the aim of the following definitions is to avoid this possibility.

\begin{defn}
Let $\Phi(x;y)$ be a finite set of formulas and $\CT$ an abstract  cell
decomposition for $\Phi(x;y)$. We say that $\CT$ is \emph{weakly
  definable} if there is a finite set of formulas
$\Psi(x; \bar y)=\Psi(x;y_1,\dotsc,y_k)$ with
$|y_1|=\ddotsb=|y_k|=|y|$ such that for any finite $S\subseteq M^{|y|}$, 
every $\Delta\in \CT(S)$ is  $\Psi(x;\bar y)$-definable over $S$ (i.e., $\Delta=\psi(M; s_1,\dotsc,s_k)$ for some $s_1,\dotsc,s_k \in S$ and $\psi\in \Psi$).
\end{defn}


Notice that if an abstract  cell decomposition $\CT$ for $\Phi(x;y)$ is weakly
defined by $\Psi(x;\bar y)$  then $\Psi(x;\bar y)$ does not determine
$\CT$ uniquely; however there is a maximal abstract cell decomposition
$\CT^{\textrm{max}}$  weakly defined by  $\Psi(x;\bar y)$, where 
 $\CT^{\textrm{max}}(S)$ consists of \emph{all} $\Psi(x;\bar y)$-definable over $S$ sets $\Delta$ 
such that $\Phi(x;S)$ does not cross $\Delta$. 

For combinatorial applications discussed in this paper, we would like  to have a cell decomposition with as few sets as
possible, and  we want to have control over the sets appearing in
$\CT(S)$ in a definable way. 




\begin{defn}\label{def: def cell decomp} Let $\Phi(x;y)$ be a finite set of formulas. 
An abstract  cell decomposition $\CT$  
for $\Phi$ is \emph{definable} 
if for every finite $S\subseteq M^{|y|}$  there is a family $\Psi(S)$ of subsets of
$M^{|x|}$, uniformly definable in $S$, and for each $\Delta\in \Psi(S)$ a
subset $\CI(\Delta)\subseteq M^{|y|}$, uniformly definable in $\Delta$, 
such that 
\begin{equation}
  \label{eq:1}
\CT(S)=\{ \Delta\in \Psi(S) \colon \CI(\Delta)\cap S 
=\emptyset\}. 
 \end{equation}
By the uniform definability of $\Psi(S)$ we  mean the existence of 
a finite set of formulas
$\Psi(x; \bar y)$ as above, so that 
for any finite $S\subseteq M^{|y|}$  the set 
$\Psi(S)$ consists of all $\Psi(x; \bar y)$-definable over $S$ sets;
and  uniform definability of  $\CI(\Delta)$ means that  for every
$\psi(x;\bar y )\in \Psi(x;\bar y)$ there is a formula
$\theta_\psi(y;\bar y)$ such that for any $s_1,\dotsc,s_k\in
M^{|y|}$ if $\Delta=\psi(M;s_1,\dotsc,s_k)$ then 
$\CI(\Delta)=\theta_\psi(M;s_1,\dotsc,s_k)$. 
\end{defn}

For example, $\CT^{\textrm{max}}$ defined above is definable with $\CI(\Delta)=\{ s\in M^{|y|} \colon   
 \Phi(x;s) \text{ crosses }\Delta \}$.

\begin{rem}\label{rem: I Delta contains crossing params}
It follows from Definition \ref{def: def cell decomp} that for every $\Psi(x;M)$-definable set $\Delta \subseteq M^{|x|}$, the set of all $s \in M^{|y|}$ such that $\Phi(x;s)$ crosses $\Delta$ is contained in $\CI(\Delta)$ (strict containment is possible, however).

Indeed, assume that $s \in M^{|y|}$ and $\varphi(x;y) \in \Phi$ are such that $\varphi(x;s)$ crosses $\Delta$. By Definition \ref{def: cell decomp}(1), necessarily $\Delta \notin \CT(\{ s \})$. But then $\CI(\Delta) \cap \{s \} \neq \emptyset$ by  (\ref{eq:1}), hence $s \in \CI(\Delta)$.
\end{rem}

\begin{rm}


\end{rm}




As was realized in \cite{distal}, such combinatorial definable cell decompositions have a close connection to the model-theoretic notion of distality. Distal structures were introduced in \cite{DistalPierre} for purely model theoretic purposes (we don't give the original definition here). The following was pointed out in \cite{distal} (and can be used as the definition of a distal structure in this paper). 
\begin{fact} \label{fac: char of distality} The following are equivalent for a first-order structure $\CM$.
\begin{enumerate}
	\item $\CM$ is distal,
	\item for every formula $\varphi(x;y)$ there is a weakly definable cell
  decomposition for $\{ \varphi(x;y) \}$,
  \item for every formula $\varphi(x;y)$ there is a definable cell decomposition for $\{ \varphi(x;y) \}$.
	\end{enumerate}
\end{fact}

 
  Equivalence of the original definition of distality and existence of weakly definable cell
  decompositions is given by \cite[Theorem 21]{chernikov2015externally}; and if $\CT$ is a weakly definable cell decomposition for $\varphi(x;y)$, then $\CT^{\textrm{max}}$ as defined above is definable.
 
 Examples of distal structures include (again, we refer to the introduction of \cite{distal} for a more detailed discussion): 
 \begin{enumerate}
 	\item $o$-minimal structures,
 	\item Presburger arithmetic $(\mathbb{Z}, +, 0, <)$,
 	\item the field of $p$-adics $\mathbb{Q}_p$.
 \end{enumerate}
  
There are several contexts in model theory relevant for the topics of this paper where certain notions of cell decomposition play a prominent role (e.g. $o$-minimal cell decomposition, $p$-adic cell decomposition, etc.). These cell decompositions tend to carry more geometric information, while the one distinguished here captures combinatorial complexity. To distinguish from those cases, and in view of Fact \ref{fac: char of distality}, we will from now on refer to a definable cell decomposition $\CT$ for a finite set of formulas $\Phi(x;y)$ as in Definition \ref{def: def cell decomp} as a \emph{distal cell decomposition} for $\Phi(x;y)$. Hence, \textbf{a structure $\CM$ is distal if and only if every formula admits a distal cell decomposition}.
  
   Distality of the examples listed above had been established by different (sometimes infinitary) methods and the question of obtaining the exact bounds on the size of the corresponding distal cell decompositions hasn't been considered. While it is easy to verify in the examples listed above that all formulas $\varphi(x,y)$ with $|x|=1$ admit a cell decomposition $\CT$ with the best possible bound $|\CT(S)| = O(|S|)$, already the case of formulas with $|x|=2$ becomes more challenging (and grows in complexity with $|x|$). In Section \ref{sec: omin-cell-decomp} we establish that in an $o$-minimal expansion of a field, all formulas with $|x|=2$ admit a distal cell decomposition $\CT$ with the optimal bound $|\CT(S)| = O(|S|^2)$ (the case $|x|\geq 3$ remains open, even in the semialgebraic case).   
   
%    (and there are good reasons to believe that it is difficult). We make a definition capturing the best possible scenario. \stodo{As I wrote in e-mail this pat should be rewritten} 
%   \begin{defn}
%Given a finite set of formulas $\Phi(x;y)$, we will say that $\Phi(x;y)$ admits an \emph{optimal distal cell decomposition} if there is a distal cell decomposition $\CT$ for $\Phi(x;y)$ and some fixed constant $C = C(\Phi)$ such that $|\CT(S)| \leq C |S|^{|x|}$ for all finite $S \subseteq M^{|y|}$.
%\end{defn}
%  
%  While it is easy to verify for most of the examples above that all formulas $\varphi(x,y)$ with $|x|=1$ admit an optimal distal cell decomposition, already the case of formulas with $|x|=2$ becomes more challenging (and grows in complexity with $|x|$, see the end of Section \ref{sec: omin-cell-decomp} for a discussion). 






\section{Distal cutting lemma}
In this section we show how a bound on the size of a distal cell decomposition for a given definable family can be used to obtain a definable cutting lemma with the corresponding bound 
on its size.

\begin{thm} \label{lem-r_cut}
(Distal cutting lemma) Let $\varphi(x;y)$ be a formula admitting a distal cell decomposition $\CT$ (given by a finite set of formulas $\Psi(x; y_1, \ldots, y_s)$ --- see Definition \ref{def: def cell decomp}) with 
$|\CT(S)| = O(|S|^d)$. 

Then for any finite $H \subseteq M^{|y|}$ of size $n$ and any real $r$ satisfying $1 < r < n$,  there are subsets $X_1, \ldots, X_t$ of $M^{|x|}$ covering $M^{|x|}$ with
$$
t \leq Cr^d
$$
for some constant $C = C(\varphi)$ (and independent of $H$, $r$ and $n$), and with each $X_i$ crossed by at most $n/r$ of the formulas $\{\varphi(x;a): a \in H\}.$ 

Moreover, each of the $X_i$'s is an intersection of at most two $\Psi(x;H)$-definable sets.



\end{thm}
Our proof generalizes (and closely follows) the axiomatic treatment of the Clarkson-Shor random sampling technique in \cite[Section 6.5]{mbook}. 

Let $\CT, \Psi$ and $H$ as in the assumption be fixed.
Then (recalling Definition \ref{def: def cell decomp}) for each finite $S \subseteq M^{|y|}$, we have a finite collection ${\mathcal T}(S)$ of subsets of $M^{|x|}$ that covers $M^{|x|}$ and satisfies the following conditions.

\begin{enumerate}
	\item[\textbf{(C1)}] Let 
$$
{\rm Reg} := \{\Delta : \Delta \in {\mathcal T}(S)~\mbox{for some $S \subseteq H$}\}.
$$  
Then every set in {\rm Reg} is definable by an instance of a formula from $\Psi$ with parameters in $H$.
	\item[\textbf{(C2)}] For every $S \subseteq H$ we have
$$
|{\mathcal T}(S)| \leq C'\left(|S|^d+1\right)
$$
for some constant $C'$ depending only on $\varphi$. (The hypothesis of the theorem ensures that for {\emph non-empty} $S$ we have $|{\mathcal T}(S)| \leq C|S|^d$ for some constant $C=C(\varphi)$. We add ``$+1$'' here to take into account the case $S = \emptyset$.)


%(We add ``$+1$'' here to take into account the case $S = \emptyset$.)

%\dtodo{I think it is ok as-is. The hypothesis of the thm is that there some absolute $C'$ such that for all non-empty $S$, $|{\mathcal T}(S)| \leq C'|S|^d$. When $S$ is empty, rhs becomes $0$, but we want it to be $1$ to get a true bound (since there is a good decomposition with just one cell, in this case). So it seems to me that $C'|S|^d+1$ is fine here.}

\item[\textbf{(C3)}] To each $\Delta \in {\rm Reg}$ we associate a collection ${\mathcal D}(\Delta)$ of subsets of $H$, called the {\em defining sets} of $\Delta$, via 
$$
{\mathcal D}(\Delta) := \{S \subseteq H: |S| \leq s,~\Delta \in {\mathcal T}(S)\}.
$$ 
(Here $s$ is a fixed constant corresponding to the number of parameters in $\Psi(x;y_1, \ldots, y_s)$ given by the distal cell decomposition and depending only on $\varphi$). 
Given $\CI$ as in Definition \ref{def: def cell decomp}, we define $\CI_H(\Delta) := \CI(\Delta) \cap H$.  Notice that $\CI_H(\Delta)$ contains all of the $a \in H$ such that $\varphi(x;a)$ crosses $\Delta$ (by Remark \ref{rem: I Delta contains crossing params}). We have:
$$
\Delta \in {\mathcal T}(S) \iff {\mathcal I}_H(\Delta) \cap S = \emptyset~\mbox{and there is}~S_0 \in {\mathcal D}(\Delta)~\mbox{with}~S_0 \subseteq S.
$$


%\item[\textbf{(C4)}] For any $\Delta \in {\rm Reg}$ and $S_0 \in {\mathcal D}(\Delta)$ we have $|S_0| \leq s$ (immediate), and any $S_0 \subseteq H$ is in $\CD(\Delta)$ for no more than a constant number of $\Delta \in {\rm Reg}$ (an upper bound on this constant is given by the maximum of $|{\mathcal T}(S')|$ over all $S' \subseteq H$ with $|S'| \leq s$; note that this maximum is uniformly bounded in $n$ by \textbf{(C2)}). \stodo{ I don't think we use this condition anywhere. So we can remove it}
\end{enumerate}

\begin{rem} It  follows from the proof that the distal cutting lemma (Theorem \ref{lem-r_cut}) holds for any abstract cell decomposition satisfying the conditions (C1)--(C3) with an appropriately chosen relation $\CI(\Delta)$. 
\end{rem}

\medskip

Before proceeding to the proof of the distal cutting lemma (Theorem \ref{lem-r_cut}) we isolate two key tools. The first is a tail bound on the probability that a cell $\Delta \in {\mathcal T}(S)$ is crossed by many formulas, where $S$ is a randomly chosen subset of $H$.

For $S \subseteq H$, let ${\mathcal T}(S)_{\geq t}$ denote the set of $\Delta \in {\mathcal T}(S)$ with $|{\mathcal I}_H(\Delta)| \geq tn/r$. Recall that for $0 \leq p \leq 1$ we say that $S \subseteq H$ is selected by {\em independent Bernoulli trials with success probability $p$} if $S$ is selected according to the distribution $\mu$ (supported on the power set of $H$) given by 
$$
\mu(S') = p^{|S'|}(1-p)^{|H|-|S'|}
$$
for each $S' \subseteq H$; observe that this is essentially the process of flipping a biased coin (biased to show heads with probability $p$) $|H|$ times independently, and for $1 \leq i \leq |H|$ putting the $i$th element of $H$ in $S$ if and only if the $i$th flip comes up heads. 

\begin{lem} \label{lem-tail}
(Tail Bound Lemma) Let $\varphi(x;y)$ be a formula as in Theorem \ref{lem-r_cut}. Let $H \subseteq M^{|y|}$ be a finite set of size $n$. Fix $\varepsilon > 0$ and let $r$ be a parameter satisfying $1 \leq r \leq (1-\varepsilon)n$. Let $S \subseteq H$ be selected by independent Bernoulli trials with success probability $r/n$, and let $t \geq 0$ be given. Then there is a constant $C=C(\varepsilon)$ such that
$$
{\bf E}_{\mu}\left(\left|{\mathcal T}(S)_{\geq t}\right|\right) \leq C2^{-t}r^d.
$$
\end{lem} 

We use this to derive the second main tool, a cutting lemma that is weaker than Theorem \ref{lem-r_cut}.
\begin{lem} \label{lem-subopt_cut}
(Suboptimal Cutting Lemma) Let $\varphi(x;y)$ be a formula as in Theorem \ref{lem-r_cut}. Let $H \subseteq M^{|y|}$ be a finite set of size $n$. Let $r$ be a parameter satisfying $1 < r < n$. There is $S \subseteq H$ with
$$
|{\mathcal T}(S)| \leq Kr^d\log^d (r+1)
$$
for some constant $K$ independent of $H$, $r$ and $n$ and with each $X \in {\mathcal T}(S)$ crossed by at most $n/r$ of the formulas $\{\varphi(x;a): a \in H\}.$  
\end{lem}

\medskip

\begin{proof}
%We begin by observing that ${\mathcal T}(H)$ furnishes an $r$-cutting for all $r$, with size at most $C'n^d +1$ (this uses Conditions 2 and 3). This allows us to assume, say, $n \geq 10$; we need only adjust the constant $K$ at the end of the argument to deal with smaller $n$. \textcolor{blue}{necessary?}

Let $A$ be such that $3\times 2^{2d}CA^d = 2^A$, where $C$ is the constant appearing in Lemma \ref{lem-tail}. We treat separately the cases $2Ar \log(r+1) \leq n$ and $2Ar \log(r+1) \geq n$. If $2Ar \log(r+1) \geq n$ then we may take ${\mathcal T}(H)$ as our $r$-cutting, since it has size  $C'(n^d +1) \leq C'((2A)^dr^d \log^d(r+1) + 1) \leq Kr^d\log^d (r+1)$ for suitably large $K$ (note that by \textbf{(C3)} no instance of $\varphi(x;y)$ over $H$ can cross any of the sets in ${\mathcal T}(H)$). 


Suppose now that $2Ar \log(r+1) \leq n$. Set $r' = Ar\log (r+1)$. Applying Lemma \ref{lem-tail} with $r'$ taking the role of $r$ (valid since $r' < n/2$) and with $t=0$ we obtain that if $S \subseteq H$ is selected by independent Bernoulli trials with success probability $r'/n$ (with associated distribution $\mu'$) then
$$
{\bf E}_{\mu'}\left(\left|{\mathcal T}(S)\right|\right) \leq CA^dr^d \log^d(r+1).
$$
Applying Lemma \ref{lem-tail} again with $t=A \log(r+1)$ we get
$$
{\bf E}_{\mu'}\left(\left|{\mathcal T}(S)_{\geq A \log(r+1)}\right|\right) \leq \frac{CA^d r^d \log^d(r+1)}{(r+1)^A} \leq \frac{CA^d}{(r+1)^{A-2d}} \leq 1/3,
$$
the second inequality using $r\log(r+1) \leq (r+1)^2$ and the third using our choice of $A$ and the fact that $r \geq 1$.  By linearity of expectation
$$
{\bf E}_{\mu'}\left(\frac{\left|{\mathcal T}(S)\right|}{3CA^dr^d \log^d(r+1)} + \left|{\mathcal T}(S)_{\geq A \log(r+1)}\right| \right) \leq 2/3,
$$
so there exists an $S \subseteq H$ such that 
$$
\left|{\mathcal T}(S)\right| \leq 3CA^dr^d \log^d(r+1)
$$
and ${\mathcal T}(S)_{\geq A \log(r+1)} = \emptyset$. This last condition implies that each $\Delta \in {\mathcal T}(S)$ is crossed by at most
$(A \log(r+1) n)/r' = n/r$
formulas. 

%We now consider $2Ar \log(r+1) \geq n$, for which we do not require Lemma \ref{lem-tail}. Note that there is a constant $c<1$ (depending on $A$) such that $r \geq n^c$ for all $n \geq 10$.
%
%\textcolor{blue}{We assume that there is some constant $c'$ such that $|{\rm Reg}| \leq n^{c'}$}. Set $m=(c'+1)r \ln n$, and let $(\varphi_1, \ldots, \varphi_m)$ be obtained by selecting $m$ formulae from $H$ uniformly and independently (with replacement). Set $S=\{\varphi_1, \ldots, \varphi_m\}$ (so $|S|\leq m$ and $|{\mathcal T}(S)| \leq C'm^d + 1$). For each $\Delta \in {\rm Reg}$ that is crossed by at least $n/r$ of the formulae in $H$ (i.e., with $|{\mathcal I}(\Delta)| \geq n/r$) we have that the probability that no formula in $S$ crosses $\Delta$ is at most
%$$
%\left(1-\frac{n/r}{n}\right)^m \leq e^{-m/r} =  n^{-(c'+1)},
%$$
%the inequality using $1+x \leq e^x$, valid for all real $x$. Using our bound on $|{\rm Reg}|$ is follows that the probability that there is at least one $\Delta \in {\rm Reg}$ with $|{\mathcal I}(\Delta)| \geq n/r$ with no formula of $S$ crossing $\Delta$ is at most $1/n$. It follows that with positive probability, every $\Delta \in {\rm Reg}$ with $|{\mathcal I}(\Delta)| \geq n/r$ is crossed by some formula in $S$. This implies (by Condition 3) that no $\Delta \in {\mathcal T}(S)$ is crossed by more than $n/r$ formula from $H$, and so ${\mathcal T}(S)$ forms an $r$-cutting. Combining $|{\mathcal T}(S)| \leq C'm^d + 1 = C'(c'+1)^d r^d \ln^d n + 1$ with $r \geq n^c$ yields $|{\mathcal T}(S)| \leq O(r^d \log r^d)$, as required.
\end{proof}


\medskip

We use Lemmas \ref{lem-subopt_cut} and \ref{lem-tail} to derive Theorem \ref{lem-r_cut}, before turning to the proof of Lemma \ref{lem-tail}.

\medskip

\begin{proof}[Proof of Theorem \ref{lem-r_cut}]
Just as in the proof of Lemma \ref{lem-subopt_cut} we begin by observing that ${\mathcal T}(H)$ furnishes an $r$-cutting for all $r$, with size at most $C'(n^d +1)$. This allows us to assume, say, $r \leq n/2$, which allows us to use Lemma \ref{lem-tail}.


Let $S \subseteq H$ be selected by independent Bernoulli trials with success probability $r/n$, and let ${\mathcal T}(S)$ be as in the assumption.

For $\Delta \in {\mathcal T}(S)$ define $t_\Delta$ by $|{\mathcal I}_H(\Delta)| = t_\Delta n/r$. Note that if $t_\Delta \leq 1$ then the number of $a$ in $H$ such that $\varphi(x,a)$ crosses $\Delta$ is no more than $n/r$.

For $\Delta \in {\mathcal T}(S)$ with $t_\Delta > 1$, consider the set ${\mathcal I}_H(\Delta)$, it contains all of $a \in H$ for which $\varphi(x,a)$ crosses $\Delta$.  By Lemma \ref{lem-subopt_cut} there is $S' \subseteq {\mathcal I}_H(\Delta)$ with ${\mathcal T}(S')$ having size at most $O(t^d_\Delta \log (t^d_\Delta+1))$ with the property that for every $\Delta' \in {\mathcal T}(S')$, the number of $a \in {\mathcal I}_H(\Delta)$ such that $\varphi(x,a)$ crosses $\Delta'$ is at most
$$
\frac{|{\mathcal I}(\Delta)|}{t_\Delta} = \frac{n}{r}.
$$       
In particular that means that for every $\Delta' \in {\mathcal T}(S')$ the number of $a \in H$ such that $\varphi(x,a)$ crosses $\Delta' \cap \Delta$ is at most $n/r$.

It follows that the family of subsets of $M^{|x|}$ consisting of those $\Delta \in {\mathcal T}(S)$ for which $t_\Delta \leq 1$, together with all sets of the form $\Delta' \cap \Delta$ where $\Delta \in {\mathcal T}(S)$ has $t_\Delta > 1$ and $\Delta' \in {\mathcal T}(S')$ (with $S'$ constructed from $S$ via Lemma \ref{lem-subopt_cut}, as described above), forms a cover of $M^{|x|}$ with size at most
\begin{equation} \label{eq-decomp_bound}
\sum_{\Delta \in {\mathcal T}(S)} \left({\bf 1}_{\{t_\Delta \leq 1\}} + Ct_\Delta^d\log^d(t_\Delta+1) {\bf 1}_{\{t_\Delta > 1\}}\right).
\end{equation}
We now upper bound the expectation (with respect to $\mu$) of this quantity. By linearity the expectation is at most
\begin{equation} \label{eq-size}
{\bf E}_{\mu}\left(\left|{\mathcal T}(S)\right|\right) + C\sum_{i \geq 0} {\bf E}_{\mu}\left(\sum_{\Delta \in {\mathcal T}(S) \colon 2^i \leq t_\Delta < 2^{i+1}} t_\Delta^{2d}\right)
\end{equation}
(using $\log (t_\Delta+1) \leq t_\Delta$ for $t_\Delta \geq 1$). 

We bound the first term in (\ref{eq-size}) by an application of Lemma \ref{lem-tail} with $t=0$. This gives
$$
{\bf E}_{\mu}\left(\left|{\mathcal T}(S)\right|\right) \leq O(r^d).
$$
For the second term in (\ref{eq-size}) we have
\begin{multline*}
\sum_{i \geq 0} {\bf E}_\mu \left(\sum_{\Delta \in {\mathcal T}(S) \colon 2^i \leq t_\Delta < 2^{i+1}} t_\Delta^{2d}\right) \leq  \sum_{i \geq 0} 2^{2d(i+1)} {\bf E}_{\mu}\left(\left|{\mathcal T}(S)_{\geq 2^i}\right|\right) \\
 \leq  C\sum_{i \geq 0} 2^{2d(i+1)} 2^{-2^i} r^d = O(r^d),
\end{multline*}
with the last inequality being an application of Lemma \ref{lem-tail}. 

We conclude that the expectation of the quantity in (\ref{eq-decomp_bound}) is $O(r^d)$, so there is at least one choice of $S \subseteq H$ for which (\ref{eq-decomp_bound}) is at most $O(r^d)$, proving Theorem \ref{lem-r_cut} (the definability clause follows by \textbf{(C1)} as every set in the constructed covering is an intersection of at most two sets from ${\rm Reg}$).  
\end{proof}

\medskip

Before proving Lemma \ref{lem-tail} we isolate a useful set-systems lemma.
\begin{lem} \label{lem-set_system_corr}
Let $\Omega$ be a set of size $m$, and let $\{D_1, \ldots, D_q\}$ be a collection of subsets of $\Omega$ with $|D_i| \leq u$ for all $i$, $1 \leq i \leq q$, for some $u$. Let
$$
{\mathcal F} = \{X \subseteq \Omega:D_i \subseteq X~\mbox{for some $i$, $1 \leq i \leq q$}\}
$$
be the up-set (or filter) generated by the $D_i$'s. Let $\tilde{p}$ and $p$ satisfy $0 < \tilde{p} \leq p \leq 1$. We have
\begin{equation} \label{eq-correlation_inq}
\frac{\sum_{X \in {\mathcal F}} \tilde{p}^{|X|}(1-\tilde{p})^{m-|X|}}{\sum_{X \in {\mathcal F}} p^{|X|}(1-p)^{m-|X|}} \geq \left(\frac{\tilde{p}}{p}\right)^u.
\end{equation}
\end{lem}

\begin{proof}
With each $X \in {\mathcal F}$ associate (arbitrarily) a set $D_X$ satisfying $D_X \subseteq X$ and $D_X \in \{D_1, \ldots, D_q\}$ (such a set exists by the definition of ${\mathcal F}$).

Let $A \subseteq \Omega$ be selected by independent Bernoulli trials with success probability $p$, and, independently, let $B \subseteq \Omega$ be selected by independent Bernoulli trials with success probability $\tilde{p}/p$. Observe that
\begin{equation} \label{eq-first_random_selection}
\Pr(A \in {\mathcal F}) = \sum_{X \in {\mathcal F}} p^{|X|}(1-p)^{m-|X|}
\end{equation} 
and
\begin{equation} \label{eq-combination_random_selection}
\Pr(A \cap B \in {\mathcal F}) = \sum_{X \in {\mathcal F}} \tilde{p}^{|X|}(1-\tilde{p})^{m-|X|},
\end{equation}
with (\ref{eq-combination_random_selection}) holding by independence and because for each $\omega \in \Omega$, $\Pr(\omega \in A \cap B)=\Pr(\omega \in A)\Pr(\omega \in B)$. 
  
Now consider the two events
$$
E_1 = \{A \in {\mathcal F}~\mbox{and}~D_A \subseteq B\}
$$  
and
$$
E_2 = \{A \cap B \in {\mathcal F}\}.
$$
If $A \in {\mathcal F}$ and $D_A \subseteq B$ then $D_A \subseteq A \cap B$, so that $A \cap B \in {\mathcal F}$. It follows that $E_1 \subseteq E_2$ and 
\begin{equation} \label{eq-containment}
\Pr(E_1) \leq \Pr(E_2).
\end{equation}
Using independence we have
\begin{multline*}
\Pr(E_1) = \sum_{X \in {\mathcal F}} \Pr(A=X~\mbox{and}~D_X \subseteq B) = \sum_{X \in {\mathcal F}} \Pr(A=X)\left(\frac{\tilde{p}}{p}\right)^{|D(X)|}  \\
 \geq \Pr(A \in {\mathcal F})\left(\frac{\tilde{p}}{p}\right)^u.
\end{multline*}
Combining with (\ref{eq-first_random_selection}), (\ref{eq-combination_random_selection}) and (\ref{eq-containment}) we get (\ref{eq-correlation_inq}).
\end{proof}

We are now ready to prove Lemma \ref{lem-tail}. We follow Matou\v{s}ek's approach in \cite[Section 6.5]{mbook}, but add an additional argument. 
\begin{proof}[Proof of Lemma \ref{lem-tail}] 
We start by establishing
\begin{equation} \label{claim1}
{\bf E}_\mu\left(\left|{\mathcal T}(S)\right|\right) = O(r^d),
\end{equation}
which gives Lemma \ref{lem-tail} for $t \leq 1$.
To see (\ref{claim1}) note that \textbf{(C2)} yields ${\bf E}_\mu\left(\left|{\mathcal T}(S)\right|\right) \leq C{\bf E}_\mu\left(|S|^d\right)+1$. Now $|S|=X_1+\ldots + X_n$ where the $X_i's$ are independent Bernoulli random variables each with parameter $p=r/n$. We claim that for all $d \geq 1$ we have
\begin{equation} \label{eq-bin-moment-bound}
{\bf E}_\mu(|S|^d) \leq (r+d)^d.
\end{equation}
(from which (\ref{claim1}) immediately follows; note that we can drop the $+1$ since $r \geq 1$).

To see (\ref{eq-bin-moment-bound}), note first that by linearity we have 
$$
{\bf E}_\mu(|S|^d) = \sum_{(i_1,i_2,\ldots,i_d) \in \{1, \ldots, n\}^d} {\bf E}(X_{i_1}X_{i_2}\cdots X_{i_d}).
$$
Let $a_k$ be the number of tuples $(i_1,i_2,\ldots,i_d) \in \{1, \ldots, n\}^d$ such that $|\{i_1,i_2,\ldots,i_d\}|=d-k$. By independence of the $X_i$, and the fact that $X_i^\ell$ has the same distribution as $X_i$ for any integer $\ell \geq 1$ we have
\begin{equation} \label{eq-bin-moment-bound_int}
{\bf E}_\mu(|S|^d) = \sum_{k=0}^d a_k p^{d-k}.
\end{equation}
We claim that 
\begin{equation} \label{eq-bin-moment-bound_int2}
a_k \leq \binom{d}{k}d^kn^{d-k}.
\end{equation}
Inserting into (\ref{eq-bin-moment-bound_int}) and using the binomial theorem together with $np=r$, this gives (\ref{eq-bin-moment-bound}).

To see (\ref{eq-bin-moment-bound_int2}) note that we overcount $a_k$ by first specifying $d-k$ indices from $\{1,\ldots,d\}$ on which the $i_j$'s are all different from each other ($\binom{d}{d-k}=\binom{d}{k}$ choices), then choosing values for these $i_j$'s ($n(n-1)\cdots(n-(d-k)+1) \leq n^{d-k}$ choices), and finally choosing values for the remaining indices ($(d-k)^k \leq d^k$ choices, since these indices are all constrained to lie among the $d-k$ distinct indices chosen initially). It follows that $a_k \leq \binom{d}{k} n^{d-k} d^k$, as claimed.

(We note that in the case $d=2$ things are considerably easier: we have
$$
|S|^2 = \sum_{i=1}^n X_i^2 + 2\sum_{1 \leq i < j \leq n} X_iX_j
$$
so
\begin{align*}
{\bf E}_\mu(|S|^2) & =  \sum_{i=1}^n {\bf E}(X_i^2) + 2\sum_{1 \leq i < j \leq n} {\bf E}(X_iX_j) \\
& =  np + n(n-1)p^2 \\
& \leq  np + n^2p^2 = r^2+r.)
\end{align*}


We assume from now on that $t\geq 1$. For $\Delta\in {\rm Reg}$ denote by $p(\Delta)$ the probability that
$\Delta$ appears in ${\mathcal T}(S)$,  i.e.
$$
p(\Delta)=  \mu(\{ S\subseteq H \colon \Delta\in {\mathcal T}(S)\})=\sum_{\Delta\in {\mathcal T}(S)} \mu(S).
$$
Let ${\rm Reg}_{\geq t}=\{ \Delta\in  {\rm Reg} \colon |{\mathcal I}_H(\Delta)|\geq tn/r\}$. By linearity of expectation we have
\begin{equation} \label{eq:2}
{\bf E}_\mu\left(\left|{\mathcal T}(S)_{\geq t}\right|\right)= \sum_{\Delta\in {\rm Reg}_{\geq t}} p(\Delta).
\end{equation}

Now set $\tilde{p}=p/t$ and let $\tilde{\mu}$ be the distribution associated with selection from $H$ by independent Bernoulli trials with success probability $\tilde{p}$. By (\ref{claim1}) we have 
\begin{equation} \label{eq:3}
{\bf E}_{\tilde{\mu}}\left(\left|{\mathcal T}(S)\right|\right)=O(r^d/t^d).
\end{equation}
Also, as in \eqref{eq:2} we have   
\begin{multline}\label{eq:4}
{\bf E}_{\tilde{\mu}}\left(\left|{\mathcal T}(S)\right|\right)  =  \sum_{\Delta\in {\rm Reg}}
\tilde{p}(\Delta) 
 \geq  \sum_{\Delta\in {\rm Reg}_{\geq t}} \tilde{p}(\Delta) \\
 =  \sum_{\Delta\in {\rm Reg}_{\geq t}} p(\Delta)\frac{\tilde{p}(\Delta)}{p(\Delta)}  
 \geq   \min\left\{ \frac{\tilde{p}(\Delta)}{p(\Delta)}\colon \Delta\in
      {\rm Reg}_{\geq t}\right\} \sum_{\Delta\in {\rm Reg}_{\geq t}} p(\Delta)  \\
 =  \min\left\{ \frac{\tilde{p}(\Delta)}{p(\Delta)}\colon \Delta\in
      {\rm Reg}_{\geq t}\right\} {\bf E}_\mu\left(\left|{\mathcal T}(S)_{\geq t}\right|\right). 
\end{multline}
  
We now estimate from below the quantity $\tilde{p}(\Delta)/p(\Delta)$ for $\Delta \in {\rm Reg}_{\geq t}$. Fix such a $\Delta$ and let ${\mathcal F}(\Delta)$ be the up-set on ground set $H \setminus {\mathcal I}_H(\Delta)$ generated by ${\mathcal D}(\Delta)$.
Using \textbf{(C3)} we see that
$$
p(\Delta) = (1-p)^{|{\mathcal I}_H(\Delta)|}\sum_{X \subseteq {\mathcal F}(\Delta)} p^{|X|}(1-p)^{|H \setminus {\mathcal I}_H(\Delta)|-|X|}
$$
with an analogous expression for $\tilde{p}(\Delta)$. Recalling $\tilde{p}/p=1/t$ and that defining sets have size at most $s$, an application of Lemma \ref{lem-set_system_corr} immediately yields
\begin{align}
\frac{\tilde{p}(\Delta)}{p(\Delta)} & \geq \frac{(1-\tilde{p})^{|{\mathcal I}_H(\Delta)|}}{(1-p)^{|{\mathcal I}_H(\Delta)|}}\left(\frac{1}{t}\right)^s \nonumber \\
& \geq  \left(\frac{1-\tilde{p}}{1-p}\right)^{tn/r} \left(\frac{1}{t}\right)^s  \nonumber \\
& \geq  \left(\frac{e^{-c\tilde{p}}}{e^{-p}}\right)^{tn/r} \left(\frac{1}{t}\right)^s  \nonumber \\
& =  e^{t-c} t^{-s}, \label{eq:5}
\end{align} 
with the second inequality using $(1-\tilde{p})/(1-p) \geq 1$ and $|{\mathcal I}_H(\Delta)| \geq tn/r$, and the third inequality using the standard bound $1- p\leq e^{- p}$ (valid for all real $p$). In the third inequality we also use that for $0 \leq \tilde{p} \leq (1-\varepsilon)n$ (which certainly holds, since $\tilde{p} \leq p \leq (1-\varepsilon)n$) we have
$1-\tilde p  \geq e^{-c\tilde{p}}$ for some sufficiently large $c=c(\varepsilon)$ ($c=\log(1/\varepsilon)/(1-\varepsilon)$ will do).


Inserting (\ref{eq:5}) into (\ref{eq:4}) and combining with (\ref{eq:3}) we finally get
$$
{\bf E}_\mu\left(\left|{\mathcal T}(S)_{\geq t}\right|\right) \leq t^s e^{c-t} O(r^d/t^d) \leq C2^{-t}r^d
$$
for sufficiently large $C$. 
\end{proof}

%\bigskip
%
%\textcolor{blue}{\bf Comment on Matou\v{s}ek's derivation of the suboptimal cutting lemma from the tail bound}:
%
%Matou\v{s}ek's derives the suboptimal cutting lemma from the tail bound. Recall that when we apply the suboptimal cutting lemma, we have a region $\Delta$ that is crossed by $t_\Delta (n/r)$ formulae, for some $t_\Delta$ with
%$$
%1 \leq t_\Delta \leq r.
%$$
%We seek a $1/t_\Delta$-cutting of this collection of $n^\star=t_\Delta (n/r)$ formulae.
%
%Matou\v{s}ek begins by setting $r^\star=At_\Delta\log(1+t_\Delta)$ (for some suitably chosen constant $A$), and then applying the tail bound with $(n,r)$ replaced by $(n^\star,r^\star)$. In order to apply the tail bound, we require $r^\star < (1-\varepsilon)n^\star$, that is
%$$
%At_\Delta\log(1+t_\Delta) \leq (1-\varepsilon) t_\Delta (n/r)
%$$ 
%or
%$$
%\left(\frac{A}{1-\varepsilon}\right)r \log(1+t_\Delta) \leq n. 
%$$
%It is perfectly reasonable that we have to consider some $t_\Delta$ that are on the order of $r$; but then the application of the tail bound is only valid when $r$ is at most something like $n/\log n$, and it seems to me that we cannot (at least with this approach) use the tail bound to prove the suboptimal cutting leema.   
 


\section{Optimal distal cell decomposition on the plane in $o$-minimal expansions of fields}
\label{sec: omin-cell-decomp}

Our goal in this section is to prove the following theorem.
\begin{thm}
  \label{thm:cell-dec}
Let $\CM$ be an $o$-minimal expansion of a real closed field. 
Then any  formula $\varphi(x;y)$ with $|x|=2$ admits a distal cell decomposition $\CT$ with 
$|\CT(S)| = O(|S|^2)$.
\end{thm}


% \subsection{Suboptimal $r$-cutting Lemma}
% \label{sec:suboptimal-r-cutting}
% Before we proceed with  the proof of Theorem \ref{thm:cell-dec}, we
% show how to derive from it a suboptimal $r$-catting Lemma.  The proof
% presented here is extracted from \cite[Lemma 3.5]{distal} that is an
% adaptation  of \cite[Exercise 10.3.4(b)]{mbook}.


% Let $\varphi(x;y)$ be a formula, $H\subseteq M^{|y|}$ a finite set and
% $0<r<1$.  A family $\CF$ of subsets of $M^{|x|}$ is called
% \emph{$r$-cutting} for $\varphi(x;H)$ if $\CF$ covers $M^{|x|}$ and for
% evert $\Delta\in \CF$ the size of the set $\{ s\in H \colon
% \varphi(x;s) \text{ crosses } \Delta\}$ is at most $r|H|$. 

% \begin{lem}[Suboptimal $r$-cutting lemma]\label{lem:suboptimal-r-cutting-1}
% Let $\varphi(x;y)$ be a formula and $\CT$ a uniformly definable cell
% decomposition compatible with $\varphi$. Let $0<r<1$. Then for  every finite
% $H\subseteq M^{|y|}$ there is $S\subseteq H$ such that $\CT(S)$ is an
% $r$-cutting of $\varphi(x;H)$ and $|S|\leq K r \log(r)$, where the
% constant $K$ depends only on $\varphi(x;y)$ and  formulas involved in
% definability of $\CT$.       
% \end{lem}
% \begin{proof} Let $\Psi$ and $\CI$ be from uniform definability of
%   $\CT$. By o-minimality and definability the family 
%  $\mathcal C=\{ \CI(\Delta)\cap H \colon \Delta\in
% \Psi(H)\}$ is a VC-family of subsets of $H$ whose VC-dimension $d$ is
% bounded in terms of formulas involved in $\Psi$ and $\CI$. 

% Applying $\varepsilon$-net theorem to this family with $\varepsilon=r$
% we obtain that there is $S\subseteq H$ with $|S|\leq Kd r\log{r}$
% (where $K$ is an absolute constant) such that  for $C\in \mathcal
% C$ we have $\frac{|C|}{|H|} \geq r$ implies $C\cap S \neq \emptyset$. 

% For $\Delta\in \CT(S)$ we have $\CI(\Delta)\cap S=\emptyset$, and
% therefore  $\frac{|\CI(\Delta)\cap H |}{|H|} <r$.

% Also, since $\varphi(x;s)$ crosses $S$ implies $s\in\CI(\Delta)$,
% the family $\CT(S)$ is an $r$-cutting for $\varphi(x;H)$.   

% \end{proof}


Towards this purpose, we fix a formula $\varphi(x;y)$ with $|x|=2$ (and often we will write
$x$ as $(x_1,x_2)$). 


We first construct a finite set of
formulas $\Phi(x;y)$ such that for any $s\in M^{|y|}$ the set
$\varphi(M;s)$ is a Boolean combination of $\Phi(x;s)$-definable sets,
and formulas in $\Phi(x;y)$ have a very simple form, and then we
construct a definable cell decomposition $\CT$ for
$\Phi(x;y)$ (hence also for $\varphi$)   with $|\CT(S)|=O(|S|^2)$.   

\medskip






Let $\varphi_1(x_1;x_2,y)$ be the formula
$\varphi(x_1,x_2;y)$.

 

Using $o$-minimality and definable choice  we can find  definable functions
$h_1,\dotsc,h_k\colon M\ttimes M^{|y|}\to M$ such that 
\[
h_1(a,s)\leq h_2(a,s)\leq \dotsb \leq h_k(a,s) \text{ for all } a\in
M,  s\in M^{|y|} \]
and for all $a\in M, s\in M^{|y|}$ and $i=0,\dotsc,k$ we have 
\[ h_i(a,s) < x_1,x_1'  < h_{i+1}(a,s) \rightarrow [\varphi(x_1;a,s)\leftrightarrow
\varphi(x_1';a,s)], \]
 where for convenience we let $h_0(a,s)=-\infty$ and $
 h_{k+1}(a,s)=+\infty$. 


\medskip

At this point we have that for  a fixed  $i=0,\dotsc,k$ for all $a\in
M$, $s\in M^{|y|}$ the truth value  of $\varphi(x_1,a; s)$ is constant on
the interval  $ h_i(a,s) < x_1 < h_{i+1}(a,s)$ but may vary if we
perturb  $a$. We need to partition $M$ into pieces where this truth
value does not depend on $a$. 



For $a,a'\in M$ and $s\in M^{|y|}$ we define the relation $a
\sim_s a'$ as
\begin{multline*} a\sim_s a' \text{ iff  for all } i=0,\dotsc,k
 \\ \text{ and any } h_i(a,s) < x_1
< h_{i+1}(a,s),  \,  h_i(a',s) < x_1'  < h_{i+1}(a',s) \\\text{ we have } 
 \varphi_1(x_1;a,s)\leftrightarrow
\varphi(x_1';a',s).
\end{multline*}
Clearly $\sim_s$ is an equivalence relation on $M$ with at most
$2^{k+1}$-classes  uniformly definable in
terms of $s$. Using $o$-minimality and definable choice, we can find definable functions
$u_i\colon M^{|y|}\to M$, $i=1,\dotsc,l$ with $u_1(y)\leq u_2(y) \leq \dotsb\leq
u_l(y)$ such that for all $s\in M^{|y|}$ and $i=0,\dotsc,l$ we have 
\[ u_i(s)< x_2,x_2' <u_{i+1}(s) \rightarrow x_2\sim_s x_2', \] 
where again for convenience we use $u_0(y)=-\infty$ and
$u_{l+1}(y)=+\infty$. 

We would prefer that for $s\in M^{|y|}$ each of the 
functions $x_2\mapsto h_i(x_2,s)$  is continuous. 

For $k \in \mathbb{N}$, we will write $[k]$ to denote the set $\{1,2, \ldots, k\}$. Since every definable function is piecewise continuous, we can further
partition $M$  and in addition require that for any $i=0,\dotsc,l$,
 $j\in[k]$  and
every $s\in M^{|y|}$ the function $x_2\mapsto h_j(x_2,s)$ is continuous on
the  interval $u_i(s) <x_2 < u_{i+1}(s)$. 
\medskip  

We take $\Phi(x;y)$ to be the following set of formulas (recall that $x=(x_1,x_2)$): 
\begin{gather*}
\{ x_2 = u_i(y) \colon i\in [l]\} \cup \{ x_2 < u_i(y) \colon i  \in [l] \}  \\
\cup \,  \{ x_2 > u_i(y) \colon i\in [l] \}\cup \{ x_1=h_i(x_2,y)\colon i\in [k]\} \\
\cup \, \{ x_1<h_i(x_2,y)\colon i\in [k]\} \cup \{ x_1>h_i(x_2,y)\colon i\in [k]\}. 
\end{gather*}

It is not hard to see that for any $s\in M^{|y|}$ the set $\varphi(M;s)$
is a Boolean combination of $\Phi(x;s)$-definable sets. 

We now
proceed with a construction of a  definable cell
decomposition for $\Phi(x;y)$. \\


Geometrically we view $M^2$ as $(x_1,x_2)$-plane, with $x_1$ being on the
vertical axis and $x_2$ on horizontal. Then 
$\Phi(x;S)$-definable sets partition the plain by  vertical lines
$x_2=u_i(s)$ and ``horizontal'' ``curves'' $x_1=h_j(x_2,s)$. 


Unfortunately we cannot use complete $\Phi$-types over $S$ as
$\CT(S)$.  Since $S$ is finite every complete $\Phi$-type is equivalent
to a formula however in general we cannot get uniform definability. 


Consider a simple example of a partition of a plane by straight lines,
i.e. the case when we don't have functions $u_i$ and 
have only one $h(x_2,a,b)$ defining the straight  
lines $x_1=ax_2+b$.  In the example below all points in the gray area have the same
$\Phi$-type, but we need at least $5$ lines to describe the region; and in general, this
number may be as big as one wants.\\   


\begin{tikzpicture}[scale=0.4]
\draw[->,ultra thick] (-0.5,0.5)--(20,0.5) node[right]{$x_2$};
\draw[->,ultra thick] (0.5,-0.5)--(0.5,10) node[left]{$x_1$};
\draw[thick] (0,2)--(20,2);
\draw[thick] (0,4)--(6,10);
\draw[thick] (0,6)--(8,0);
\draw[thick] (0,7)--(20,7);
\draw[thick] (8,10)--(20,4);
\draw[thick] (0, 0.66)--(20,7.5); 
% \filldraw[black] (1.15,5.1) circle (2pt);
% \filldraw[black] (3,7) circle (2pt);
% \filldraw[black] (14,7) circle (2pt);
% \filldraw[black] (15.85,6.1) circle (2pt);
% \filldraw[black] (4.9,2.4) circle (2pt);
\fill[gray!50] (1.2,5.15)--(3,7) --(14,7)--(15.85,6.1)--(4.9,2.38)--cycle;
\end{tikzpicture}  

We could solve this problem by using also vertical lines  through all
points of intersections, as shown
below, but then the size of the partition would be $O(|S|^3)$. \\


\begin{tikzpicture}[scale=0.4]
\draw[->,ultra thick] (-0.5,0.5)--(20,0.5) node[right]{$x_2$};
\draw[->,ultra thick] (0.5,-0.5)--(0.5,10) node[left]{$x_1$};
\draw[thick] (0,2)--(20,2);
\draw[thick] (0,4)--(6,10);
\draw[thick] (0,6)--(8,0);
\draw[thick] (0,7)--(20,7);
\draw[thick] (8,10)--(20,4);
\draw[thick] (0, 0.66)--(20,7.5); 
\draw[dashed] (1.15,0) --  (1.15,10);
\draw[dashed] (3,0) -- (3,10);
\draw[dashed] (4.9,0) -- (4.9,10);
\draw[dashed] (5.4,0) -- (5.4,10);
\draw[dashed] (14,0) -- (14,10);
\draw[dashed] (15.85,0)--(15.85, 10);
\draw[dashed] (18.5,0)--(18.5, 10);
\end{tikzpicture}  

Using the idea of ``vertical decomposition''  from \cite{13}
we  add only vertical line segments where they are
needed, i.e. from an intersection point to the first line above (or plus infinity) and
the first line below (or minus infinity), as in the following picture.

\begin{tikzpicture}[scale=0.4]
\draw[->,ultra thick] (-0.5,0.5)--(20,0.5) node[right]{$x_2$};
\draw[->,ultra thick] (0.5,-0.5)--(0.5,10) node[left]{$x_1$};
\draw[thick] (0,2)--(20,2);
\draw[thick] (0,4)--(6,10);
\draw[thick] (0,6)--(8,0);
\draw[thick] (0,7)--(20,7);
\draw[thick] (8,10)--(20,4);
\draw[thick] (0, 0.66)--(20,7.5); 
\draw[dashed] (1.15,2) --  (1.15,7);
\draw[dashed] (3,3.8) -- (3,10);
\draw[dashed] (4.9,2) -- (4.9,7);
\draw[dashed] (5.4,0) -- (5.4,2.55);
\draw[dashed] (14,5.5) -- (14,10);
\draw[dashed] (15.85,2)--(15.85, 7);
\draw[dashed] (18.5,4.69)--(18.5, 10);
\end{tikzpicture}  

Our  general case is slightly more complicated since the functions
$x_2\mapsto h_i(x_2,s)$ are not linear and even not continuous, just
piecewise continuous, so their graphs may intersect without one crossing
another.  \\


For $i\in [l]$ and $s\in M^{|y|}$ we will denote by $\hat u_i(s)$ the
corresponding vertical line 
\[ \hat u_i(s) :=\{ (x_1,x_2)\in M^2 \colon x_2=u_i(s)\},
 \]
and also for $i\in [k]$ and $s\in M^{|y|}$ we will denote by $\hat h_i(s)$
the ``curve''
\[ \hat h_i(s) :=\{ (x_1,x_2)\in M^2 \colon x_1=h_i(x_2,s)\}. \]


For $i,j\in [k]$,$s_1,s_2\in M^{|y|}$ and $(a,b)\in \RR^2$ we say that 
$\hat h_i(s_1)$ and $\hat h_j(s_2)$ \emph{properly intersect} at
$(a,b)$  if $(a,b)\in \hat h_i(s_1)\cap \hat h_j(s_2)$ and 
$\hat h_i(s_1),\hat h_j(s_2)$ have different germs at $(a,b)$.  
Formally it means that 
$a=h_i(b,s_1)=h_j(b,s_2)$  and for any $\varepsilon>0$ there is
$b'\in (b-\varepsilon, b+\varepsilon)$ with $h_i(b',s_1)\neq
h_j(b',s_2)$.  We will denote by $\hat h_i(s_1) \sqcap  \hat h_j(s_2)$
the set of all points $(a,b)\in M^2$ where   $\hat h_i(s_1)$ and  $
\hat h_j(s_2)$ intersect properly.  It is easy to see using
$o$-minimality that the set
$\hat h_i(s_1) \sqcap  \hat h_j(s_2)$
is finite and there is $N_l\in \NN$ such that 
$|\hat h_i(s_1) \sqcap \hat  h_j(s_2)|\leq N_l$ for all $i,j\in [k]$
and $s_1,s_2\in M^{|y|}$. Also all points in $\hat  h_i(s_1)\sqcap  \hat
h_j(s_2)$ are definable over $s_1,s_2$, i.e. there are definable
functions $f_{i,j}^m(y_1,y_2)$ with $m\in [N_l]$ such that for all
$s_1,s_2$ the set $\hat  h_i(s_1)\sqcap  \hat
h_j(s_2)$ is either empty or it is exactly $\{ f_{ij}^m(s_1,s_2) \colon
m\in [N_l] \}$. 




\medskip
We will construct a definable cell decomposition $\CT(S)$ for 
$\Phi(x;y)$ as a union  of 5 families  of
cells: 
\begin{itemize}
\item $\CT_0(S)$ -- 0-dimensional cells, i.e. points; 
\item $\CT_1^u(S)$ -- 1-dimensional ``vertical'' cells;
\item $\CT_1^e(S)$ -- extra 1-dimensional vertical cells;
\item $\CT_1^h(S)$ -- 1-dimensional ``horizontal'' cells; 
\item $\CT_2(S)$ -- 2-dimensional cells. 
\end{itemize}
For each family $\CT_{\star}^\star(S)$ we will have
$|\CT_\star^\star(S)|=O(|S|^2)$, and also we will have  appropriate
uniformly definable $\Psi_\star^\star(S)$ and $\CI_\star^\star(\Delta)$
so that $\CT^\star_\star(S)=\{ \Delta\in \Psi_\star^\star(S)
\colon \CI_\star^\star(\Delta) \cap S =\emptyset\}$. 

\medskip

\textbf{ The family $\mathbf{\CT_0(S)}$.}  We take $\CT_0(S)$ to be the
set of all points of intersections of vertical lines $\hat u_i(s)$ and
curves $\hat h_j(s')$ together with all points where 
curves $\hat h_i(s)$ and $\hat h_j(s')$ intersect properly. I.e.,
\begin{gather*}
\CT_0(S)=\cup \{ (\hat u_i(s)\cap \hat  h_j(s') \colon 
i\in [l];  j\in [k]; s,s'\in S\}\,   \\ 
\cup\, \{ \hat h_i(s) \sqcap \hat  h_j(s') \colon i,j\in [k]; 
s,s'\in S \}.
\end{gather*}

We take $\Psi_0(S) :=\CT(S)$ and $\CI_0(\Delta) :=\emptyset$. 

It is easy to see that  $\Psi_0(S)$ is uniformly definable. 

We also have $|\CT_0(S)|\leq k l|S|^2 + N_lk^2|S|^2 =O(|S|^2)$.


\medskip

\textbf{ The set $\mathbf{\CT_1^u(S)}$.}
For fixed  $i\in [l]$ and $s\in S$ let 
$I_i^s$ be the set of all definably connected components of $\hat
u_i(s) \setminus \CT_0(S)$.

Since 
\[ \hat u_i(s) \cap \CT_0(S)=\{ \hat u_i(s)\cap \hat h_j(s')\colon 
j\in [k], s'\in S\}, \]
we have $|I_i^s|\leq (k+1)|S|$, and every $\Delta\in  I_i^s$ has form 
\[ \Delta=\{ (x_1,x_2) \in M^2 \colon x_2=u_i(s); h_j(s_1) < x_1 < h_{j'}(s_2) \}, \]
for some $j,j'\in \{ 0,\dotsc, k+1\}$, and  $s_1,s_2\in S$. 

We take $\CT^u_1 (S)$ to be the union of all  $I_i^s$ for $i\in
[l]$ and $s\in S$.  Clearly $|\CT_1^u(S)|\leq l(k+1)|S|^2 =O(|S|^2)$.


We take $\Psi_1^u(S)$ to be the set of all vertical lines segments 
of the form 
$\{ (x_1,x_2) \in M^2 \colon x_2=u_i(s); h_j(s_1) < x_1 < h_{j'}(s_2)
\}$, for $i\in [l]$, $j,j'\in \{ 0,\dotsc, k+1\}$, $s,s_1,s_2\in S$.
For $\Delta\in \Psi_1^u(S)$  we take $\CI_1^u(\Delta) :=\{ s\in M^{|y|} \colon 
\Phi(x;s) \text{ crosses } \Delta\}$. 


It is not hard to see that $\Psi_1^u$ and $\CI_1^u$ are uniformly
definable and $\CT_1^u(S)= \{ \Delta\in \Psi_1^u(S) \colon
\CI_1^u(\Delta)\cap S = \emptyset\}$. 


\medskip
\textbf{ The set $\mathbf{\CT_1^e(S)}$.} For each point where two horizontal curves  intersect properly we add two vertical
line segments: one from the point to the curve above (or to plus infinity if there is no curve above) and one to the
curve below (or to minus infinity if there is no curve below). 



Let  $i,j\in [k]$, $s,s_1\in S$ and $p=(p_1,p_2)\in \hat h_i(s) \sqcap
\hat h_j(s_1)$.


Let \[p^+ :=\inf \{ h_m(p_2,s') \colon m=1,\dotsc,k+1; s'\in S;
h_m(p_2,s')>p_1\},\]
and  
\[p^- :=\sup\{ h_m(p_2,s') \colon m=0,\dotsc,k; s'\in S;
h_m(p_2,s')<p_1\}.\]

We define $I_p^+ :=\{ (x_1,x_2)\in M^2 \colon x_2=p_2;\, p_1<x_1<p^+
\}$, $I_p^- :=\{ (x_1,x_2)\in M^2 \colon x_2=p_2;\, p^-<x_1<p_1
\}$; and take 
\[ \CT_1^e(S) := \{ I_p^+, I_p^- \colon p\in \hat h_i(s) \sqcap
\hat h_j(s_1); \, i,j\in [k]; \,  s,s_1\in S\}. \]

Obviously $|\CT_1^e(S)| \leq 2N_l k^2|S|^2 =O(|S|^2)$. 


We take $\Psi_1^e(S)$ to be the family of all sets of the form 
\[ \{ (x_1,x_2)\in M^2 \colon x_2=p_2;\, p_1<x_1< h_m(p_2,s') 
\}\] 
for all $i,j\in [k]$, $m\in \{ 1,\dotsc,k+1\}$, $s,s_1,s'\in S$, and
$p=(p_1,p_2)\in   \hat h_i(s) \sqcap
\hat h_j(s_1)$; and of the form 
\[ \{ (x_1,x_2)\in M^2 \colon x_2=p_2;\, h_m(p_2,s')<x_1<  p_1
\}\] 
for all $i,j\in [k]$, $m\in \{ 0,\dotsc,k\}$, $s,s_1,s'\in S$, and
$p=(p_1,p_2)\in   \hat h_i(s) \sqcap
\hat h_j(s_1)$. It is not hard to see that $\Psi(S)$ is uniformly
definable. 

For $\Delta\in \Psi_1^e(S)$ we take $\CI_1^e(\Delta) :=\{ s\in M^{|y|} \colon
\Phi(x;s) \text{ crosses } \Delta\}$.  It is not hard to see
$\CI_1^e(\Delta)$ is uniformly
definable and $\CT_1^e(S)= \{ \Delta\in \Psi_1^e(S) \colon
\CI_1^e(\Delta)\cap S = \emptyset\}$. 


\medskip

\textbf{ The set $\mathbf{\CT_1^h(S)}$.}
Given  $i\in [k]$ and $s\in S$, let $J_i^s$ be the set of all definably
connected components of $\hat h_i(s) \setminus \CT_0(S)$. 
It is easy to see that  
\begin{multline*}
 \hat h_i(s)\cap \CT_0(S)=\{ \hat h_i(s)\cap \hat u_j(s')\colon j\in
[l]; s'\in S \}  \\
\cup\, \{ \hat h_i(s)\sqcap \hat h_j(s')\colon j\in
[k]; s'\in S \}. 
\end{multline*}
In particular $|J_i^s|\leq (l+N_l k+1)|S|$. 

We take $\CT_1^h(S)$ to be the union of all $J_i^s$ for $i\in [k]$,
$s\in S$.   Clearly $|\CT_1^h (S)|\leq k(l+N_l k+1)|S|^2=O(|S|^2)$.






Given  $i\in [k]$, $s\in S$ and $s_1,s_2\in S$ let   
$\mathcal A_{i,s}[s_1,s_2]$  be the family of all sets of the form $\{ (x_1,x_2)\in \hat h_i(s); c_1<x_2 < c_2
  \},$ with 
\begin{multline*}
 c_1,c_2\in \{ u_j(s_1) \colon j\in [l]\}\\ 
\cup \,\{ p_2
  \colon (p_1,p_2) \in \hat h_i(s) \sqcap \hat h_j(s_2) \text{ for some }
  p_1\}\cup
\{ \pm\infty\}.
\end{multline*}


We take $\Psi_1^h(S)$ to be the union of all $\mathcal A_{i,s}[s_1,s_2]$ with $i\in
[k]$ and $s,s_1,s_2\in S$.
 It is not hard to see that 
$\Psi_1^h(S)$ is uniformly
definable and $\CT_1^h(S)= \{ \Delta\in \Psi_1^h(S) \colon
\CI_1^h(\Delta)\cap S = \emptyset\}$, where $\CI_1^h(\Delta)=\{ s\in M^{|y|} \colon
\Phi(x;s) \text{ crosses } \Delta\}$.

\medskip



\textbf{ The set $\mathbf{\CT_2(S)}$.} For the family $\CT_2(S)$ we
take all definably connected components of $M^2\setminus
(\CT_0(S)\cup
\CT_1^u(S)\cup
\CT_1^e(S)\cup
\CT_1^h(S))$.




Given  $i,j\in \{0,\dotsc,k+1\}$ , $s_1,s_2\in S$   and  $c_1<c_2\in
M\cup\{\pm\infty\}$ 
with $h_i(x_2,s_1)< h_j(x_2,s_2)$ for all $x_2\in (c_1,c_2)$,
let
$A_{i,s_1}^{j,s_2}(c_1,c_2)$  be the set 
\[ A_{i,s_1}^{j,s_2} (c_1,c_2) =\{ (x_1,x_2)\in M^2\colon c_1<x_2 < c_2;\,
h_i(x_2,s_1)< x_1< h_j(x_2,s_2)  \}.  \]


It is not hard to see that if  $\Delta\in \CT_2(S)$ then $\Delta=
A_{i,s_1}^{j,s_2} (c_1,c_2)$ for some $i,j\in\{0,\dotsc,k+1\}$,
 $s_1,s_2\in S$ and $c_1,c_2$  belonging to the following
set:
\begin{gather*}S_{i,s_1}^{j,s_2}=\{  u_{i'}(s') \colon i'\in \{ 0,\dotsc l+1\}; s'\in
  S\} \\ 
\cup\,\{ p_2 \colon (p_1,p_2)\in \hat h_i(s_1)\sqcap \hat h_{i'}(s') 
\text{ for some } i'\in [k], s'\in S, p_1\in M \} \\
\cup\,\{ p_2 \colon (p_1,p_2)\in \hat h_j(s_2)\sqcap \hat h_{i'}(s') 
\text{ for some } i'\in [k], s'\in S, p_1\in M \}. 
\end{gather*}


We take $\Psi_2(S)$ to be the family of all $A_{i,s_1}^{j,s_2}
(c_1,c_2)$, for all $c_1,c_2\in S_{i,s_1}^{j,s_2}$. 

It is not hard to see that $\Psi_2(S)$ is uniformly definable family,
and we have $\CT_2(S) \subseteq \Psi_2(S)$. 


It is also not hard to see that a set $\Delta\in \Psi_2(S)$ is in
$\CT_2(S)$ if and only if it is not crossed by $\Phi(x;S)$, and is also not crossed
by any line segment in $\CT_1^e(S)$.  


Hence a set $\Delta=A_{i,s_1}^{j,s_2}(c_1,c_2)\in \Psi_2(S)$ \textbf{ is not in } $\CT_2(S)$ if and
only if there is $s\in S$ satisfying at least one of the following conditions. 
\begin{enumerate}[(C1)]
\item  $\Phi(x;s)$ crosses $\Delta$. 
\item There are  $i'\in [k]$ and 
  $(p_1,p_2)\in  \hat h_i(s_1) \sqcap \hat h_{i'}(s)$ with
  $c_1<p_2<c_2$.
\item There are  $i'\in [k]$ and 
  $(p_1,p_2)\in  \hat h_j(s_2) \sqcap \hat h_{i'}(s)$ with
  $c_1<p_2<c_2$.
\end{enumerate}


For $\Delta\in \Psi_2(S)$ we take $\CI_2(\Delta)$ to be the set of all
$s\in M^{|y|}$ satisfying any of the conditions $(C1)-(C3)$. It is not
hard to see that $\CI_2(\Delta)$ is uniformly definable and
$\CT_2(S)=\{ \Delta\in \Psi_2(S) \colon \CI_2(\Delta)\cap S
=\emptyset\}$. 

\medskip


We are left to check that $|\CT_2(S)|=O(|S|^2)$. 

Since $\CT_2(S)$ consists of definably connected components  of 
 $M^2\setminus
(\CT_0(S)\cup
\CT_1^u(S)\cup
\CT_1^e(S)\cup
\CT_1^h(S))$, any two $\Delta,\Delta'\in \CT_2(S)$ are either disjoint
or coincide, hence every $\Delta\in \CT_2(S)$ is completely determined
by its ``left lower corner'', i.e. if   $\Delta=A_{i,s_1}^{j,s_2}(c_1,c_2)$
and $\Delta'=A_{i,s_1}^{j',s'_2}(c_1,c'_2)$ are in $\CT_2$ then
$\Delta=\Delta'$. 


We divide $\CT_2(S)$ into 4 disjoint families: 
\begin{itemize}
\item The family $F_1(S)$ of all $A_{i,s_1}^{j,s_2}(c_1,c_2)\in \CT_2(S)$
  with $c_1=-\infty$. 



\item  The family $F_2(S)$ of all $A_{i,s_1}^{j,s_2}(c_1,c_2)\in \CT_2(S)$
  with $c_1=u_{i'}(s')$ for some $i' \in [l]$ and $s'\in S$.
\item  The family $F_3(S)$ of all $A_{i,s_1}^{j,s_2}(c_1,c_2)\in \CT_2(S)$ 
that are not in $F_2(S)$ and $(p_1,c_1)\in \hat h_i(s_1)\sqcap \hat
h_{i'}(s')$  for some $i' \in [k]$, $s'\in S$, and $p_1\in  M$. 

\item  The family $F_4(S)$ of all $A_{i,s_1}^{j,s_2}(c_1,c_2)\in \CT_2(S)$ 
that are not in $F_1(S)\cup F_2(S)\cup F_3(S)$.  In this case we have that $\{ (x_1,c_1) \colon h_i(c_1,s_1)< x_1
< h_j(c_1,s_2) \}\in \CT_1^e(S)$.
\end{itemize}

Every  $A_{i,s_1}^{j,s_2}(c_1,c_2)\in F_1(S)$ is completely determined by
$i$ and $s_1$, hence $|F_1(S)|\leq (k+1)|S|$ (we get $k+1$, since we
allow $i=0$). 

Every $A_{i,s_1}^{j,s_2}(c_1,c_2)\in F_2(S)$ is completely determined by
$i$, $s_1$, some $i'\in [l]$ and $s'\in S$. Hence 
$|F_2(S)|\leq (k+1)l|S|^2$.

Since $ \hat h_i(s_1)\sqcap \hat
h_{i'}(s')\leq N_l$ we have $|F_3(S)|\leq k^2N_l|S|^2$. 
 

Finally,  each $A_{i,s_1}^{j,s_2}(c_1,c_2)\in F_4(S)$  is completely
determined by its ``left side'' $\{ (x_1,c_1) \colon h_i(c_1,s_1)< x_1
< h_j(c_1,s_2) \}$ that is in $\CT_1^e(S)$. Since
$|\CT_1^e(S)|=O(|S|^2)$, we also have $|F_4(S)|=O(|S|^2)$.


Therefore $|\CT_2(S)|=O(|S|^2)$. 

\medskip

Taking $\CT(S)=\CT_0(S)\cup
\CT_1^u(S)\cup
\CT_1^e(S)\cup
\CT_1^h(S)\cup \CT_2(S)$ we obtain a definable cell decomposition
for $\Phi(x;y)$ with $|\CT(S)|=O(|S|^2)$. 

\section{Planar Zarankiewicz's problem in distal structures}\label{sec: Zarank}

\subsection{Zarankiewicz's problem}

Zarankiewicz's problem in graph theory asks to determine the largest possible number of edges in a bipartite graph on a given number of vertices that has no complete bipartite subgraphs of a given size.

In \cite{zaran} the authors investigate Zarankiewicz's problem for semialgebraic graphs of bounded description complexity, a setting which in particular subsumes a lot of different incidence-type questions.

In particular, they prove the following upper bound on the number of edges (they have more general results in $\mathbb{R}^n$ for arbitrary $n$ as well, but here we will be only concerned with the ``planar'' case). 
\begin{fact} \cite[Theorem 1.1]{zaran}\label{fac: semialg zarank}
Let $E \subseteq \mathbb{R}^2 \times \mathbb{R}^2$ be a semi-algebraic relation such that $E$ has description complexity at most $t$ (i.e., $E$ can be defined as a Boolean combination of at most $t$ polynomial inequalities, with all of the polynomials involved of degree at most $t$). Then for any $k \in \mathbb{N}$ there is some constant $c = c(t,k)$ satisfying the following.

If $P, Q \subseteq \mathbb{R}^2$ with $|P|=m, |Q|=n$ are such that $E \cap (P \times Q)$ doesn't contain a copy of $K_{k,k}$ (the complete bipartite graph with both parts of size $k$), then
$$|E(P,Q)| \leq c \left( (mn)^{\frac{2}{3}} + m + n \right),$$

where $E(P,Q) = E \cap (P \times Q)$.

\end{fact}

\begin{rem} This result is a natural generalization of the Szemer\'edi-Trotter theorem over $\RR$ \cite{szemeredi1983extremal}. Namely, if $P$ a set of points on the plane, $Q$ the dual of the lines (i.e.  lines are semialgebraically coded by points in $\mathbb{R}^2$), and $E$ the incidence relationship (which is also clearly semialgebraic), then $E(P,Q)$ is $K_{2,2}$-free as any two distinct lines intersect in at most one point.
\end{rem}

We will give a common generalization of Fact \ref{fac: semialg zarank} and the semialgebraic ``points / planar curves'' incidence bound from \cite[Theorem 4]{pach1992repeated} to arbitrary definable families admitting a quadratic distal cell decomposition (e.g. any definable family of subsets of $M^2$ in an $o$-minimal expansion of a field). To state the result, we first recall the notion of the VC-density of a formula (and refer to \cite{VCD1} for a detailed discussion).

\begin{defn}
\begin{enumerate}
\item Given a set $X$ and a family $\CF$ of subsets of $X$, the \emph{shatter function} $\pi_{\CF}: \mathbb{N} \to \mathbb{N}$ of $\CF$ is defined as
$$ \pi_{\CF}(n) := \max \{ |\CF \cap A| : A \subseteq X, |A| = n \}, $$
where $\CF \cap A = \{ S \cap A : S \in \CF \}$.

\item The \emph{VC-density} of $\CF$, or $\vc(\CF)$, is defined as the infimum of all real numbers $r$ such that $\pi_{\CF}(n) = O(n^r)$ (and $\vc(\CF) = \infty$ if there is no such $r$).

\item Given a formula $\varphi(x;y)$, we define its VC density $\vc(\varphi)$ as the VC-density of the family $\{ \varphi(M,b) : b \in M^{|y|}\}$ of subsets of $M^{|x|}$.

\item Given a formula $\varphi(x;y)$, we consider its dual formula $\varphi^*(y;x) := \varphi(x;y)$ obtained by interchanging the roles of the variables. It is easy to see then that the family $\{ \varphi^*(y; a) : a \in M^{|x|}\}$ of subsets of $M^{|y|}$ is the dual set system for the family $\{ \varphi^*(x; b) : b \in M^{|y|}\}$ of subsets of $M^{|x|}$.
\end{enumerate}

\end{defn}

VC-density in various classes of NIP structures is investigated e.g. in \cite{VCD1, VCD2}, and the optimal bounds are known in some cases including the $o$-minimal structures.

\begin{fact} \cite[Theorem 6.1]{VCD1}\label{fac: vc bound in o-min}
Let $\CM$ be an $o$-minimal structure, and let $\varphi(x;y)$ be any formula. Then $\vc(\varphi^*) \leq |x|$.
\end{fact}

\begin{rem}\label{rem: distal decomp bounds dual VC density}
Let $\varphi(x;y)$ be a formula admitting a distal cell decomposition $\CT$ with $|\CT(S)| = O(|S|^d)$. Then $\vc(\varphi^*) \leq d$. 

Indeed, recalling Definition \ref{def: def cell decomp}, given any finite $S \subseteq M^{|y|}$ and $\Delta \in \CT(S)$, $S \cap \varphi^*(M,a) = S \cap \varphi^*(M,a')$ for any $a,a' \in \Delta$ (and the sets in $\CT(S)$ give a covering of $M^{|x|}$), hence at most $|S|^d$ different subsets of $S$ are cut out by the instances of $\varphi^*(y;x)$.
\end{rem}



We will need the following weaker bound that applies to graphs of bounded VC-density.

\begin{fact} \label{VCBoundOnEdges}
\cite[Theorem 2.1]{zaran} For every $c, d, k$ there is some constant $c_1 = c_1(c,d,k)$ such that the following holds.

  Let $E \subseteq P \times Q$ be a bipartite graph with $|P|=m, |Q|=n$ such that the family of sets $\CF = \{ E(q) : q \in Q \}$ satisfies $\pi_{\mathcal{F}}(z) \leq c z^d$ for all $z \in \mathbb{N}$ (where $E(q) = \{ p \in P : (p,q) \in E \}$). Then if $E$ is $K_{k,k}$-free, we have 
$$|E(P,Q)| \leq c_1(m n^{1- 1/d}+n).$$
\end{fact}


%We remark that conversely, existence of any bound of this form with $d$ independent of $k$ implies NIP.
%\begin{rem}
%Assume that for any definable relation $E$ there is some $d = d(E)$ such that for any $k$ there is some $c = c(E,k)$ such that if $G$ is $K_{k,k}$-free then $|E(G)| \leq c(m n ^{1 - 1/d} + n)$. Then $T$ is NIP.
%\end{rem}
%\begin{proof}
%
%The following lower bound on Zarankiewicz numbers for general graphs is known for $n=m$ from \cite{bohman2010early}: for $k\geq 5$ there are $K_{k,k}$-free graphs with $m=n$ such that $\Omega(n^{2-\frac{2}{k}} (\log k)^{\frac{1}{k^2-1}})$. As for any fixed $d$ taking $k$ large enough we have that for any $c,c' > 0$,  $c(n^{2 - \frac{1}{d}} + n) < c' n^{2 - \frac{2}{k}}$ for all $n$ large enough, and any finite bipartate graph is encoded by the formula witnessing IP, we can conclude that no bound of this form is possible.
%\end{proof}

We are ready to prove the main theorem of this section.

\begin{thm}\label{thm: distal Zarank}
Let $\CM$ be a structure, and assume that $E(x,y)$ is a formula admitting a distal cell decomposition $\CT$ with    $|\CT(S)| = O(|S|^2)$ and such that $\vc(E) \leq d$. Then for any $k \in \mathbb{N}$ there is a constant $c = c(E,k)$ satisfying the following.

For any finite $P \subseteq M^{|x|}, Q \subseteq M^{|y|}$, $|P|=m, |Q| = n$, if $E(P,Q)$ is $K_{k,k}$-free, then we have:
$$ |E(P,Q)| \leq c \left( m^{\frac{d}{2d-1}} n^{\frac{2d-2}{2d-1}} + m + n \right).$$
\end{thm}


\begin{proof} 

Our argument is a generalization of the proofs of \cite[Theorem 3.2]{zaran} and \cite[Theorem 4]{pach1992repeated}.

If $n > m^d$, then by Fact \ref{VCBoundOnEdges} and assumption we have 
$$|E(P,Q)| \leq c_0 ( m n^{1 - \frac{1}{d}} + n) \leq c_0 (n^{\frac{1}{d}} n^{1 - \frac{1}{d}} + n) =  2c_0n$$ 
for some $c_0 = c_0(E,d,k)$, and we are done.
Hence we assume $n \leq m^2$.

Let $r := \frac{m^{\frac{d}{2d-1}}}{n^{\frac{1}{2d-1}}}$, and consider the family $\Sigma = \{E(M,q) : q \in Q\}$ of subsets of $M^{|x|}$. By assumption and Theorem \ref{lem-r_cut}, there is a family $\mathcal{C}$ of subsets of $M^{|x|}$ giving a $1/r$-cutting with respect to $\Sigma$. That is, $M^{|x|}$ is covered by the union of the sets in $\mathcal{C}$ and any of the sets $C \in \mathcal{C}$ is crossed by at most $|\Sigma|/r$ elements from $\Sigma$. Moreover, $|\mathcal{C}| \leq c_1 r^2$ for some $c_1 = c_1(E)$.

Then there is a set $C \in \mathcal{C}$ containing at least $\frac{m}{c_1 r^2} = \frac{n^{\frac{2}{2d-1}}}{c_1 m ^{\frac{1}{2d-1}}}$ points from $P$. Let $P' \subseteq P \cap C$ be a subset of size exactly $\lceil \frac{n^{\frac{2}{2d-1}}}{c_1 m ^{\frac{1}{2d-1}}} \rceil$.

If $|P'| < k$, we have $\frac{n^{\frac{2}{2d-1}}}{c_1 m ^{\frac{1}{2d-1}}} \leq |P'| < k$, so $n < k^{\frac{2d-1}{2}} c_1^{\frac{2d-1}{2}}m^{\frac{1}{2}}$.
Then by  Fact \ref{VCBoundOnEdges} applied to the dual formula $E^*$ (and using Remark \ref{rem: distal decomp bounds dual VC density}) we have 
$$|E(P,Q)| \leq c_2(n m^{1 - \frac{1}{2}} + m) \leq c_2(k^{\frac{2d-1}{2}} c_1^{\frac{2d-1}{2}}m^{\frac{1}{2}} m^{\frac{1}{2}} + m) \leq c_3 m$$
for some $c_3 = c_3 (E,k)$, so we are done.

Hence we may assume that $|P'| \geq k$. 
Let $Q'$ be the set of all points $q \in Q$ such that $E(M,q)$ crosses $C$. We know that 
$$|Q'| \leq \frac{|Q|}{r} \leq  \frac{n n^{\frac{1}{2d-1}}}{m^{\frac{d}{2d-1}}} = \frac{n^{\frac{2d}{2d-1}}}{m^{\frac{d}{2d-1}}} \leq c_1^d |P'|^d.$$
Again by Fact \ref{VCBoundOnEdges} we get 
$$|E(P',Q')| \leq c_4(|P'| |Q'|^{1-\frac{1}{d}} + |Q'|) \leq c_4 (|P'|c_1^d |P'|^{d-1} + c_1^d |P'|^d) \leq c_5 |P'|^d$$
for some $c_5 = c_5(E,k)$. Hence there is a point $p \in P'$ such that $|E(p) \cap Q'| \leq c_5 |P'|^{d-1}$.

Since $E(P,Q)$ is $K_{k,k}$-free, there are at most $k-1$ points in $Q\setminus Q'$ from $E(p)$ (otherwise, since none of those points crosses $C$ and $C$ contains $P'$, which is of size $\geq k$, we would have a copy of $K_{k,k}$).
Hence 
$$|E(p)| \leq c_5 |P'| + (k-1) \leq \frac{c_5}{c_1} \frac{n^{\frac{2(d-1)}{2d-1}}}{m^{\frac{d-1}{2d-1}}} + (k-1).$$

We remove $p$ and repeat the argument until we have no vertices remaining in $P$, and see that 
$$|E(P,Q)| \leq (c/2)(n+m) + \sum_{i=n^{\frac{1}{d}}}^{m} \left( \frac{c_5}{c_1} \frac{n^{\frac{2(d-1)}{2d-1}}}{i^{\frac{d-1}{2d-1}}} + (k-1) \right)$$
$$ \leq (c/2)(n+m) + \frac{c_5}{c_1} n^{\frac{2(d-1)}{2d-1}} \sum_{i=n^{\frac{1}{d}}}^{m} \frac{1}{i^{\frac{d-1}{2d-1}}} + (k-1) m $$
$$\leq (c/2)(n+m) + \frac{c_5}{c_1} n^{\frac{2(d-1)}{2d-1}} m^{1-\frac{d-1}{2d-1}} + (k-1)m$$
$$ \leq c ( m^{\frac{d}{2d-1}} n^{\frac{2d-2}{2d-1}} + m + n)$$
for a sufficiently large $c = c(E,k)$.
\end{proof}

\subsection{Omitting $K_{k,k}$ versus omitting infinite complete bipartite graphs}
We recall a theorem of Bukh and Matou\v{s}ek.

\begin{fact}\cite[Theorem 1.9]{bm}\label{fac: semialg BM}
For every $d,D$ and $k$ there exists $N$ such that for every semialgebraic relation $R(x_1, \ldots, x_k)$ with $|x_1| = \ldots = |x_k|=d$ of description complexity $D$, the following two conditions are equivalent.
\begin{enumerate}
\item There exist $A_1, \ldots, A_k \subseteq \mathbb{R}^d$ such that $|A_1| = \ldots = |A_k| = N$ and $A_1 \times \ldots \times A_k \subseteq R$.
\item There exist \emph{infinite} sets $A_1, \ldots, A_k \subseteq \mathbb{R}^d$ such that $A_1 \times \ldots \times A_k \subseteq R$.
\end{enumerate}

\end{fact}

We give a generalization of this result for any distal structure in which finite sets in every definable family have a uniform bound on their size.
Recall:

\begin{defn}\label{def: elimination of infinity}
An $\mathcal{L}$-structure $\mathcal{M}$ \emph{eliminates $\exists^\infty$} if for every $\varphi(x,y) \in \mathcal{L}$ there is some $n_\varphi \in \mathbb{N}$ such that for any $b \in M^{|y|}$, $\varphi(M,b)$ is infinite if and only if $|\varphi(M,b)| \geq n_\varphi$.
\end{defn}

We will use the definable strong Erd\H{o}s-Hajnal property for hypergraphs in distal structures from \cite{distal} (and we will use some terminology from that paper in our argument).
\begin{fact}\cite[Corollary 4.6]{distal}\label{fac: definable strong EH in distal}
Let $\mathcal{M}$ be a distal $\mathcal{L}$-structure. Then for every formula $\varphi(x_1, \ldots, x_k; z) \in \mathcal{L}$ there are some $\alpha > 0$ and formulas $\psi_i(x_i, y_i) \in \mathcal{L}$ for $1 \leq i \leq k$ such that the following holds.

For any generically stable Keisler measures $\mu_i$ on $M^{|x_i|}$ and any $c \in M^{|z|}$, there are some $b_i \in M^{|y_i|}$ such that $\mu_i(\psi_i(M^{|x_i|},b_i)) \geq \alpha$ and either $\prod_{1\leq i \leq k} \psi_i(M^{|x_i|},b_i) \subseteq \varphi(M^{|x_1|}, \ldots, M^{|x_k|}; c)$ or $\prod_{1\leq i \leq k} \psi_i(M^{|x_i|},b_i) \subseteq \neg \varphi(M^{|x_1|}, \ldots, M^{|x_k|}; c)$.
\end{fact}


\begin{thm}\label{thm: distal BukhMatousek}
Let $\mathcal{M}$ be a distal $\mathcal{L}$-structure eliminating $\exists^{\infty}$. Then for any formula $\varphi(x_1, \ldots, x_k;z) \in \mathcal{L}$ there is some $N \in \mathbb{N}$ and $\psi_i(x_i,y_i) \in \mathcal{L}$, for $1\leq i \leq k$, such that the following are equivalent for any $c \in M^{|z|}$, letting $R \subseteq M^{|x_1|} \times \ldots \times M^{|x_k|}$ be given by $R := \varphi(M^{|x_1|}, \ldots, M^{|x_k|}, c)$.

\begin{enumerate}
\item There exist $A_i \subseteq M^{|x_i|}$ for $1\leq i \leq k$ such that $|A_1| = \ldots = |A_k| = N$ and $A_1 \times \ldots \times A_k \subseteq R$.
\item There are some $b_i \in M^{|y_i|}$ such that $\psi_i(M^{|x_i|}, b_i)$ is infinite for all $1 \leq i \leq k$ and $\psi_1(M^{|x_1|}, b_1) \times \ldots \times \psi_k(M^{|x_k|}, b_k) \subseteq R$.
\end{enumerate}

\end{thm}
\begin{proof}
Let $\alpha > 0$ and $\psi_i(x_i,y_i) \in \mathcal{L}$, for $1\leq i \leq k$, be as given by Fact \ref{fac: definable strong EH in distal} for $\varphi(x_1, \ldots, x_k;z)$.
Let $n_i \in \mathbb{N}$ be as given by Definition \ref{def: elimination of infinity} for $\psi_i(x_i,y_i)$, and let $n := \max \{ n_i : 1 \leq i \leq k \}$.
We take $N := \lceil \frac{n}{\alpha} \rceil$, then $N = N(\varphi)$.

Let $c \in M^{|z|}$ be arbitrary, and let $R := \varphi(M^{|x_1|}, \ldots, M^{|x_k|}, c)$. Assume that (1) holds. That is, there are some $A_i \subseteq M^{|x_i|}$ such that $|A_1| = \ldots = |A_k| = N$ and $A_1 \times \ldots \times A_k \subseteq R$. Let $\mu_i$ be a Keisler measure on $M^{|x_i|}$ defined by $\mu_i(X) := \frac{|A_i \cap X|}{|A_i|}$ for all definable $X \subseteq M^{|x_i|}$, then $\mu_i$ is generically stable for all $1 \leq i \leq k$. Applying Fact \ref{fac: definable strong EH in distal}, we find some $b_i \in M^{|y_i|}$ such that $\mu_i(\psi_i(M^{|x_i|}, b_i)) \geq \alpha$ and $\prod_{1\leq i \leq k} \psi_i(M^{|x_i|},b_i) \subseteq R$ (note that $\prod_{1\leq i \leq k} \psi_i(M^{|x_i|},b_i) \subseteq \neg R$ is impossible as $\prod_{1 \leq i \leq k} A_i \subseteq R$). Now for any $1\leq i \leq k$, $\mu_i(\psi_i(M^{|x_i|}, b_i)) \geq \alpha$ implies $|\psi_i(A_i, b_i)| \geq \alpha N \geq n_i$, hence $\psi_i(M^{|x_i|}, b_i)$ is infinite by the choice of $n_i$, as wanted.
\end{proof}

\begin{rem}
Examples of structures satisfying the assumption of Theorem \ref{thm: distal BukhMatousek} are given by arbitrary $o$-minimal structures and $p$-minimal structures (e.g. the field $\mathbb{Q}_p$). Hence Fact \ref{fac: semialg BM} follows by applying it to the field of reals.

\subsection{The $o$-minimal case}

Theorem \ref{thm: distal BukhMatousek} implies that in Theorem \ref{thm: distal Zarank}, assuming $\mathcal{M}$ eliminates $\exists^\infty$, we can relax the assumption to just assuming that $E$ doesn't contain a copy of an infinite complete bipartite graph.
\end{rem}
We conclude by observing that all of these results apply to $o$-minimal expansions of fields.

\begin{thm}\label{thm: everything o-min}
Let $\CM$ be an $o$-minimal expansion of a field and let $E(x;y) \subseteq M^2 \times M^d$ be a definable relation. 

\begin{enumerate}
\item For every $k \in \mathbb{N}$ there is a constant $c = c(E,k)$ such that for any finite $P \subseteq M^2, Q \subseteq M^d$, $|P|=m, |Q| = n$, if $E(P,Q)$ does not contain a copy of $K_{k,k}$ (the complete bipartite graph with two parts of size $k$), then we have 
	$$ |E(P,Q)| \leq c \left( m^{\frac{d}{2d-1}} n^{\frac{2d-2}{2d-1}} + m + n \right).$$

	\item There is some $k' \in \mathbb{N}$ and formulas $\varphi(x,v), \psi(y,w)$ depending only on $E$ such that if $E$ contains a copy of $K_{k',k'}$, then there are some parameters $b \in M^v, c \in M^w$ such that both $\varphi(M,b)$ and $ \psi(M,c)$ are infinite and $\varphi(M,b) \times \psi(M,c) \subseteq E$.
	
		\end{enumerate}
\end{thm}

\begin{proof}
(1) Follows by applying Theorem \ref{thm: distal Zarank}. Its assumptions are satisfied for $E$ by Theorem \ref{thm:cell-dec} and by Fact \ref {fac: vc bound in o-min} (applied to the dual formula $E^*(y;x)$).

(2) Follows by Theorem \ref{thm: distal BukhMatousek} as $o$-minimal theories eliminate the $\exists^\infty$ quantifier.

\end{proof}

\begin{cor}
In the setting of Theorem \ref{thm: everything o-min}, there is a constant $c$ and formulas $\varphi(x,v), \psi(y,w)$ depending only on $E$ such that either 	
	$$ |E(P,Q)| \leq c \left( m^{\frac{d}{2d-1}} n^{\frac{2d-2}{2d-1}} + m + n \right)$$
 for all finite $P \subseteq M^2, Q \subseteq M^d$ with $|P|=m, |Q| = n$, or there are some  $b \in M^v, c \in M^w$ such that both $\varphi(M,b)$ and $ \psi(M,c)$ are infinite and $\varphi(M,b) \times \psi(M,c) \subseteq E$.

\end{cor}
\begin{proof}
Immediate combining (1) and (2) in Theorem \ref{thm: everything o-min} (let $k'$, $\varphi$, $\psi$ be as given by (2) for $E(x,y)$, and let $c$ be as given by (1) for this $k'$).
\end{proof}

\begin{rem}
The special case with $d=2$ and $E$ satisfying an additional assumption of $1$-dimensionality of its fibers was obtained independently by Basu and Raz \cite{basu2016minimal} using different methods.
\end{rem}







\bibliographystyle{acm}
\bibliography{refs}

\end{document}








declar.tex
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Theorem}[section]
\newtheorem*{thm*}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{claim}[thm]{Claim}
\newtheorem{fact}[thm]{Fact}
\newtheorem{prob}[thm]{Problem}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
%\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{ntn}[thm]{Notation}
\newtheorem{rem}[thm]{Remark}
\newtheorem{con}{Construction}
\newtheorem{sample}[thm]{Example} \numberwithin{equation}{section}
\newenvironment{inrmk} % Inline remark
    {\medskip\begingroup\leftskip 0.5cm\rightskip 0.5cm\noindent\begin{small}{\bf Remark.}}
    {\end{small}\par\endgroup}
\newenvironment{mylist} % formylist
{\begin{list}{$\bullet$}
 {\settowidth{\labelwidth}{\textsf{$\bullet$}} \setlength{\leftmargin}{10pt}}}
{\end{list}}


\newcounter{ssample}[section]

\newenvironment{ssample} % fo example
{\color{Bittersweet} \noindent Example \refstepcounter{ssample}\hbox{\bf \arabic{section}.\arabic{ssample}.}}
{}


\newcounter{insertcount}

\newenvironment{insertt}[1] % Inline insert
    {\color{blue} \medskip\begingroup\noindent\begin{small}{\color{blue} \stepcounter{insertcount}
          {
            \bf Insert \arabic{insertcount}. #1.}
            \addcontentsline{toc}{subsection}{{\ \ \small  Insert \arabic{insertcount}: #1}}
               \leavevmode  }
           }
    {\end{small}\par\endgroup}





\newcommand{\mrmk}[1]%marginal remark
{{\tiny$^{\spadesuit}$}\marginpar{\fbox{\footnotesize #1}}}
\def\strutdepth{\dp\strutbox}%
\def\marginalnote#1{\strut\vadjust{\kern-\strutdepth\specialnote{#1}}}%
\def\specialnote#1{\vtop to \strutdepth{\baselineskip%
\strutdepth\vss\llap{\hbox{\scriptsize \bf #1}}\null}}%

\newcommand{\vlabel}[1]{{\marginalnote{ \boxed{#1}}}\label{#1}}
%\newcommand{\vlabel}[1]{{\marginpar{ \boxed{#1}}}\label{#1}}
\newcommand{\elabel}[1]{\marginalnote{\boxed{#1}}\label{#1} }




\newcommand{\CN}{\mathcal N}

%MATH_____________________
\newcommand{\KK}{\mathbf{K}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}

\def\gac{\cdot} % group action
\def\op{\circ} % jordan algebra operation
\def\g{\mathfrak{g}}
\def\h{\mathfrak{h}}
\def\a{\mathfrak{a}}
\def\gl{\mathfrak{gl}}
\def\sl{\mathfrak{sl}}
\def\sp{\mathfrak{sp}}
\def\ft{\mathfrak{t}}
\def\fp{\mathfrak{p}}
\def\fu{\mathfrak{u}}

\def\GG{\mathbb{G}}
%\def\tr{\operatorname{tr}}
\def\ad{\operatorname{ad}}
\def\Ad{\operatorname{Ad}}
\def\GL{\operatorname{GL}}
\def\End{\operatorname{End}}
\def\Gl{\operatorname{gl}}
\def\Int{\operatorname{Int}}
\def\Aut{\operatorname{Aut}}
\def\Der{\operatorname{Der}}
\def\Hom{\operatorname{Hom}}
\def\Re{\operatorname{Re}}

\def\vc{\operatorname{vc}}


% MATH -----------------------------------------------------------
\def\DD{\mathcal D}
\newcommand{\QQ}{\mathbb{Q}}
\def\CD{\mathcal{D}}
\def\FX{\frak X}
\def\oDD{\overline{\DD}}
\def\bDD{\partial \DD}
\def\KK{\mathbb K}
\def\CF{\mathcal F}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\CR}{\mathcal R} %rge structure
\newcommand{\NN}{\mathbb N}
\newcommand{\rarr}{\rightarrow}
\newcommand{\rest}{\!\!\upharpoonright\!}
\newcommand{\rrest}{\upharpoonright}
\newcommand{\co}{\circ}
\newcommand{\id}{\mathrm{id}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\PP}{\mathbb{P}} %Projective space
\newcommand{\R}{\mathbf{R}}
\newcommand{\cchi}{{\raisebox{2pt}{\boldmath$\chi$}}}
\newcommand{\schi}{{\boldsymbol{\chi}}}
\newcommand{\Gr}{\mathrm{Gr}}
\def\tp{\mathrm{tp}}
\def\dcl{\mathrm{dcl}}
\newcommand{\sub}{\subseteq}
\newcommand{\1}{\mathbf{1}}
\newcommand{\CI}{\mathcal I}
\def\A{\mathfrak{A}}
\def\C{\mathfrak{C}}
\def\CE{\mathcal{E}}
\reversemarginpar
\def\Vs{V^\sharp}
\def\tCR{\tilde\CR}
\def\t{\tilde}
\def\n{\mathfrak{n}}
\def\m{\mathfrak{m}}
\def\CL{\mathcal{L}}
%\def\v{\mathfrak{v}}
%\addtolength{\parskip}{0.1in}
\def\st{\operatorname{st}}
\def\veq{\sim_\v}
\def\chalf{C^{1/2}}
\def\esubeq{\preccurlyeq}
\def\subeqe{\succcurlyeq}
\def\esub{\prec}
\def\sube{\succ}
\def\emptys{\varnothing}
\def\cl{\operatorname{cl}}
\def\CG{\mathcal G}
\def\gc{\g_{\CC}}
\def\gcr{\g_{\CC}^{\RR}}

\def\bc{\bold c}
\def\Sh{\frak}
\def\ep#1{e^{\frac{2\pi i}{#1}}}
\def\ai{j}
\def\tr#1{\prescript{t}{}{#1}} % transpose


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "paper"
%%% End:

localdef.tex
\def\CM{\mathcal{M}}
\def\CZ{\mathcal{Z}}
\def\CN{\mathcal{N}}
\def\CO{\mathcal{O}}
\def\Ip{I^+}
\def\Mp{M^+}
\def\St{\widetilde{S}}
\def\seq{\unlhd}
\def\UU{\mathbb{U}}
\def\Smu{\operatorname{Stab}^\mu}
\def\Stab{\operatorname{Stab}}
\def\ccdot{{.}}
\def\SL{\operatorname{SL}}
\gdef\CX{\mathcal{X}}
\gdef\bX{\mathbf{X}}
\DeclareRobustCommand{\rchi}{{\mathpalette\irchi\relax}}
\newcommand{\irchi}[2]{\raisebox{0.35ex}{$#1\chi$}} % inner command, used by \rchi
\gdef\elemeq{\preceq}
\gdef\dt{{\widehat{S}}}
\gdef\sv{$*$}

\newcommand*\bbar[1]{%
  \hbox{%
    \vbox{%
      \hrule height 0.5pt % The actual bar
      \kern0.5ex%         % Distance between bar and symbol
      \hbox{%
        \kern-0.1em%      % Shortening on the left side
        \ensuremath{#1}%
        \kern-0.1em%      % Shortening on the right side
      }%
    }%
  }%
} 
\gdef\Def{\operatorname{Def}}
\newcommand\odef[2]{%
\overline{\Def_{#1}(#2)^s}%
}%
\gdef\mh{\text{-}}
\gdef\M{\mathfrak{M}}
\gdef\Av{\operatorname{Av}}
\gdef\CP{\mathcal{P}}
\gdef\CU{\mathcal{U}}
\gdef\CB{\mathscr{B}}
\gdef\VV{\mathbb{V}}
\gdef\SS{\mathbb{S}}
\gdef\Rexp{\RR_{\mathrm{exp}}}
\gdef\mh{\text{-}}
\gdef\CT{{\mathcal{T}}}
\gdef\ttimes{{\times}}
\gdef\ddotsb{{\dotsb}}
DistalCuttingLemma.bbl
% \bib, bibdiv, biblist are defined by the amsrefs package.
\begin{bibdiv}
\begin{biblist}

\bib{VCD2}{article}{
      author={Aschenbrenner, Matthias},
      author={Dolich, Alf},
      author={Haskell, Deirdre},
      author={Macpherson, Dugald},
      author={Starchenko, Sergei},
       title={Vapnik--{C}hervonenkis density in some theories without the
  independence property, {II}},
        date={2013},
     journal={Notre Dame Journal of Formal Logic},
      volume={54},
      number={3-4},
       pages={311\ndash 363},
}

\bib{VCD1}{article}{
      author={Aschenbrenner, Matthias},
      author={Dolich, Alf},
      author={Haskell, Deirdre},
      author={Macpherson, Dugald},
      author={Starchenko, Sergei},
       title={Vapnik--{C}hervonenkis density in some theories without the
  independence property, {I}},
        date={2016},
     journal={Transactions of the American Mathematical Society},
      volume={368},
      number={8},
       pages={5889\ndash 5949},
}

\bib{basu2016minimal}{article}{
      author={Basu, Saugata},
      author={Raz, Orit~E},
       title={An o-minimal {S}zemer\'edi-{T}rotter theorem},
        date={2016},
     journal={Preprint, arXiv:1611.07362},
}

\bib{bm}{article}{
      author={Bukh, Boris},
      author={Matou{\v{s}}ek, Ji{\v{r}}{\'\i}},
       title={Erd{\H{o}}s--{S}zekeres-type statements: {R}amsey function and
  decidability in dimension $1$},
        date={2014},
     journal={Duke Mathematical Journal},
      volume={163},
      number={12},
       pages={2243\ndash 2270},
}

\bib{cuttings}{incollection}{
      author={Chazelle, Bernard},
       title={Cuttings},
        date={2005},
   booktitle={Handbook of data structures and applications},
   publisher={CRC Press 25},
       pages={25.1\ndash 25.10},
}

\bib{chaz}{article}{
      author={Chazelle, Bernard},
      author={Edelsbrunner, Herbert},
      author={Guibas, Leonidas~J},
      author={Sharir, Micha},
       title={{A singly exponential stratification scheme for real
  semi-algebraic varieties and its applications}},
        date={1991},
     journal={Theoretical Computer Science},
      volume={84},
      number={1},
       pages={77\ndash 105},
}

\bib{chernikov2015externally}{article}{
      author={Chernikov, Artem},
      author={Simon, Pierre},
       title={Externally definable sets and dependent pairs {II}},
        date={2015},
     journal={Transactions of the American Mathematical Society},
      volume={367},
      number={7},
       pages={5217\ndash 5235},
}

\bib{distal}{article}{
      author={Chernikov, Artem},
      author={Starchenko, Sergei},
       title={{Regularity lemma for distal structures}},
        date={2015},
     journal={Journal of the European Mathematical Society, accepted
  (arXiv:1507.01482)},
}

\bib{13}{article}{
      author={Clarkson, Kenneth~L},
      author={Shor, Peter~W},
       title={{Applications of random sampling in computational geometry. II}},
        date={1989},
     journal={Discrete \& Computational Geometry. An International Journal of
  Mathematics and Computer Science},
      volume={4},
      number={5},
       pages={387\ndash 421},
}

\bib{zaran}{article}{
      author={Fox, Jacob},
      author={Pach, J{\'a}nos},
      author={Sheffer, Adam},
      author={Suk, Andrew},
      author={Zahl, Joshua},
       title={{A semi-algebraic version of Zarankiewicz's problem}},
        date={2014},
     journal={Journal of the European Mathematical Society, accepted
  (arXiv:1407.5705)},
}

\bib{mbook}{book}{
      author={Matou{\v{s}}ek, Ji{\v{r}}{\'{\i}}},
       title={Lectures on discrete geometry},
      series={Graduate Texts in Mathematics},
   publisher={Springer-Verlag, New York},
        date={2002},
      volume={212},
        ISBN={0-387-95373-6},
         url={http://dx.doi.org/10.1007/978-1-4613-0039-7},
      review={\MR{1899299}},
}

\bib{pach1992repeated}{article}{
      author={Pach, J{\'a}nos},
      author={Sharir, Micha},
       title={Repeated angles in the plane and related problems},
        date={1992},
     journal={Journal of Combinatorial Theory, series A},
      volume={59},
      number={1},
       pages={12\ndash 22},
}

\bib{DistalPierre}{article}{
      author={Simon, Pierre},
       title={Distal and non-distal {NIP} theories},
        date={2013},
        ISSN={0168-0072},
     journal={Annals of Pure and Applied Logic},
      volume={164},
      number={3},
       pages={294 \ndash  318},
  url={http://www.sciencedirect.com/science/article/pii/S0168007212001790},
}

\bib{szemeredi1983extremal}{article}{
      author={Szemer{\'e}di, Endre},
      author={Trotter~Jr, William~T},
       title={Extremal problems in discrete geometry},
        date={1983},
     journal={Combinatorica},
      volume={3},
      number={3-4},
       pages={381\ndash 392},
}

\end{biblist}
\end{bibdiv}
