A Model-Theoretic Helly's Theorem There is a combinatorial question posed to me (or rather, posed near me) by my adviser.  I am having quite a lot of difficulty proving it.  It goes:

For any NIP theory $T$ (complete with infinite models as usual) and any partitioned formula $\phi(x; y)$, there are natural numbers $k$ and $N$ such that for any finite sets $A$ and $B$, if $A$ is $k$-consistent in $B$, then there is a $B_0\subset B$ with $|B_0|=N$ and so that for any $a\in A$, there is $b\in B_0$ such that $\phi(a;b)$ holds.

Here, by $k$-consistent, we mean for any $a_1, \ldots, a_n\in A$ there is $b\in B$ such that $\bigwedge_{i=1}^n \phi(a_i,b)$ holds.  Also, while it isn't stated, we can take $A$ and $B$ to be sets of tuples; I don't think this affects much of anything.
This is used in a proof that NIP theories have UDTFS, in an unpublished paper by Pierre Simon and Artem Chernikov.  They claim this lemma has been proved "in the literature;" neither I nor my adviser has been able to verify this, except for a very long-winded probabilistic argument which feels non-illustrative.
So, what I'm hoping for is either a reference to where it has been proved (or even discussed), some direction on the literature hunt, or just an explanation of why it may or may not be true (or a counterexample, if it is false).  Just anything, really.
Note: this fails immediately in the unstable NIP case (take $A=B$ to be an $\omega$-sequence, ordered by $\phi$, so the sets $\phi(a_i,B)$ are strictly decreasing, infinite, with empty intersection).
 A: I believe this can be translated into a question about fractional Helly number, which is answered in a paper of Matousek.  
The citation is:  Bounded VC-Dimension Implies a Fractional Helly Theorem, Discrete & Computational Geometry, Volume 31, Number 2.  
A pdf can be found by googling "the (p,k) property, VC dimension"
For a set $X$, any $\mathcal{F} \subseteq \mathcal{P}(X)$ is a set system on $X$.
Theorem 4 of the paper states:

Let $\mathcal{F}$ be a set system with
  $\pi_{\mathcal{F}}^*(m) = o(m^k)$ for
  some integer $k$, and let $p \geq k$. 
  Then there is a constant $N$ such that
  the following holds for every finite
  $\mathcal{G} \subseteq \mathcal{F}$: 
  If $\mathcal{G}$ has the $(p,k)$
  property then $\tau(\mathcal{G}) \leq
> N$

The terminology in the theorem can be found online, but I will list some definitions here.
The symbol $\pi_{\mathcal{F}}^*(m)$ refers to the dual-shatter function of $\mathcal{F}$.  
A sufficient condition for the assumption $\pi_{\mathcal{F}}^*(m) = o(m^k)$ is simply that the independence dimension of $\mathcal{F}$ is at most $k-1$.  If you are unfamiliar with the dual-shatter function, more can be found in this paper: http://arxiv.org/abs/1109.5438.
We say that $\mathcal{F}$ has the $(p,k)$-property if among any $p$ elements of $\mathcal{F}$, some $k$ have non-empty intersection.  
The transversal number of $\mathcal{F}$, denoted $\tau(\mathcal{F})$, is the least integer $N$ such that there is a subset $X_0 \subseteq X$ with $|X_0|=N$, and $F \cap X_0 \neq \emptyset$ for every $F \in \mathcal{F}$.
I will try to translate your question as follows.  We make the assumption that there is some theory $T$ and monster $M \models T$ with respect to which formulas are evaluated.
Let $\varphi(x,y)$ be the given formula. As you remark, if $x$ and $y$ are tuples, rather than arity 1,  it makes no difference.  For sets $A$ and $B$, let $S_\phi(B)^A$ denote the set family
$$\lbrace \varphi(a;B): a \in A \rbrace$$
Take $\mathcal{F} = S_\phi(M)^M$.  Since $T$ is NIP (note we need only $\varphi$ NIP), $\mathcal{F}$ has finite independence dimension, say $d$. 
The $k$ that suffices for your claim is $d+1$.  The $N$ that suffices is given by applying Theorem 4 with $p=k=d+1$.
I will argue for the correctness of this statement.  If finite sets $A$ and $B$ are given, your hypothesis allows us to assume that $\mathcal{G} = S_\varphi(B)^A$ has the $(k,k)$ property.  
I now need to make an assumption which I cannot really justify, which is that although $\mathcal{G} \subseteq \mathcal{F}\vert_B$ rather than $\mathcal{G} \subseteq \mathcal{F}$, this makes no difference.
Given this assumption, Theorem 4 now gives a $B_0 \subseteq B$ of cardinality $N$ which pierces $\mathcal{G}$.  Translating this back to model theory, it is easy to see that $B_0$ is the set sought after.
A: First, let me point out that the proof of udtfs is joint work with Artem Chernikov.
Hunter Johnson's answer is correct. The reference is Matousek's paper. I don't know of any proof not using probabilty theory. I tried a little bit to look for a model theoretic proof, but did not find any.
However, Matousek's $(p,k)$-theorem gives us more than we need, and the proof can be made much shorter as:


*

*we are only interested in the case $p=k$ of the $(p,k)$-theorem,

*we do not need an optimal value of $k$.
I will sketch the argument:
Let $\phi(x,y)$, $A$ and $B$ as in your question.
Pick any $\epsilon>0$.
Use the VC-theorem to get $N$ such that for any probability measure on $A$, there is an $\epsilon$-net of size $N$ (namely, a subset $A_0$ of size $N$ such that for any $b$ the measure of $\phi(A,b)$ is within $\epsilon$ of $\frac {|\phi(A_0,b)|}{N}$.)
Assume that $A$ is $N$-consistent in $B$ (using your terminolgy). It follows that for any probability measure on $A$, there is $b$ such that $\phi(A,b)$ has measure at least $1-\epsilon$.
Next, apply Farkas' lemma exactly as in the paper by Alon and Kleitman to which Matousek refers (there are some unnecessary intermediate steps there). You obtain a measure on $B$ such that every subset $\phi(a,B)$ has large measure. Then apply the VC-theorem again to extract an $\epsilon$-net $B_0 \subseteq B$ of bounded size (for some, possibly smaller $\epsilon$). Then every $\phi(a,B)$ intersects $B_0$, so we have what we want.
Compared with Matousek's proof, we can avoid the fractional Helly property and Lemma 2.2 in Alon and Kleitman.
