A Model-Theoretic Helly's Theorem - MathOverflow

A Model-Theoretic Helly's Theorem

2011-11-06T00:30:11Z

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

Answer by Hunter Johnson for A Model-Theoretic Helly's Theorem

2011-11-25T03:56:53Z

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.

Answer by Pierre Simon for A Model-Theoretic Helly's Theorem

2011-11-26T09:03:39Z

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.