Return to Answer

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}$.

Your question can be translated 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$. If $d=0$ then $\mathcal{F}$ is finite, and the claim follows. Assume $d>0$.

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.

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.

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.

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 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 $k$.

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}$.

Your question can be translated 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 $k$.

The proof of your question now almost follows from applying Theorem 4 with $p=k$.

There is the issue of $B$ being a proper subset of $M$, which is not exactly analogous to the condition in Matousek's theorem. One would hope this makes no difference, and you may be able to insert the necessary changes.

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}$.

Your question can be translated 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$. If $d=0$ then $\mathcal{F}$ is finite, and the claim follows. Assume $d>0$.

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.

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.

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)$ 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 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)$ is simply that the independence dimension of $\mathcal{F}$ is $k$.

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}$.

Your question can be translated 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 $k$.

The proof of your question now almost follows from applying Theorem 4 with $p=k$.

There is the issue of $B$ being a proper subset of $M$, which is not exactly analogous to the condition in Matousek's theorem. One would hope this makes no difference, and you may be able to insert the necessary changes.

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.

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 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 $k$.

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}$.

Your question can be translated 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 $k$.

The proof of your question now almost follows from applying Theorem 4 with $p=k$.

There is the issue of $B$ being a proper subset of $M$, which is not exactly analogous to the condition in Matousek's theorem. One would hope this makes no difference, and you may be able to insert the necessary changes.