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 Model-Theoretic Helly's Theorem
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.


