MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
Edited with attribution; thanks for the response. – Richard Rast Nov 27 '11 at 19:23

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:

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.