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).